From 27e33ae5bcd5b172f2f8311bed4e1300ba5697cc Mon Sep 17 00:00:00 2001 From: Christoph Egger Date: Wed, 15 Jan 2020 15:11:59 +0100 Subject: [PATCH] Add secret sharing --- include/DIPE.h | 4 ++ src/CMakeLists.txt | 3 +- src/DIPE.cxx | 31 +-------- src/DIPE_Internal.h | 30 +++++++++ src/SS.cxx | 161 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 198 insertions(+), 31 deletions(-) create mode 100644 src/DIPE_Internal.h create mode 100644 src/SS.cxx diff --git a/include/DIPE.h b/include/DIPE.h index 70d70b8..b9889af 100644 --- 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 7379e31..efe49f4 100644 --- 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 e06f2f3..9b8c91e 100644 --- a/src/DIPE.cxx +++ b/src/DIPE.cxx @@ -1,4 +1,5 @@ #include "DIPE.h" +#include "DIPE_Internal.h" #include #include @@ -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 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 index 0000000..c762e98 --- /dev/null +++ b/src/SS.cxx @@ -0,0 +1,161 @@ +#include "DIPE.h" +#include "DIPE_Internal.h" + +#include + +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); + } + } +} -- 2.39.2