Add secret sharing

diff --git a/include/DIPE.h b/include/DIPE.h
index 70d70b82de42a0142b4412902d4851d03c23e99e..b9889afe33b94dce902315935e2f2c62761eae07 100644 (file)
--- a/include/DIPE.h
+++ b/include/DIPE.h
@@ -21,6 +21,10 @@ extern "C" {
        void dipe_encap(dipe_param_t param, dipe_master_publickey_t mpk, element_t* x, element_t ptxt, dipe_ctxt_t* ctxt);
        void dipe_decap(dipe_param_t param, dipe_secretkey_t sk, char* cid, element_t* y, dipe_ctxt_t ctxt, element_t ptxt);
 
+       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);
+       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);
+
        size_t dipe_serialize_ctxt(dipe_param_t param, dipe_ctxt_t ctxt, uint8_t* buffer);
        size_t dipe_deserialize_ctxt(dipe_param_t param, size_t dimension, dipe_ctxt_t* ctxt, uint8_t* buffer);
        

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 7379e31741d5762936b5716736855e912d4b8265..efe49f4e2a48886ff722bdcf1ba0b9d1a64d2c01 100644 (file)
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -1,5 +1,6 @@
 option(BUILD_SHARED_LIBS "Build using shared libraries" ON)
-add_library (DIPE DIPE.cxx)
+
+add_library (DIPE DIPE.cxx SS.cxx)
 
 add_definitions(-Wall -Wextra -Werror)
 

diff --git a/src/DIPE.cxx b/src/DIPE.cxx
index e06f2f3b4b95eeba42176062f70aa74c1b892fa9..9b8c91ec52c9f8495aa8f178072fd672674e9ec0 100644 (file)
--- a/src/DIPE.cxx
+++ b/src/DIPE.cxx
@@ -1,4 +1,5 @@
 #include "DIPE.h"
+#include "DIPE_Internal.h"
 
 #include <string.h>
 #include <nettle/hkdf.h>
@@ -13,36 +14,6 @@
 using std::min;
 using std::max;
 
-struct dipe_param {
-       pairing_t pairing;
-       element_t g1;
-       element_t g2;
-       element_t gt;
-};
-
-struct dipe_master_publickey {
-       size_t dimension;
-       element_t a;
-       element_t* k;
-};
-
-struct dipe_master_secretkey {
-       size_t dimension;
-       element_t a;
-       element_t* k;
-};
-
-struct dipe_secretkey {
-       size_t dimension;
-       element_t d;
-};
-
-struct dipe_ctxt {
-       size_t dimension;
-       element_t s;
-       element_t* cx;
-       element_t c;
-};
 
 
 namespace {

diff --git a/src/DIPE_Internal.h b/src/DIPE_Internal.h
new file mode 100644 (file)
index 0000000..521c2d6
--- /dev/null
+++ b/src/DIPE_Internal.h
@@ -0,0 +1,30 @@
+struct dipe_param {
+       pairing_t pairing;
+       element_t g1;
+       element_t g2;
+       element_t gt;
+};
+
+struct dipe_master_publickey {
+       size_t dimension;
+       element_t a;
+       element_t* k;
+};
+
+struct dipe_master_secretkey {
+       size_t dimension;
+       element_t a;
+       element_t* k;
+};
+
+struct dipe_secretkey {
+       size_t dimension;
+       element_t d;
+};
+
+struct dipe_ctxt {
+       size_t dimension;
+       element_t s;
+       element_t* cx;
+       element_t c;
+};

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);
+               }
+       }
+}