aboutsummaryrefslogtreecommitdiff
path: root/mp_pub.c
diff options
context:
space:
mode:
Diffstat (limited to 'mp_pub.c')
-rw-r--r--mp_pub.c526
1 files changed, 526 insertions, 0 deletions
diff --git a/mp_pub.c b/mp_pub.c
new file mode 100644
index 0000000..7c2a373
--- /dev/null
+++ b/mp_pub.c
@@ -0,0 +1,526 @@
1/* This file is part of libbrandt.
2 * Copyright (C) 2016 GNUnet e.V.
3 *
4 * libbrandt is free software: you can redistribute it and/or modify it under
5 * the terms of the GNU General Public License as published by the Free Software
6 * Foundation, either version 3 of the License, or (at your option) any later
7 * version.
8 *
9 * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
10 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
11 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License along with
14 * libbrandt. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17/**
18 * @file mp_pub.c
19 * @brief Implementation of the m+1st price public outcome algorithm.
20 * @author Markus Teich
21 */
22
23#include "platform.h"
24
25#include <gcrypt.h>
26
27#include "crypto.h"
28#include "internals.h"
29#include "util.h"
30
31
32void
33mp_pub_prep_outcome (struct BRANDT_Auction *ad)
34{
35 gcry_mpi_t factor = gcry_mpi_new (256);
36 gcry_mpi_point_t subtr = gcry_mpi_point_new (0);
37 gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
38 gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
39 gcry_mpi_point_t *tlta1;
40 gcry_mpi_point_t *tltb1;
41 gcry_mpi_point_t **tlta2;
42 gcry_mpi_point_t **tltb2;
43 gcry_mpi_point_t **tlta3;
44 gcry_mpi_point_t **tltb3;
45
46 ad->gamma3 = smc_init3 (ad->n, 2, ad->k);
47 brandt_assert (ad->gamma3);
48
49 ad->delta3 = smc_init3 (ad->n, 2, ad->k);
50 brandt_assert (ad->delta3);
51
52 /* create temporary lookup tables with partial sums */
53 tlta1 = smc_init1 (ad->k);
54 tltb1 = smc_init1 (ad->k);
55 tlta2 = smc_init2 (ad->n, ad->k);
56 tltb2 = smc_init2 (ad->n, ad->k);
57 tlta3 = smc_init2 (ad->n, ad->k);
58 tltb3 = smc_init2 (ad->n, ad->k);
59
60 /* temporary lookup table for first summand (building ladder of bids) */
61 for (uint16_t i = 0; i < ad->n; i++)
62 {
63 smc_sums_partial (tlta3[i], ad->alpha[i], ad->k, 1, 1);
64 smc_sums_partial (tltb3[i], ad->beta[i], ad->k, 1, 1);
65 for (uint16_t j = 0; j < ad->k; j++)
66 {
67 gcry_mpi_ec_sub (tlta2[i][j],
68 tlta3[i][ad->k - 1],
69 tlta3[i][j],
70 ec_ctx);
71 gcry_mpi_ec_sub (tltb2[i][j],
72 tltb3[i][ad->k - 1],
73 tltb3[i][j],
74 ec_ctx);
75 }
76 brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][ad->k - 1]));
77 brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][ad->k - 1]));
78 }
79 for (uint16_t j = 0; j < ad->k; j++)
80 {
81 /* 2L - 2I */
82 smc_sum (tmpa, &tlta2[0][j], ad->n, ad->k);
83 smc_sum (tmpb, &tltb2[0][j], ad->n, ad->k);
84 gcry_mpi_ec_mul (tlta1[j], GCRYMPI_CONST_TWO, tmpa, ec_ctx);
85 gcry_mpi_ec_mul (tltb1[j], GCRYMPI_CONST_TWO, tmpb, ec_ctx);
86
87 /* I */
88 smc_sum (tmpa, &ad->alpha[0][j], ad->n, ad->k);
89 smc_sum (tmpb, &ad->beta[0][j], ad->n, ad->k);
90
91 /* 2L - 2I + I = 2L - I */
92 gcry_mpi_ec_add (tlta1[j], tlta1[j], tmpa, ec_ctx);
93 gcry_mpi_ec_add (tltb1[j], tltb1[j], tmpb, ec_ctx);
94 }
95 brandt_assert (!ec_point_cmp (tmpa, tlta1[ad->k - 1]));
96 brandt_assert (!ec_point_cmp (tmpb, tltb1[ad->k - 1]));
97
98 /* compute subtrahend: (2M+1)G */
99 gcry_mpi_set_ui (factor, ad->m);
100 gcry_mpi_lshift (factor, factor, 1);
101 gcry_mpi_add_ui (factor, factor, 1);
102 gcry_mpi_ec_mul (subtr, factor, ec_gen, ec_ctx);
103
104 /* compute gamma and delta for price determination */
105 for (uint16_t j = 0; j < ad->k; j++)
106 {
107 /* compute inner gamma */
108 gcry_mpi_ec_sub (tmpa, tlta1[j], subtr, ec_ctx);
109
110 /* inner delta */
111 ec_point_copy (tmpb, tltb1[j]);
112
113 /* copy unmasked outcome to all other bidder layers so they don't
114 * have to be recomputed to check the ZK proof_2dle's from other
115 * bidders when receiving their outcome messages */
116 for (uint16_t a = 0; a < ad->n; a++)
117 {
118 ec_point_copy (ad->gamma3[a][0][j], tmpa);
119 ec_point_copy (ad->delta3[a][0][j], tmpb);
120 }
121 }
122
123 /* gamma and delta for winner determination: compute
124 * @f$\sum_{h=1}^n\sum_{d=j+1}^k2^{h-1}b_h@f and store it in every bidders gamma and
125 * delta, since it is needed each time a gamma,delta pair is received from
126 * another bidder. */
127 for (uint16_t i = 0; i < ad->n; i++)
128 {
129 for (uint16_t j = 0; j < ad->k; j++)
130 {
131 /* initialize with zeroes, since we are calculating a sum */
132 ec_point_copy (ad->gamma3[i][1][j], ec_zero);
133 ec_point_copy (ad->delta3[i][1][j], ec_zero);
134 }
135 }
136 gcry_mpi_set_ui (factor, 1);
137 for (uint16_t h = 0; h < ad->n; h++)
138 {
139 for (uint16_t j = 0; j < ad->k; j++)
140 {
141 for (uint16_t d = j + 1; d < ad->k; d++)
142 {
143 gcry_mpi_ec_mul (tmpa, factor, ad->alpha[h][d], ec_ctx);
144 gcry_mpi_ec_add (ad->gamma3[0][1][j],
145 ad->gamma3[0][1][j],
146 tmpa,
147 ec_ctx);
148 gcry_mpi_ec_mul (tmpb, factor, ad->beta[h][d], ec_ctx);
149 gcry_mpi_ec_add (ad->delta3[0][1][j],
150 ad->delta3[0][1][j],
151 tmpb,
152 ec_ctx);
153 }
154 }
155 gcry_mpi_lshift (factor, factor, 1);
156 }
157 /* copy component to all bidders so they don't have to be recomputed */
158 for (uint16_t a = 1; a < ad->n; a++)
159 {
160 for (uint16_t j = 0; j < ad->k; j++)
161 {
162 ec_point_copy (ad->gamma3[a][1][j], ad->gamma3[0][1][j]);
163 ec_point_copy (ad->delta3[a][1][j], ad->delta3[0][1][j]);
164 }
165 }
166
167 gcry_mpi_release (factor);
168 gcry_mpi_point_release (subtr);
169 gcry_mpi_point_release (tmpa);
170 gcry_mpi_point_release (tmpb);
171 smc_free1 (tlta1, ad->k);
172 smc_free1 (tltb1, ad->k);
173 smc_free2 (tlta2, ad->n, ad->k);
174 smc_free2 (tltb2, ad->n, ad->k);
175 smc_free2 (tlta3, ad->n, ad->k);
176 smc_free2 (tltb3, ad->n, ad->k);
177}
178
179
180/**
181 * mp_pub_compute_outcome computes encrypted outcome shares and packs them into
182 * a message buffer together with proofs of correctnes.
183 *
184 * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
185 * @param[out] buflen Size of the returned message buffer in bytes
186 * @return A buffer containing the encrypted outcome vectors
187 * which needs to be broadcast
188 */
189unsigned char *
190mp_pub_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
191{
192 unsigned char *ret;
193 unsigned char *cur;
194 struct msg_head *head;
195 gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
196 gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
197 struct ec_mpi *gamma;
198 struct ec_mpi *delta;
199 struct proof_2dle *proof2;
200
201 brandt_assert (ad && buflen);
202
203 *buflen = (sizeof (*head) + /* msg header */
204 ad->k * /* k * (gamma, delta, proof2) */
205 (sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2)));
206 ret = GNUNET_new_array (*buflen, unsigned char);
207
208 head = (struct msg_head *)ret;
209 head->prot_version = htonl (0);
210 head->msg_type = htonl (msg_outcome);
211 cur = ret + sizeof (*head);
212
213 for (uint16_t j = 0; j < ad->k; j++)
214 {
215 gamma = (struct ec_mpi *)cur;
216 delta = &((struct ec_mpi *)cur)[1];
217 proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
218
219 /* only send the price determination gamma,delta pair, since the winner
220 * determination pair can and will be computed by the receiver */
221 ec_point_copy (tmpa, ad->gamma3[ad->i][0][j]);
222 ec_point_copy (tmpb, ad->delta3[ad->i][0][j]);
223
224 /* apply random masking for losing bidders */
225 smc_zkp_2dle (ad->gamma3[ad->i][0][j],
226 ad->delta3[ad->i][0][j],
227 tmpa,
228 tmpb,
229 NULL,
230 proof2);
231
232 ec_point_serialize (gamma, ad->gamma3[ad->i][0][j]);
233 ec_point_serialize (delta, ad->delta3[ad->i][0][j]);
234
235 /* compute own winner determination gamma,delta pair */
236 gcry_mpi_ec_add (ad->gamma3[ad->i][1][j],
237 ad->gamma3[ad->i][0][j],
238 ad->gamma3[ad->i][1][j],
239 ec_ctx);
240 gcry_mpi_ec_add (ad->delta3[ad->i][1][j],
241 ad->delta3[ad->i][0][j],
242 ad->delta3[ad->i][1][j],
243 ec_ctx);
244
245 cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
246 }
247
248 gcry_mpi_point_release (tmpa);
249 gcry_mpi_point_release (tmpb);
250 return ret;
251}
252
253
254int
255mp_pub_recv_outcome (struct BRANDT_Auction *ad,
256 const unsigned char *buf,
257 size_t buflen,
258 uint16_t sender)
259{
260 int ret = 0;
261 const unsigned char *cur = buf;
262 struct proof_2dle *proof2;
263 gcry_mpi_point_t gamma = gcry_mpi_point_new (0);
264 gcry_mpi_point_t delta = gcry_mpi_point_new (0);
265
266 brandt_assert (ad && buf);
267
268 if (buflen != (ad->k * (2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
269 {
270 weprintf ("wrong size of received outcome");
271 goto quit;
272 }
273
274 for (uint16_t j = 0; j < ad->k; j++)
275 {
276 ec_point_parse (gamma, (struct ec_mpi *)cur);
277 ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
278 proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
279 if (smc_zkp_2dle_check (gamma,
280 delta,
281 ad->gamma3[sender][0][j],
282 ad->delta3[sender][0][j],
283 proof2))
284 {
285 weprintf ("wrong zkp2 for gamma, delta received");
286 goto quit;
287 }
288 ec_point_copy (ad->gamma3[sender][0][j], gamma);
289 ec_point_copy (ad->delta3[sender][0][j], delta);
290
291 /* compute winner determination gamma,delta pair */
292 gcry_mpi_ec_add (ad->gamma3[sender][1][j],
293 ad->gamma3[sender][0][j],
294 ad->gamma3[sender][1][j],
295 ec_ctx);
296 gcry_mpi_ec_add (ad->delta3[sender][1][j],
297 ad->delta3[sender][0][j],
298 ad->delta3[sender][1][j],
299 ec_ctx);
300
301 cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
302 }
303
304 ret = 1;
305quit:
306 gcry_mpi_point_release (gamma);
307 gcry_mpi_point_release (delta);
308 return ret;
309}
310
311
312void
313mp_pub_prep_decryption (struct BRANDT_Auction *ad)
314{
315 gcry_mpi_point_t tmp_price = gcry_mpi_point_new (0);
316 gcry_mpi_point_t tmp_winner = gcry_mpi_point_new (0);
317
318 ad->phi3 = smc_init3 (ad->n, 2, ad->k);
319 brandt_assert (ad->phi3);
320
321 for (uint16_t j = 0; j < ad->k; j++)
322 {
323 smc_sum (tmp_price, &ad->delta3[0][0][j], ad->n, 2 * ad->k);
324 smc_sum (tmp_winner, &ad->delta3[0][1][j], ad->n, 2 * ad->k);
325
326 /* copy still encrypted outcome to all other bidder layers so they
327 * don't have to be recomputed to check the ZK proof_2dle's from
328 * other bidders when receiving their outcome decryption messages */
329 for (uint16_t a = 0; a < ad->n; a++)
330 {
331 ec_point_copy (ad->phi3[a][0][j], tmp_price);
332 ec_point_copy (ad->phi3[a][1][j], tmp_winner);
333 }
334 }
335
336 gcry_mpi_point_release (tmp_price);
337 gcry_mpi_point_release (tmp_winner);
338}
339
340
341/**
342 * mp_pub_decrypt_outcome decrypts part of the outcome and packs it into a
343 * message buffer together with proofs of correctnes.
344 *
345 * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
346 * @param[out] buflen Size of the returned message buffer in bytes
347 * @return A buffer containing the own share of the decrypted outcome
348 * which needs to be broadcast
349 */
350unsigned char *
351mp_pub_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
352{
353 unsigned char *ret;
354 unsigned char *cur;
355 gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
356 struct msg_head *head;
357 struct ec_mpi *phi;
358 struct proof_2dle *proof2;
359
360 brandt_assert (ad && buflen);
361
362 *buflen = (sizeof (*head) + 2 * ad->k * (sizeof (*phi) + sizeof (*proof2)));
363 ret = GNUNET_new_array (*buflen, unsigned char);
364
365 head = (struct msg_head *)ret;
366 head->prot_version = htonl (0);
367 head->msg_type = htonl (msg_decrypt);
368 cur = ret + sizeof (*head);
369
370 /* decrypt price and winner components */
371 for (uint16_t comp = 0; comp < 2; comp++)
372 {
373 for (uint16_t j = 0; j < ad->k; j++)
374 {
375 phi = (struct ec_mpi *)cur;
376 proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
377
378 ec_point_copy (tmp, ad->phi3[ad->i][comp][j]);
379
380 /* decrypt outcome component and prove the correct key was used */
381 smc_zkp_2dle (ad->phi3[ad->i][comp][j],
382 NULL,
383 tmp,
384 ec_gen,
385 ad->x,
386 proof2);
387
388 ec_point_serialize (phi, ad->phi3[ad->i][comp][j]);
389
390 cur += sizeof (*phi) + sizeof (*proof2);
391 }
392 }
393
394 gcry_mpi_point_release (tmp);
395 return ret;
396}
397
398
399int
400mp_pub_recv_decryption (struct BRANDT_Auction *ad,
401 const unsigned char *buf,
402 size_t buflen,
403 uint16_t sender)
404{
405 int ret = 0;
406 const unsigned char *cur = buf;
407 struct proof_2dle *proof2;
408 gcry_mpi_point_t phi = gcry_mpi_point_new (0);
409
410 brandt_assert (ad && buf);
411
412 if (buflen != (2 * ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
413 {
414 weprintf ("wrong size of received outcome decryption");
415 goto quit;
416 }
417
418 /* handle received price and winner components */
419 for (uint16_t comp = 0; comp < 2; comp++)
420 {
421 for (uint16_t j = 0; j < ad->k; j++)
422 {
423 ec_point_parse (phi, (struct ec_mpi *)cur);
424 proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
425
426 if (smc_zkp_2dle_check (phi,
427 ad->y[sender],
428 ad->phi3[sender][comp][j],
429 ec_gen,
430 proof2))
431 {
432 weprintf ("wrong zkp2 for phi, y received");
433 goto quit;
434 }
435 ec_point_copy (ad->phi3[sender][comp][j], phi);
436 cur += sizeof (struct ec_mpi) + sizeof (*proof2);
437 }
438 }
439
440 ret = 1;
441quit:
442 gcry_mpi_point_release (phi);
443 return ret;
444}
445
446
447struct BRANDT_Result *
448mp_pub_determine_outcome (struct BRANDT_Auction *ad,
449 uint16_t *len)
450{
451 struct BRANDT_Result *ret;
452 int32_t price = -1;
453 uint16_t cur_winner = 0;
454 int dlogi = -1;
455 gcry_mpi_point_t sum_gamma = gcry_mpi_point_new (0);
456 gcry_mpi_point_t sum_phi = gcry_mpi_point_new (0);
457
458 brandt_assert (ad);
459
460 for (uint16_t j = ad->k - 1; j >= 0; j--)
461 {
462 smc_sum (sum_gamma, &ad->gamma3[0][0][j], ad->n, 2 * ad->k);
463 smc_sum (sum_phi, &ad->phi3[0][0][j], ad->n, 2 * ad->k);
464 gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
465 /* first zero component determines the price */
466 if (!ec_point_cmp (sum_gamma, ec_zero))
467 {
468 price = j;
469 break;
470 }
471 }
472
473 if (-1 == price)
474 return NULL;
475
476 /* extract winners point for the winning price */
477 smc_sum (sum_gamma, &ad->gamma3[0][1][price], ad->n, 2 * ad->k);
478 smc_sum (sum_phi, &ad->phi3[0][1][price], ad->n, 2 * ad->k);
479 gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
480
481 dlogi = GNUNET_CRYPTO_ecc_dlog (ec_dlogctx, sum_gamma);
482 brandt_assert (dlogi > 0);
483
484 /* all bidders participated with a multiplicative share */
485 dlogi /= ad->n;
486
487 price = price / ad->n;
488 ret = GNUNET_new_array (ad->m, struct BRANDT_Result);
489
490 /* can only support up to bits(dlogi) bidders */
491 brandt_assert (sizeof (int) * 8 > ad->n);
492 for (uint16_t i = 0; i < ad->n; i++)
493 {
494 /* a set bit determines a winner */
495 if (dlogi & (1 << i))
496 {
497 if (cur_winner >= ad->m)
498 {
499 weprintf ("too many winners detected");
500 GNUNET_free (ret);
501 ret = NULL;
502 goto quit;
503 }
504
505 ret[cur_winner].bidder = i;
506 ret[cur_winner].price = price;
507 ret[cur_winner].status = BRANDT_bidder_won;
508 cur_winner++;
509 }
510 }
511
512 if (cur_winner != ad->m)
513 {
514 weprintf ("too few winners detected");
515 GNUNET_free (ret);
516 ret = NULL;
517 goto quit;
518 }
519
520 if (len)
521 *len = ad->m;
522quit:
523 gcry_mpi_point_release (sum_gamma);
524 gcry_mpi_point_release (sum_phi);
525 return ret;
526}
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-25 20:56:47 +0000