Add secret sharing

[software/DIPE.git] / src / SS.cxx

diff --git a/src/SS.cxx b/src/SS.cxx
new file mode 100644 (file)
index 0000000..c762e98
--- /dev/null
+++ b/src/SS.cxx
@@ -0,0 +1,161 @@
+#include "DIPE.h"
+#include "DIPE_Internal.h"
+
+#include <assert.h>
+
+namespace {
+       void dipe_ss_esf(dipe_param_t param, size_t size, size_t m, size_t excl, element_t* elements, element_t* result) {
+               assert(size >= m);
+               
+               /* m = n */
+               if (size == m || (m + 1 == size && excl < size)) {
+                       assert((size == m) ? excl > size : true);
+                       element_set1(*result);
+                       for (size_t i = 0; i < size; ++i) {
+                               if (i != excl) {
+                                       element_mul(*result, *result, elements[i]);
+                               }
+                       }
+                       return;
+               }
+               /* m = 1 */
+               if (m == 1) {
+                       element_set0(*result);
+                       for (size_t i = 0; i < size; ++i) {
+                               if (i != excl) {
+                                       element_add(*result, *result, elements[i]);
+                               }
+                       }
+                       return;
+               }
+
+               /* otherwise */
+               element_t lhs;
+               element_init_Zr(lhs, param->pairing);
+               dipe_ss_esf(param, size-1, m, excl, elements, result);
+               dipe_ss_esf(param, size-1, m-1, excl, elements, &lhs);
+               element_mul(lhs, lhs, elements[size-1]);
+               element_add(*result, *result, lhs);
+               element_clear(lhs);
+       }
+
+       
+       /* https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix     
+        * Contract: result is allocated but not initialized size x size array
+        */
+       void dipe_ss_inverse_vandermonde(dipe_param_t param, size_t size, element_t* elements, element_t** result) {
+               /* b_ij = (-1)^{n-i} e_{n-i}() / \Prod ()
+                */
+               element_t numerator, denominator;
+               element_t tmp;
+               element_init_Zr(numerator, param->pairing);
+               element_init_Zr(denominator, param->pairing);
+               element_init_Zr(tmp, param->pairing);
+               
+               for (size_t i = 0; i < size; ++i) {
+                       for (size_t j = 0; j < size; ++j) {
+                               element_init_Zr(result[i][j], param->pairing);
+
+                               /* numerator */
+                               dipe_ss_esf(param, size, size-i, j, elements, &numerator);
+                               if (((size - i) & 1) == 1) {
+                                       element_neg(numerator, numerator);
+                               }
+                               
+                               /* denominator */
+                               element_set1(denominator);
+                               for (size_t k = 0; k < size; ++k) {
+                                       if (k != j) {
+                                               element_sub(tmp, elements[j], elements[k]);
+                                               element_mul(denominator, denominator, tmp);
+                                       }
+                               }
+
+                               element_div(result[i][j], numerator, denominator);
+                       }
+               }
+               element_clear(tmp);
+               element_clear(numerator);
+               element_clear(denominator);
+       }
+}
+
+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,
+                   element_t* secret, element_t** dummy_shares) {
+       element_t tmp;
+       element_t a_pow;
+       element_init_Zr(tmp, param->pairing);
+       element_init_Zr(a_pow, param->pairing);
+
+       /* Precompute V_I^{-1} needed in several steps */
+       element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
+       for (size_t i = 0; i < id_size; ++i) {
+               b[i] = (element_t*)calloc(id_size, sizeof(element_t));
+       }
+       dipe_ss_inverse_vandermonde(param, id_size, ids, b);
+
+       /* Compute Secret */
+       for (size_t k = 0; k < share_size; ++k) {
+               element_set0(secret[k]);
+               for (size_t j = 0; j < id_size; ++j) {
+                       element_mul(tmp, b[0][j], shares[j][k]);
+                       element_add(secret[k], secret[k], tmp);
+               }
+       }
+
+       /* Compute Dummy Shares */
+       /* Matrix Product */
+       element_t** ab = (element_t**)calloc(id_size, sizeof(element_t*));
+       for (size_t i = 0; i < fid_size; ++i) {
+               ab[i] = (element_t*)calloc(id_size, sizeof(element_t));
+               
+               for (size_t j = 0; j < id_size; ++j) {
+                       element_init_Zr(ab[i][j], param->pairing);
+                       element_set0(ab[i][j]);
+                       element_set1(a_pow);
+                       
+                       for (size_t k = 0; k < id_size; ++ k) {
+                               element_mul(tmp, a_pow, b[k][j]);
+                               element_add(ab[i][j], ab[i][j], tmp);
+                               element_mul(a_pow, a_pow, fake_ids[i]);
+                       }
+               }
+       }
+
+       /* Matrix Product */
+       for (size_t i = 0; i < fid_size; ++ i) {
+               for (size_t j = 0; j < share_size; ++j) {
+                       element_init_Zr(dummy_shares[i][j], param->pairing);
+                       element_set0(dummy_shares[i][j]);
+                       for (size_t k = 0; k < id_size; ++k) {
+                               element_mul(tmp, ab[i][k], shares[j][k]);
+                               element_add(dummy_shares[i][j], dummy_shares[i][j], tmp);
+                       }
+               }
+       }
+
+       /* TODO: cleanup */
+}
+
+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) {
+       element_t tmp;
+       /* TODO: fix type, shares are in G_t here~ */
+       element_init_Zr(tmp, param->pairing);
+
+       /* Precompute V_I^{-1} needed in several steps */
+       /* Actually for recover we only need the values b[0][j] */
+       element_t** b = (element_t**)calloc(id_size, sizeof(element_t*));
+       for (size_t i = 0; i < id_size; ++i) {
+               b[i] = (element_t*)calloc(id_size, sizeof(element_t));
+       }
+       dipe_ss_inverse_vandermonde(param, id_size, ids, b);
+
+       /* Compute Secret */
+       for (size_t k = 0; k < share_size; ++k) {
+               element_set0(secret[k]);
+               for (size_t j = 0; j < id_size; ++j) {
+                       element_mul(tmp, b[0][j], shares[j][k]);
+                       element_add(secret[k], secret[k], tmp);
+               }
+       }
+}