]> git.siccegge.de Git - software/DIPE.git/blob - src/SS.cxx
benchmarks\~
[software/DIPE.git] / src / SS.cxx
1 #include "DIPE.h"
2 #include "DIPE_Internal.h"
3
4 #include <assert.h>
5
6 namespace {
7 void dipe_ss_esf(dipe_param_t param, size_t size, size_t m, size_t excl, element_t* elements, element_t* result) {
8 assert(size >= m);
9
10 if (m == 0) {
11 element_set1(*result);
12 return;
13 }
14
15 /* m = n */
16 if (size == m || (m + 1 == size && excl <= size)) {
17 assert((size == m) ? excl > size : true);
18 element_set1(*result);
19 for (size_t i = 0; i < size; ++i) {
20 if (i != excl) {
21 element_mul(*result, *result, elements[i]);
22 }
23 }
24 return;
25 }
26 /* m = 1 */
27 if (m == 1) {
28 element_set0(*result);
29 for (size_t i = 0; i < size; ++i) {
30 if (i != excl) {
31 element_add(*result, *result, elements[i]);
32 }
33 }
34 return;
35 }
36
37 /* otherwise */
38 element_t lhs;
39 element_init_Zr(lhs, param->pairing);
40 dipe_ss_esf(param, size-1, m, excl, elements, result);
41 dipe_ss_esf(param, size-1, m-1, excl, elements, &lhs);
42 element_mul(lhs, lhs, elements[size-1]);
43 element_add(*result, *result, lhs);
44 element_clear(lhs);
45 }
46
47
48 /* https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix
49 * Contract: result is allocated but not initialized size x size array
50 */
51 void dipe_ss_inverse_vandermonde(dipe_param_t param, bool flat, size_t size, element_t* elements, element_t** result) {
52 /* b_ij = (-1)^{n-i} e_{n-i}() / \Prod ()
53 */
54 element_t numerator, denominator;
55 element_t tmp;
56 element_init_Zr(numerator, param->pairing);
57 element_init_Zr(denominator, param->pairing);
58 element_init_Zr(tmp, param->pairing);
59
60 for (size_t i = 0; i < size; ++i) {
61 if (flat && i > 0) continue;
62
63 for (size_t j = 0; j < size; ++j) {
64 element_init_Zr(result[i][j], param->pairing);
65
66 /* numerator */
67 dipe_ss_esf(param, size, size-i-1, j, elements, &numerator);
68 if (((size - i-1) & 1) == 1) {
69 element_neg(numerator, numerator);
70 }
71
72 /* denominator */
73 element_set1(denominator);
74 for (size_t k = 0; k < size; ++k) {
75 if (k != j) {
76 element_sub(tmp, elements[j], elements[k]);
77 element_mul(denominator, denominator, tmp);
78 }
79 }
80
81 element_div(result[i][j], numerator, denominator);
82 }
83 }
84 element_clear(tmp);
85 element_clear(numerator);
86 element_clear(denominator);
87 }
88 }
89
90 void dipe_ss_share(dipe_param_t param, size_t id_size, element_t* ids, size_t fid_size, element_t* fake_ids, size_t share_size, element_t** shares,
91 element_t* secret, element_t** dummy_shares) {
92 element_t tmp;
93 element_t tmpz;
94 element_t a_pow;
95 element_init_same_as(tmp, shares[0][0]);
96 element_init_Zr(tmpz, param->pairing);
97 element_init_Zr(a_pow, param->pairing);
98
99 /* Precompute V_I^{-1} needed in several steps */
100 element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
101 for (size_t i = 0; i < id_size; ++i) {
102 b[i] = (element_t*)calloc(id_size, sizeof(element_t));
103 }
104 dipe_ss_inverse_vandermonde(param, false, id_size, ids, b);
105
106 /* Compute Secret */
107 for (size_t k = 0; k < share_size; ++k) {
108 element_init_same_as(secret[k], shares[0][0]);
109 element_set1(secret[k]);
110 for (size_t j = 0; j < id_size; ++j) {
111 element_pow_zn(tmp, shares[j][k], b[0][j]);
112 element_mul(secret[k], secret[k], tmp);
113 }
114 }
115
116 /* Compute Dummy Shares */
117 /* Matrix Product */
118 element_t** ab = (element_t**)calloc(id_size, sizeof(element_t*));
119 for (size_t i = 0; i < fid_size; ++i) {
120 ab[i] = (element_t*)calloc(id_size, sizeof(element_t));
121
122 for (size_t j = 0; j < id_size; ++j) {
123 element_init_Zr(ab[i][j], param->pairing);
124 element_set0(ab[i][j]);
125 element_set1(a_pow);
126
127 for (size_t k = 0; k < id_size; ++ k) {
128 element_mul(tmpz, a_pow, b[k][j]);
129 element_add(ab[i][j], ab[i][j], tmpz);
130 element_mul(a_pow, a_pow, fake_ids[i]);
131 }
132 }
133 }
134
135 /* Matrix Product. Note this is an abuse of notation and we're doing scalar * group in additive writing */
136 for (size_t i = 0; i < fid_size; ++ i) {
137 for (size_t j = 0; j < share_size; ++j) {
138 element_init_same_as(dummy_shares[i][j], shares[0][0]);
139 element_set1(dummy_shares[i][j]);
140 for (size_t k = 0; k < id_size; ++k) {
141 element_pow_zn(tmp, shares[k][j], ab[i][k]);
142 element_mul(dummy_shares[i][j], dummy_shares[i][j], tmp);
143 }
144 }
145 }
146
147 for (size_t i = 0; i < id_size; ++i) {
148 for (size_t j = 0; j < id_size; ++j) {
149 element_clear(b[i][j]);
150 }
151 free(b[i]);
152 }
153 free(b);
154
155 for (size_t i = 0; i < fid_size; ++i) {
156 for (size_t j = 0; j < id_size; ++j) {
157 element_clear(ab[i][j]);
158 }
159 free(ab[i]);
160 }
161 free(ab);
162 element_clear(tmp);
163 element_clear(tmpz);
164 element_clear(a_pow);
165 }
166
167 void dipe_ss_recover(dipe_param_t param, size_t id_size, element_t* ids, size_t share_size, element_t** shares, element_t* secret) {
168 element_t tmp;
169 /* TODO: fix type, shares are in G_t here~ */
170 element_init_same_as(tmp, shares[0][0]);
171
172 /* Precompute V_I^{-1} needed in several steps */
173 /* Actually for recover we only need the values b[0][j] */
174 element_t** b = (element_t**)calloc(1, sizeof(element_t*));
175 b[0] = (element_t*)calloc(id_size, sizeof(element_t));
176 dipe_ss_inverse_vandermonde(param, true, id_size, ids, b);
177
178 /* Compute Secret */
179 for (size_t k = 0; k < share_size; ++k) {
180 element_init_same_as(secret[k], shares[0][0]);
181 element_set1(secret[k]);
182 for (size_t j = 0; j < id_size; ++j) {
183 element_pow_zn(tmp, shares[j][k], b[0][j]);
184 element_mul(secret[k], secret[k], tmp);
185 }
186 }
187
188 for (size_t j = 0; j < id_size; ++j) {
189 element_clear(b[0][j]);
190 }
191 free(b[0]);
192 free(b);
193 element_clear(tmp);
194 }