viff

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 diff
     1.1 --- a/viff/bedoza/zero_knowledge.py	Tue Sep 28 15:14:06 2010 +0200
     1.2 +++ b/viff/bedoza/zero_knowledge.py	Tue Sep 28 15:47:40 2010 +0200
     1.3 @@ -54,7 +54,10 @@
     1.4          self.c = c
     1.5          self.paillier = paillier
     1.6          self.random = random
     1.7 +        self.prover_n = mpz(self.runtime.players[self.prover_id].pubkey['n'])
     1.8  
     1.9 +        # TODO: Use the n**2 already in the pubkey.
    1.10 +        self.prover_n2 = self.prover_n**2
    1.11  
    1.12      def start(self):
    1.13          """Executes this zero-knowledge proof.
    1.14 @@ -86,11 +89,11 @@
    1.15              #print 'e', len(self.e)
    1.16              #print 'u', len(self.u)
    1.17              return True # TODO
    1.18 -        n = self.runtime.players[self.prover_id].pubkey['n']
    1.19 +        #n = self.runtime.players[self.prover_id].pubkey['n']
    1.20          #print "N_1:", n
    1.21          self._deserialize_proof(serialized_proof)
    1.22          self._generate_e()
    1.23 -        S = self._vec_mul(self.d, self._vec_pow_E(self.c))
    1.24 +        S = self._vec_mul(self.d, self._vec_pow_E(self.c, self.prover_n2))
    1.25          T = [mpz(self.paillier.encrypt(int(self.Z[j]), player_id=self.prover_id, random_elm=int(self.W[j])))
    1.26               for j in range(self.m)]
    1.27          #print 'Z', len(self.Z)
    1.28 @@ -99,7 +102,7 @@
    1.29          for j in xrange(self.m):
    1.30              #print
    1.31              #print '---'
    1.32 -            #print self.runtime.id, j, S[j] % n**2
    1.33 +            #print self.runtime.id, j, S[j] % self.prover_n2
    1.34              #print self.runtime.id, j, T[j]
    1.35              # TODO: Return false if S[j] != T[j].
    1.36              if S[j] != T[j]:
    1.37 @@ -126,13 +129,13 @@
    1.38  
    1.39      def _generate_Z_and_W(self):
    1.40          self.Z = self._vec_add(self.u, self._vec_mul_E(self.x))
    1.41 -        self.W = self._vec_mul(self.v, self._vec_pow_E(self.r))
    1.42 +        self.W = self._vec_mul(self.v, self._vec_pow_E(self.r, self.prover_n))
    1.43  
    1.44          #print self.runtime.id
    1.45          #print self.prover_id
    1.46 -        n = self.runtime.players[self.prover_id].pubkey['n']
    1.47 +        #n = self.runtime.players[self.prover_id].pubkey['n']
    1.48          #print "N_1:", n
    1.49 -        self.W = [w % n**2 for w in self.W]
    1.50 +        self.W = [w % self.prover_n2 for w in self.W]
    1.51  
    1.52          #print "Player", self.runtime.id, " Z =", self.Z
    1.53          #print "Player", self.runtime.id, " W =", self.W
    1.54 @@ -239,7 +242,7 @@
    1.55      def _vec_mul(self, x, y):
    1.56          return [x * y for x, y in zip(x,y)]
    1.57  
    1.58 -    def _vec_pow_E(self, y):
    1.59 +    def _vec_pow_E(self, y, n):
    1.60          """Computes and returns the m := 2s-1 length vector y**E."""
    1.61          assert self.s == len(y), \
    1.62              "not same length: %d != %d" % (self.s, len(y))
    1.63 @@ -247,5 +250,6 @@
    1.64          for j in range(self.m):
    1.65              for i in range(self.s):
    1.66                  if self._E(j, i) == mpz(1):
    1.67 -                    res[j] *= y[i]
    1.68 +                    # TODO: Should we reduce modulo n each time?
    1.69 +                    res[j] = (res[j] * y[i]) % n
    1.70          return res
     2.1 --- a/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 15:14:06 2010 +0200
     2.2 +++ b/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 15:47:40 2010 +0200
     2.3 @@ -30,8 +30,11 @@
     2.4  from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
     2.5  
     2.6  
     2.7 +class StubPlayer(object):
     2.8 +    pubkey = {'n': 123}
     2.9 +
    2.10  class RuntimeStub(object):
    2.11 -    def __init__(self, players=[1, 2, 3], id=1):
    2.12 +    def __init__(self, players={1: StubPlayer(), 2: StubPlayer(), 3: StubPlayer()}, id=1):
    2.13          self.players = players
    2.14          self.id = id
    2.15  
    2.16 @@ -57,7 +60,7 @@
    2.17          y = [mpz(i) for i in range(1, 6)]
    2.18          zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.19          zk.e = [1, 0, 1, 1, 0]
    2.20 -        y_pow_E = zk._vec_pow_E(y)
    2.21 +        y_pow_E = zk._vec_pow_E(y, 117)
    2.22          self.assertEquals([mpz(v) for v in [1, 2, 3, 8, 30, 12, 20, 5, 1]],
    2.23                            y_pow_E)
    2.24  
    2.25 @@ -67,7 +70,7 @@
    2.26          y = [mpz(i) for i in [1, 7, 2]]
    2.27          zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.28          zk.e = [0, 1, 1]
    2.29 -        y_pow_E = zk._vec_pow_E(y)
    2.30 +        y_pow_E = zk._vec_pow_E(y, 117)
    2.31          self.assertEquals([mpz(v) for v in [1, 1, 7, 14, 2]], y_pow_E)
    2.32  
    2.33      def test_vec_mul_E_is_correct(self):