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 @@
+/* This file is part of libbrandt.
+ * Copyright (C) 2016 GNUnet e.V.
+ *
+ * libbrandt is free software: you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later
+ * version.
+ *
+ * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * libbrandt. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file mp_pub.c
+ * @brief Implementation of the m+1st price public outcome algorithm.
+ * @author Markus Teich
+ */
+
+#include "platform.h"
+
+#include <gcrypt.h>
+
+#include "crypto.h"
+#include "internals.h"
+#include "util.h"
+
+
+void
+mp_pub_prep_outcome (struct BRANDT_Auction *ad)
+{
+ gcry_mpi_t factor = gcry_mpi_new (256);
+ gcry_mpi_point_t subtr = gcry_mpi_point_new (0);
+ gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
+ gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
+ gcry_mpi_point_t *tlta1;
+ gcry_mpi_point_t *tltb1;
+ gcry_mpi_point_t **tlta2;
+ gcry_mpi_point_t **tltb2;
+ gcry_mpi_point_t **tlta3;
+ gcry_mpi_point_t **tltb3;
+
+ ad->gamma3 = smc_init3 (ad->n, 2, ad->k);
+ brandt_assert (ad->gamma3);
+
+ ad->delta3 = smc_init3 (ad->n, 2, ad->k);
+ brandt_assert (ad->delta3);
+
+ /* create temporary lookup tables with partial sums */
+ tlta1 = smc_init1 (ad->k);
+ tltb1 = smc_init1 (ad->k);
+ tlta2 = smc_init2 (ad->n, ad->k);
+ tltb2 = smc_init2 (ad->n, ad->k);
+ tlta3 = smc_init2 (ad->n, ad->k);
+ tltb3 = smc_init2 (ad->n, ad->k);
+
+ /* temporary lookup table for first summand (building ladder of bids) */
+ for (uint16_t i = 0; i < ad->n; i++)
+ {
+ smc_sums_partial (tlta3[i], ad->alpha[i], ad->k, 1, 1);
+ smc_sums_partial (tltb3[i], ad->beta[i], ad->k, 1, 1);
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ gcry_mpi_ec_sub (tlta2[i][j],
+ tlta3[i][ad->k - 1],
+ tlta3[i][j],
+ ec_ctx);
+ gcry_mpi_ec_sub (tltb2[i][j],
+ tltb3[i][ad->k - 1],
+ tltb3[i][j],
+ ec_ctx);
+ }
+ brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][ad->k - 1]));
+ brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][ad->k - 1]));
+ }
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ /* 2L - 2I */
+ smc_sum (tmpa, &tlta2[0][j], ad->n, ad->k);
+ smc_sum (tmpb, &tltb2[0][j], ad->n, ad->k);
+ gcry_mpi_ec_mul (tlta1[j], GCRYMPI_CONST_TWO, tmpa, ec_ctx);
+ gcry_mpi_ec_mul (tltb1[j], GCRYMPI_CONST_TWO, tmpb, ec_ctx);
+
+ /* I */
+ smc_sum (tmpa, &ad->alpha[0][j], ad->n, ad->k);
+ smc_sum (tmpb, &ad->beta[0][j], ad->n, ad->k);
+
+ /* 2L - 2I + I = 2L - I */
+ gcry_mpi_ec_add (tlta1[j], tlta1[j], tmpa, ec_ctx);
+ gcry_mpi_ec_add (tltb1[j], tltb1[j], tmpb, ec_ctx);
+ }
+ brandt_assert (!ec_point_cmp (tmpa, tlta1[ad->k - 1]));
+ brandt_assert (!ec_point_cmp (tmpb, tltb1[ad->k - 1]));
+
+ /* compute subtrahend: (2M+1)G */
+ gcry_mpi_set_ui (factor, ad->m);
+ gcry_mpi_lshift (factor, factor, 1);
+ gcry_mpi_add_ui (factor, factor, 1);
+ gcry_mpi_ec_mul (subtr, factor, ec_gen, ec_ctx);
+
+ /* compute gamma and delta for price determination */
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ /* compute inner gamma */
+ gcry_mpi_ec_sub (tmpa, tlta1[j], subtr, ec_ctx);
+
+ /* inner delta */
+ ec_point_copy (tmpb, tltb1[j]);
+
+ /* copy unmasked outcome to all other bidder layers so they don't
+ * have to be recomputed to check the ZK proof_2dle's from other
+ * bidders when receiving their outcome messages */
+ for (uint16_t a = 0; a < ad->n; a++)
+ {
+ ec_point_copy (ad->gamma3[a][0][j], tmpa);
+ ec_point_copy (ad->delta3[a][0][j], tmpb);
+ }
+ }
+
+ /* gamma and delta for winner determination: compute
+ * @f$\sum_{h=1}^n\sum_{d=j+1}^k2^{h-1}b_h@f and store it in every bidders gamma and
+ * delta, since it is needed each time a gamma,delta pair is received from
+ * another bidder. */
+ for (uint16_t i = 0; i < ad->n; i++)
+ {
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ /* initialize with zeroes, since we are calculating a sum */
+ ec_point_copy (ad->gamma3[i][1][j], ec_zero);
+ ec_point_copy (ad->delta3[i][1][j], ec_zero);
+ }
+ }
+ gcry_mpi_set_ui (factor, 1);
+ for (uint16_t h = 0; h < ad->n; h++)
+ {
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ for (uint16_t d = j + 1; d < ad->k; d++)
+ {
+ gcry_mpi_ec_mul (tmpa, factor, ad->alpha[h][d], ec_ctx);
+ gcry_mpi_ec_add (ad->gamma3[0][1][j],
+ ad->gamma3[0][1][j],
+ tmpa,
+ ec_ctx);
+ gcry_mpi_ec_mul (tmpb, factor, ad->beta[h][d], ec_ctx);
+ gcry_mpi_ec_add (ad->delta3[0][1][j],
+ ad->delta3[0][1][j],
+ tmpb,
+ ec_ctx);
+ }
+ }
+ gcry_mpi_lshift (factor, factor, 1);
+ }
+ /* copy component to all bidders so they don't have to be recomputed */
+ for (uint16_t a = 1; a < ad->n; a++)
+ {
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ ec_point_copy (ad->gamma3[a][1][j], ad->gamma3[0][1][j]);
+ ec_point_copy (ad->delta3[a][1][j], ad->delta3[0][1][j]);
+ }
+ }
+
+ gcry_mpi_release (factor);
+ gcry_mpi_point_release (subtr);
+ gcry_mpi_point_release (tmpa);
+ gcry_mpi_point_release (tmpb);
+ smc_free1 (tlta1, ad->k);
+ smc_free1 (tltb1, ad->k);
+ smc_free2 (tlta2, ad->n, ad->k);
+ smc_free2 (tltb2, ad->n, ad->k);
+ smc_free2 (tlta3, ad->n, ad->k);
+ smc_free2 (tltb3, ad->n, ad->k);
+}
+
+
+/**
+ * mp_pub_compute_outcome computes encrypted outcome shares and packs them into
+ * a message buffer together with proofs of correctnes.
+ *
+ * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
+ * @param[out] buflen Size of the returned message buffer in bytes
+ * @return A buffer containing the encrypted outcome vectors
+ * which needs to be broadcast
+ */
+unsigned char *
+mp_pub_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
+{
+ unsigned char *ret;
+ unsigned char *cur;
+ struct msg_head *head;
+ gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
+ gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
+ struct ec_mpi *gamma;
+ struct ec_mpi *delta;
+ struct proof_2dle *proof2;
+
+ brandt_assert (ad && buflen);
+
+ *buflen = (sizeof (*head) + /* msg header */
+ ad->k * /* k * (gamma, delta, proof2) */
+ (sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2)));
+ ret = GNUNET_new_array (*buflen, unsigned char);
+
+ head = (struct msg_head *)ret;
+ head->prot_version = htonl (0);
+ head->msg_type = htonl (msg_outcome);
+ cur = ret + sizeof (*head);
+
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ gamma = (struct ec_mpi *)cur;
+ delta = &((struct ec_mpi *)cur)[1];
+ proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
+
+ /* only send the price determination gamma,delta pair, since the winner
+ * determination pair can and will be computed by the receiver */
+ ec_point_copy (tmpa, ad->gamma3[ad->i][0][j]);
+ ec_point_copy (tmpb, ad->delta3[ad->i][0][j]);
+
+ /* apply random masking for losing bidders */
+ smc_zkp_2dle (ad->gamma3[ad->i][0][j],
+ ad->delta3[ad->i][0][j],
+ tmpa,
+ tmpb,
+ NULL,
+ proof2);
+
+ ec_point_serialize (gamma, ad->gamma3[ad->i][0][j]);
+ ec_point_serialize (delta, ad->delta3[ad->i][0][j]);
+
+ /* compute own winner determination gamma,delta pair */
+ gcry_mpi_ec_add (ad->gamma3[ad->i][1][j],
+ ad->gamma3[ad->i][0][j],
+ ad->gamma3[ad->i][1][j],
+ ec_ctx);
+ gcry_mpi_ec_add (ad->delta3[ad->i][1][j],
+ ad->delta3[ad->i][0][j],
+ ad->delta3[ad->i][1][j],
+ ec_ctx);
+
+ cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
+ }
+
+ gcry_mpi_point_release (tmpa);
+ gcry_mpi_point_release (tmpb);
+ return ret;
+}
+
+
+int
+mp_pub_recv_outcome (struct BRANDT_Auction *ad,
+ const unsigned char *buf,
+ size_t buflen,
+ uint16_t sender)
+{
+ int ret = 0;
+ const unsigned char *cur = buf;
+ struct proof_2dle *proof2;
+ gcry_mpi_point_t gamma = gcry_mpi_point_new (0);
+ gcry_mpi_point_t delta = gcry_mpi_point_new (0);
+
+ brandt_assert (ad && buf);
+
+ if (buflen != (ad->k * (2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
+ {
+ weprintf ("wrong size of received outcome");
+ goto quit;
+ }
+
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ ec_point_parse (gamma, (struct ec_mpi *)cur);
+ ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
+ proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
+ if (smc_zkp_2dle_check (gamma,
+ delta,
+ ad->gamma3[sender][0][j],
+ ad->delta3[sender][0][j],
+ proof2))
+ {
+ weprintf ("wrong zkp2 for gamma, delta received");
+ goto quit;
+ }
+ ec_point_copy (ad->gamma3[sender][0][j], gamma);
+ ec_point_copy (ad->delta3[sender][0][j], delta);
+
+ /* compute winner determination gamma,delta pair */
+ gcry_mpi_ec_add (ad->gamma3[sender][1][j],
+ ad->gamma3[sender][0][j],
+ ad->gamma3[sender][1][j],
+ ec_ctx);
+ gcry_mpi_ec_add (ad->delta3[sender][1][j],
+ ad->delta3[sender][0][j],
+ ad->delta3[sender][1][j],
+ ec_ctx);
+
+ cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
+ }
+
+ ret = 1;
+quit:
+ gcry_mpi_point_release (gamma);
+ gcry_mpi_point_release (delta);
+ return ret;
+}
+
+
+void
+mp_pub_prep_decryption (struct BRANDT_Auction *ad)
+{
+ gcry_mpi_point_t tmp_price = gcry_mpi_point_new (0);
+ gcry_mpi_point_t tmp_winner = gcry_mpi_point_new (0);
+
+ ad->phi3 = smc_init3 (ad->n, 2, ad->k);
+ brandt_assert (ad->phi3);
+
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ smc_sum (tmp_price, &ad->delta3[0][0][j], ad->n, 2 * ad->k);
+ smc_sum (tmp_winner, &ad->delta3[0][1][j], ad->n, 2 * ad->k);
+
+ /* copy still encrypted outcome to all other bidder layers so they
+ * don't have to be recomputed to check the ZK proof_2dle's from
+ * other bidders when receiving their outcome decryption messages */
+ for (uint16_t a = 0; a < ad->n; a++)
+ {
+ ec_point_copy (ad->phi3[a][0][j], tmp_price);
+ ec_point_copy (ad->phi3[a][1][j], tmp_winner);
+ }
+ }
+
+ gcry_mpi_point_release (tmp_price);
+ gcry_mpi_point_release (tmp_winner);
+}
+
+
+/**
+ * mp_pub_decrypt_outcome decrypts part of the outcome and packs it into a
+ * message buffer together with proofs of correctnes.
+ *
+ * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
+ * @param[out] buflen Size of the returned message buffer in bytes
+ * @return A buffer containing the own share of the decrypted outcome
+ * which needs to be broadcast
+ */
+unsigned char *
+mp_pub_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
+{
+ unsigned char *ret;
+ unsigned char *cur;
+ gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
+ struct msg_head *head;
+ struct ec_mpi *phi;
+ struct proof_2dle *proof2;
+
+ brandt_assert (ad && buflen);
+
+ *buflen = (sizeof (*head) + 2 * ad->k * (sizeof (*phi) + sizeof (*proof2)));
+ ret = GNUNET_new_array (*buflen, unsigned char);
+
+ head = (struct msg_head *)ret;
+ head->prot_version = htonl (0);
+ head->msg_type = htonl (msg_decrypt);
+ cur = ret + sizeof (*head);
+
+ /* decrypt price and winner components */
+ for (uint16_t comp = 0; comp < 2; comp++)
+ {
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ phi = (struct ec_mpi *)cur;
+ proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
+
+ ec_point_copy (tmp, ad->phi3[ad->i][comp][j]);
+
+ /* decrypt outcome component and prove the correct key was used */
+ smc_zkp_2dle (ad->phi3[ad->i][comp][j],
+ NULL,
+ tmp,
+ ec_gen,
+ ad->x,
+ proof2);
+
+ ec_point_serialize (phi, ad->phi3[ad->i][comp][j]);
+
+ cur += sizeof (*phi) + sizeof (*proof2);
+ }
+ }
+
+ gcry_mpi_point_release (tmp);
+ return ret;
+}
+
+
+int
+mp_pub_recv_decryption (struct BRANDT_Auction *ad,
+ const unsigned char *buf,
+ size_t buflen,
+ uint16_t sender)
+{
+ int ret = 0;
+ const unsigned char *cur = buf;
+ struct proof_2dle *proof2;
+ gcry_mpi_point_t phi = gcry_mpi_point_new (0);
+
+ brandt_assert (ad && buf);
+
+ if (buflen != (2 * ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
+ {
+ weprintf ("wrong size of received outcome decryption");
+ goto quit;
+ }
+
+ /* handle received price and winner components */
+ for (uint16_t comp = 0; comp < 2; comp++)
+ {
+ for (uint16_t j = 0; j < ad->k; j++)
+ {
+ ec_point_parse (phi, (struct ec_mpi *)cur);
+ proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
+
+ if (smc_zkp_2dle_check (phi,
+ ad->y[sender],
+ ad->phi3[sender][comp][j],
+ ec_gen,
+ proof2))
+ {
+ weprintf ("wrong zkp2 for phi, y received");
+ goto quit;
+ }
+ ec_point_copy (ad->phi3[sender][comp][j], phi);
+ cur += sizeof (struct ec_mpi) + sizeof (*proof2);
+ }
+ }
+
+ ret = 1;
+quit:
+ gcry_mpi_point_release (phi);
+ return ret;
+}
+
+
+struct BRANDT_Result *
+mp_pub_determine_outcome (struct BRANDT_Auction *ad,
+ uint16_t *len)
+{
+ struct BRANDT_Result *ret;
+ int32_t price = -1;
+ uint16_t cur_winner = 0;
+ int dlogi = -1;
+ gcry_mpi_point_t sum_gamma = gcry_mpi_point_new (0);
+ gcry_mpi_point_t sum_phi = gcry_mpi_point_new (0);
+
+ brandt_assert (ad);
+
+ for (uint16_t j = ad->k - 1; j >= 0; j--)
+ {
+ smc_sum (sum_gamma, &ad->gamma3[0][0][j], ad->n, 2 * ad->k);
+ smc_sum (sum_phi, &ad->phi3[0][0][j], ad->n, 2 * ad->k);
+ gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
+ /* first zero component determines the price */
+ if (!ec_point_cmp (sum_gamma, ec_zero))
+ {
+ price = j;
+ break;
+ }
+ }
+
+ if (-1 == price)
+ return NULL;
+
+ /* extract winners point for the winning price */
+ smc_sum (sum_gamma, &ad->gamma3[0][1][price], ad->n, 2 * ad->k);
+ smc_sum (sum_phi, &ad->phi3[0][1][price], ad->n, 2 * ad->k);
+ gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
+
+ dlogi = GNUNET_CRYPTO_ecc_dlog (ec_dlogctx, sum_gamma);
+ brandt_assert (dlogi > 0);
+
+ /* all bidders participated with a multiplicative share */
+ dlogi /= ad->n;
+
+ price = price / ad->n;
+ ret = GNUNET_new_array (ad->m, struct BRANDT_Result);
+
+ /* can only support up to bits(dlogi) bidders */
+ brandt_assert (sizeof (int) * 8 > ad->n);
+ for (uint16_t i = 0; i < ad->n; i++)
+ {
+ /* a set bit determines a winner */
+ if (dlogi & (1 << i))
+ {
+ if (cur_winner >= ad->m)
+ {
+ weprintf ("too many winners detected");
+ GNUNET_free (ret);
+ ret = NULL;
+ goto quit;
+ }
+
+ ret[cur_winner].bidder = i;
+ ret[cur_winner].price = price;
+ ret[cur_winner].status = BRANDT_bidder_won;
+ cur_winner++;
+ }
+ }
+
+ if (cur_winner != ad->m)
+ {
+ weprintf ("too few winners detected");
+ GNUNET_free (ret);
+ ret = NULL;
+ goto quit;
+ }
+
+ if (len)
+ *len = ad->m;
+quit:
+ gcry_mpi_point_release (sum_gamma);
+ gcry_mpi_point_release (sum_phi);
+ return ret;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-09-11 09:50:49 +0000