changeset 1560:9d183f681a7c

BeDOZa: Precompute paillier modulus and reduce in each step.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Tue, 28 Sep 2010 15:47:40 +0200
parents 18b3699be9db
children 0e4476f175bb
files viff/bedoza/zero_knowledge.py viff/test/bedoza/test_zero_knowledge.py
diffstat 2 files changed, 18 insertions(+), 11 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza/zero_knowledge.py	Tue Sep 28 15:14:06 2010 +0200
+++ b/viff/bedoza/zero_knowledge.py	Tue Sep 28 15:47:40 2010 +0200
@@ -54,7 +54,10 @@
         self.c = c
         self.paillier = paillier
         self.random = random
+        self.prover_n = mpz(self.runtime.players[self.prover_id].pubkey['n'])
 
+        # TODO: Use the n**2 already in the pubkey.
+        self.prover_n2 = self.prover_n**2
 
     def start(self):
         """Executes this zero-knowledge proof.
@@ -86,11 +89,11 @@
             #print 'e', len(self.e)
             #print 'u', len(self.u)
             return True # TODO
-        n = self.runtime.players[self.prover_id].pubkey['n']
+        #n = self.runtime.players[self.prover_id].pubkey['n']
         #print "N_1:", n
         self._deserialize_proof(serialized_proof)
         self._generate_e()
-        S = self._vec_mul(self.d, self._vec_pow_E(self.c))
+        S = self._vec_mul(self.d, self._vec_pow_E(self.c, self.prover_n2))
         T = [mpz(self.paillier.encrypt(int(self.Z[j]), player_id=self.prover_id, random_elm=int(self.W[j])))
              for j in range(self.m)]
         #print 'Z', len(self.Z)
@@ -99,7 +102,7 @@
         for j in xrange(self.m):
             #print
             #print '---'
-            #print self.runtime.id, j, S[j] % n**2
+            #print self.runtime.id, j, S[j] % self.prover_n2
             #print self.runtime.id, j, T[j]
             # TODO: Return false if S[j] != T[j].
             if S[j] != T[j]:
@@ -126,13 +129,13 @@
 
     def _generate_Z_and_W(self):
         self.Z = self._vec_add(self.u, self._vec_mul_E(self.x))
-        self.W = self._vec_mul(self.v, self._vec_pow_E(self.r))
+        self.W = self._vec_mul(self.v, self._vec_pow_E(self.r, self.prover_n))
 
         #print self.runtime.id
         #print self.prover_id
-        n = self.runtime.players[self.prover_id].pubkey['n']
+        #n = self.runtime.players[self.prover_id].pubkey['n']
         #print "N_1:", n
-        self.W = [w % n**2 for w in self.W]
+        self.W = [w % self.prover_n2 for w in self.W]
 
         #print "Player", self.runtime.id, " Z =", self.Z
         #print "Player", self.runtime.id, " W =", self.W
@@ -239,7 +242,7 @@
     def _vec_mul(self, x, y):
         return [x * y for x, y in zip(x,y)]
 
-    def _vec_pow_E(self, y):
+    def _vec_pow_E(self, y, n):
         """Computes and returns the m := 2s-1 length vector y**E."""
         assert self.s == len(y), \
             "not same length: %d != %d" % (self.s, len(y))
@@ -247,5 +250,6 @@
         for j in range(self.m):
             for i in range(self.s):
                 if self._E(j, i) == mpz(1):
-                    res[j] *= y[i]
+                    # TODO: Should we reduce modulo n each time?
+                    res[j] = (res[j] * y[i]) % n
         return res
--- a/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 15:14:06 2010 +0200
+++ b/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 15:47:40 2010 +0200
@@ -30,8 +30,11 @@
 from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
 
 
+class StubPlayer(object):
+    pubkey = {'n': 123}
+
 class RuntimeStub(object):
-    def __init__(self, players=[1, 2, 3], id=1):
+    def __init__(self, players={1: StubPlayer(), 2: StubPlayer(), 3: StubPlayer()}, id=1):
         self.players = players
         self.id = id
 
@@ -57,7 +60,7 @@
         y = [mpz(i) for i in range(1, 6)]
         zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [1, 0, 1, 1, 0]
-        y_pow_E = zk._vec_pow_E(y)
+        y_pow_E = zk._vec_pow_E(y, 117)
         self.assertEquals([mpz(v) for v in [1, 2, 3, 8, 30, 12, 20, 5, 1]],
                           y_pow_E)
 
@@ -67,7 +70,7 @@
         y = [mpz(i) for i in [1, 7, 2]]
         zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [0, 1, 1]
-        y_pow_E = zk._vec_pow_E(y)
+        y_pow_E = zk._vec_pow_E(y, 117)
         self.assertEquals([mpz(v) for v in [1, 1, 7, 14, 2]], y_pow_E)
 
     def test_vec_mul_E_is_correct(self):