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, 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                         for (size_t j = 0; j < size; ++j) {
  62                                 element_init_Zr(result[i][j], param->pairing);
  63
  64                                 /* numerator */
  65                                 dipe_ss_esf(param, size, size-i-1, j, elements, &numerator);
  66                                 if (((size - i-1) & 1) == 1) {
  67                                         element_neg(numerator, numerator);
  68                                 }
  69
  70                                 /* denominator */
  71                                 element_set1(denominator);
  72                                 for (size_t k = 0; k < size; ++k) {
  73                                         if (k != j) {
  74                                                 element_sub(tmp, elements[j], elements[k]);
  75                                                 element_mul(denominator, denominator, tmp);
  76                                         }
  77                                 }
  78
  79                                 element_div(result[i][j], numerator, denominator);
  80                         }
  81                 }
  82                 element_clear(tmp);
  83                 element_clear(numerator);
  84                 element_clear(denominator);
  85         }
  86 }
  87
  88 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,
  89                    element_t* secret, element_t** dummy_shares) {
  90         element_t tmp;
  91         element_t tmpz;
  92         element_t a_pow;
  93         element_init_same_as(tmp, shares[0][0]);
  94         element_init_Zr(tmpz, param->pairing);
  95         element_init_Zr(a_pow, param->pairing);
  96
  97         /* Precompute V_I^{-1} needed in several steps */
  98         element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
  99         for (size_t i = 0; i < id_size; ++i) {
 100                 b[i] = (element_t*)calloc(id_size, sizeof(element_t));
 101         }
 102         dipe_ss_inverse_vandermonde(param, id_size, ids, b);
 103
 104         /* Compute Secret */
 105         for (size_t k = 0; k < share_size; ++k) {
 106                 element_set1(secret[k]);
 107                 for (size_t j = 0; j < id_size; ++j) {
 108                         element_pow_zn(tmp, shares[j][k], b[0][j]);
 109                         element_mul(secret[k], secret[k], tmp);
 110                 }
 111         }
 112
 113         /* Compute Dummy Shares */
 114         /* Matrix Product */
 115         element_t** ab = (element_t**)calloc(id_size, sizeof(element_t*));
 116         for (size_t i = 0; i < fid_size; ++i) {
 117                 ab[i] = (element_t*)calloc(id_size, sizeof(element_t));
 118
 119                 for (size_t j = 0; j < id_size; ++j) {
 120                         element_init_Zr(ab[i][j], param->pairing);
 121                         element_set0(ab[i][j]);
 122                         element_set1(a_pow);
 123
 124                         for (size_t k = 0; k < id_size; ++ k) {
 125                                 element_mul(tmpz, a_pow, b[k][j]);
 126                                 element_add(ab[i][j], ab[i][j], tmpz);
 127                                 element_mul(a_pow, a_pow, fake_ids[i]);
 128                         }
 129                 }
 130         }
 131
 132         /* Matrix Product. Note this is an abuse of notation and we're doing scalar * group in additive writing */
 133         for (size_t i = 0; i < fid_size; ++ i) {
 134                 for (size_t j = 0; j < share_size; ++j) {
 135                         element_init_same_as(dummy_shares[i][j], shares[0][0]);
 136                         element_set1(dummy_shares[i][j]);
 137                         for (size_t k = 0; k < id_size; ++k) {
 138                                 element_pow_zn(tmp, shares[k][j], ab[i][k]);
 139                                 element_mul(dummy_shares[i][j], dummy_shares[i][j], tmp);
 140                         }
 141                 }
 142         }
 143
 144         for (size_t i = 0; i < id_size; ++i) {
 145                 for (size_t j = 0; j < id_size; ++j) {
 146                         element_clear(b[i][j]);
 147                 }
 148                 free(b[i]);
 149         }
 150         free(b);
 151
 152         for (size_t i = 0; i < fid_size; ++i) {
 153                 for (size_t j = 0; j < id_size; ++j) {
 154                         element_clear(ab[i][j]);
 155                 }
 156                 free(ab[i]);
 157         }
 158         free(ab);
 159         element_clear(tmp);
 160         element_clear(tmpz);
 161         element_clear(a_pow);
 162 }
 163
 164 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) {
 165         element_t tmp;
 166         /* TODO: fix type, shares are in G_t here~ */
 167         element_init_same_as(tmp, shares[0][0]);
 168
 169         /* Precompute V_I^{-1} needed in several steps */
 170         /* Actually for recover we only need the values b[0][j] */
 171         element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
 172         for (size_t i = 0; i < id_size; ++i) {
 173                 b[i] = (element_t*)calloc(id_size, sizeof(element_t));
 174         }
 175         dipe_ss_inverse_vandermonde(param, id_size, ids, b);
 176
 177         /* Compute Secret */
 178         for (size_t k = 0; k < share_size; ++k) {
 179                 element_set1(secret[k]);
 180                 for (size_t j = 0; j < id_size; ++j) {
 181                         element_pow_zn(tmp, shares[j][k], b[0][j]);
 182                         element_mul(secret[k], secret[k], tmp);
 183                 }
 184         }
 185
 186         for (size_t i = 0; i < id_size; ++i) {
 187                 for (size_t j = 0; j < id_size; ++j) {
 188                         element_clear(b[i][j]);
 189                 }
 190                 free(b[i]);
 191         }
 192         free(b);
 193         element_clear(tmp);
 194 }