optimize

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

diff --git a/src/SS.cxx b/src/SS.cxx
index c762e988b1e26a2314fa6357d0397dff0f9dd827..426072b18aa21403aaa0f7e4d5dff124b6b9fc50 100644 (file)
--- a/src/SS.cxx
+++ b/src/SS.cxx
@@ -6,9 +6,14 @@
 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);
+
+               if (m == 0) {
+                       element_set1(*result);
+                       return;
+               }
                
                /* m = n */
-               if (size == m || (m + 1 == size && excl < size)) {
+               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) {
@@ -43,7 +48,7 @@ namespace {
        /* 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) {
+       void dipe_ss_inverse_vandermonde(dipe_param_t param, bool flat, size_t size, element_t* elements, element_t** result) {
                /* b_ij = (-1)^{n-i} e_{n-i}() / \Prod ()
                 */
                element_t numerator, denominator;
@@ -53,12 +58,14 @@ namespace {
                element_init_Zr(tmp, param->pairing);
                
                for (size_t i = 0; i < size; ++i) {
+                       if (flat && i > 0) continue;
+                       
                        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) {
+                               dipe_ss_esf(param, size, size-i-1, j, elements, &numerator);
+                               if (((size - i-1) & 1) == 1) {
                                        element_neg(numerator, numerator);
                                }
                                
@@ -83,8 +90,10 @@ namespace {
 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 tmpz;
        element_t a_pow;
-       element_init_Zr(tmp, param->pairing);
+       element_init_same_as(tmp, shares[0][0]);
+       element_init_Zr(tmpz, param->pairing);
        element_init_Zr(a_pow, param->pairing);
 
        /* Precompute V_I^{-1} needed in several steps */
@@ -92,14 +101,14 @@ void dipe_ss_share(dipe_param_t param, size_t id_size, element_t* ids, size_t fi
        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);
+       dipe_ss_inverse_vandermonde(param, false, id_size, ids, b);
 
        /* Compute Secret */
        for (size_t k = 0; k < share_size; ++k) {
-               element_set0(secret[k]);
+               element_set1(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);
+                       element_pow_zn(tmp, shares[j][k], b[0][j]);
+                       element_mul(secret[k], secret[k], tmp);
                }
        }
 
@@ -115,47 +124,69 @@ void dipe_ss_share(dipe_param_t param, size_t id_size, element_t* ids, size_t fi
                        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(tmpz, a_pow, b[k][j]);
+                               element_add(ab[i][j], ab[i][j], tmpz);
                                element_mul(a_pow, a_pow, fake_ids[i]);
                        }
                }
        }
 
-       /* Matrix Product */
+       /* Matrix Product. Note this is an abuse of notation and we're doing scalar * group in additive writing */
        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]);
+                       element_init_same_as(dummy_shares[i][j], shares[0][0]);
+                       element_set1(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);
+                               element_pow_zn(tmp, shares[k][j], ab[i][k]);
+                               element_mul(dummy_shares[i][j], dummy_shares[i][j], tmp);
                        }
                }
        }
 
-       /* TODO: cleanup */
+       for (size_t i = 0; i < id_size; ++i) {
+               for (size_t j = 0; j < id_size; ++j) {
+                       element_clear(b[i][j]);
+               }
+               free(b[i]);
+       }
+       free(b);
+
+       for (size_t i = 0; i < fid_size; ++i) {
+               for (size_t j = 0; j < id_size; ++j) {
+                       element_clear(ab[i][j]);
+               }
+               free(ab[i]);
+       }
+       free(ab);
+       element_clear(tmp);
+       element_clear(tmpz);
+       element_clear(a_pow);
 }
 
 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);
+       element_init_same_as(tmp, shares[0][0]);
 
        /* 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);
+       element_t** b = (element_t**)calloc(1, sizeof(element_t*));
+       b[0] = (element_t*)calloc(id_size, sizeof(element_t));
+       dipe_ss_inverse_vandermonde(param, true, id_size, ids, b);
 
        /* Compute Secret */
        for (size_t k = 0; k < share_size; ++k) {
-               element_set0(secret[k]);
+               element_set1(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);
+                       element_pow_zn(tmp, shares[j][k], b[0][j]);
+                       element_mul(secret[k], secret[k], tmp);
                }
        }
+
+       for (size_t j = 0; j < id_size; ++j) {
+               element_clear(b[0][j]);
+       }
+       free(b[0]);
+       free(b);
+       element_clear(tmp);
 }