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                 /* m = n */
  11                 if (size == m || (m + 1 == size && excl < size)) {
  12                         assert((size == m) ? excl > size : true);
  13                         element_set1(*result);
  14                         for (size_t i = 0; i < size; ++i) {
  15                                 if (i != excl) {
  16                                         element_mul(*result, *result, elements[i]);
  17                                 }
  18                         }
  19                         return;
  20                 }
  21                 /* m = 1 */
  22                 if (m == 1) {
  23                         element_set0(*result);
  24                         for (size_t i = 0; i < size; ++i) {
  25                                 if (i != excl) {
  26                                         element_add(*result, *result, elements[i]);
  27                                 }
  28                         }
  29                         return;
  30                 }
  31
  32                 /* otherwise */
  33                 element_t lhs;
  34                 element_init_Zr(lhs, param->pairing);
  35                 dipe_ss_esf(param, size-1, m, excl, elements, result);
  36                 dipe_ss_esf(param, size-1, m-1, excl, elements, &lhs);
  37                 element_mul(lhs, lhs, elements[size-1]);
  38                 element_add(*result, *result, lhs);
  39                 element_clear(lhs);
  40         }
  41
  42
  43         /* https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix
  44          * Contract: result is allocated but not initialized size x size array
  45          */
  46         void dipe_ss_inverse_vandermonde(dipe_param_t param, size_t size, element_t* elements, element_t** result) {
  47                 /* b_ij = (-1)^{n-i} e_{n-i}() / \Prod ()
  48                  */
  49                 element_t numerator, denominator;
  50                 element_t tmp;
  51                 element_init_Zr(numerator, param->pairing);
  52                 element_init_Zr(denominator, param->pairing);
  53                 element_init_Zr(tmp, param->pairing);
  54
  55                 for (size_t i = 0; i < size; ++i) {
  56                         for (size_t j = 0; j < size; ++j) {
  57                                 element_init_Zr(result[i][j], param->pairing);
  58
  59                                 /* numerator */
  60                                 dipe_ss_esf(param, size, size-i, j, elements, &numerator);
  61                                 if (((size - i) & 1) == 1) {
  62                                         element_neg(numerator, numerator);
  63                                 }
  64
  65                                 /* denominator */
  66                                 element_set1(denominator);
  67                                 for (size_t k = 0; k < size; ++k) {
  68                                         if (k != j) {
  69                                                 element_sub(tmp, elements[j], elements[k]);
  70                                                 element_mul(denominator, denominator, tmp);
  71                                         }
  72                                 }
  73
  74                                 element_div(result[i][j], numerator, denominator);
  75                         }
  76                 }
  77                 element_clear(tmp);
  78                 element_clear(numerator);
  79                 element_clear(denominator);
  80         }
  81 }
  82
  83 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,
  84                    element_t* secret, element_t** dummy_shares) {
  85         element_t tmp;
  86         element_t a_pow;
  87         element_init_Zr(tmp, param->pairing);
  88         element_init_Zr(a_pow, param->pairing);
  89
  90         /* Precompute V_I^{-1} needed in several steps */
  91         element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
  92         for (size_t i = 0; i < id_size; ++i) {
  93                 b[i] = (element_t*)calloc(id_size, sizeof(element_t));
  94         }
  95         dipe_ss_inverse_vandermonde(param, id_size, ids, b);
  96
  97         /* Compute Secret */
  98         for (size_t k = 0; k < share_size; ++k) {
  99                 element_set0(secret[k]);
 100                 for (size_t j = 0; j < id_size; ++j) {
 101                         element_mul(tmp, b[0][j], shares[j][k]);
 102                         element_add(secret[k], secret[k], tmp);
 103                 }
 104         }
 105
 106         /* Compute Dummy Shares */
 107         /* Matrix Product */
 108         element_t** ab = (element_t**)calloc(id_size, sizeof(element_t*));
 109         for (size_t i = 0; i < fid_size; ++i) {
 110                 ab[i] = (element_t*)calloc(id_size, sizeof(element_t));
 111
 112                 for (size_t j = 0; j < id_size; ++j) {
 113                         element_init_Zr(ab[i][j], param->pairing);
 114                         element_set0(ab[i][j]);
 115                         element_set1(a_pow);
 116
 117                         for (size_t k = 0; k < id_size; ++ k) {
 118                                 element_mul(tmp, a_pow, b[k][j]);
 119                                 element_add(ab[i][j], ab[i][j], tmp);
 120                                 element_mul(a_pow, a_pow, fake_ids[i]);
 121                         }
 122                 }
 123         }
 124
 125         /* Matrix Product */
 126         for (size_t i = 0; i < fid_size; ++ i) {
 127                 for (size_t j = 0; j < share_size; ++j) {
 128                         element_init_Zr(dummy_shares[i][j], param->pairing);
 129                         element_set0(dummy_shares[i][j]);
 130                         for (size_t k = 0; k < id_size; ++k) {
 131                                 element_mul(tmp, ab[i][k], shares[j][k]);
 132                                 element_add(dummy_shares[i][j], dummy_shares[i][j], tmp);
 133                         }
 134                 }
 135         }
 136
 137         /* TODO: cleanup */
 138 }
 139
 140 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) {
 141         element_t tmp;
 142         /* TODO: fix type, shares are in G_t here~ */
 143         element_init_Zr(tmp, param->pairing);
 144
 145         /* Precompute V_I^{-1} needed in several steps */
 146         /* Actually for recover we only need the values b[0][j] */
 147         element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
 148         for (size_t i = 0; i < id_size; ++i) {
 149                 b[i] = (element_t*)calloc(id_size, sizeof(element_t));
 150         }
 151         dipe_ss_inverse_vandermonde(param, id_size, ids, b);
 152
 153         /* Compute Secret */
 154         for (size_t k = 0; k < share_size; ++k) {
 155                 element_set0(secret[k]);
 156                 for (size_t j = 0; j < id_size; ++j) {
 157                         element_mul(tmp, b[0][j], shares[j][k]);
 158                         element_add(secret[k], secret[k], tmp);
 159                 }
 160         }
 161 }