viff

changeset 1557:cc989536bad7

BeDOZa: Cleaned up zero-knowledge test cases.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Tue, 28 Sep 2010 14:33:35 +0200
parents 698be97cc543
children 91f2daeb15a5
files viff/bedoza/zero_knowledge.py viff/test/bedoza/test_zero_knowledge.py viff/test/bedoza/util.py
diffstat 3 files changed, 69 insertions(+), 44 deletions(-) [+]
line diff
     1.1 --- a/viff/bedoza/zero_knowledge.py	Tue Sep 28 11:57:48 2010 +0200
     1.2 +++ b/viff/bedoza/zero_knowledge.py	Tue Sep 28 14:33:35 2010 +0200
     1.3 @@ -28,12 +28,9 @@
     1.4      inputs s ciphertexts c[i] = E(x[j], r[j]), i = 1, ..., s, created
     1.5      using the modified Paillier cipher and proves to the other players
     1.6      that the x[i]'s are of limited size, e.g. that abs(x[i]) <= 2**k.
     1.7 -    
     1.8 -    Zn is the plaintext field of player prover_id's modified Paillier
     1.9 -    cipher.
    1.10      """
    1.11      
    1.12 -    def __init__(self, s, prover_id, Zn, k, runtime, c, random=None, paillier=None, x=None, r=None):
    1.13 +    def __init__(self, s, prover_id, k, runtime, c, random=None, paillier=None, x=None, r=None):
    1.14          """
    1.15          random: a random source (e.g. viff.util.Random)
    1.16  
    1.17 @@ -43,12 +40,14 @@
    1.18          """
    1.19          assert len(c) == s
    1.20          assert prover_id in runtime.players
    1.21 +        if x != None:
    1.22 +            for xi in x:
    1.23 +                assert abs(xi) <= 2**k
    1.24          self.x = x
    1.25          self.r = r
    1.26          self.s = s
    1.27          self.m = 2 * s - 1
    1.28          self.prover_id = prover_id
    1.29 -        self.Zn = Zn
    1.30          self.k = k
    1.31          self.runtime = runtime
    1.32          self.c = c
    1.33 @@ -56,7 +55,6 @@
    1.34          self.random = random
    1.35  
    1.36  
    1.37 -
    1.38      def start(self):
    1.39          """Executes this zero-knowledge proof.
    1.40  
    1.41 @@ -87,21 +85,24 @@
    1.42              #print 'e', len(self.e)
    1.43              #print 'u', len(self.u)
    1.44              return True # TODO
    1.45 +        n = self.runtime.players[self.prover_id].pubkey['n']
    1.46 +        #print "N_1:", n
    1.47          self._deserialize_proof(serialized_proof)
    1.48          self._generate_e()
    1.49          S = self._vec_mul(self.d, self._vec_pow_E(self.c))
    1.50 -        T = [self.paillier.encrypt(self.Z[j], player_id=self.prover_id, random_elm=self.W[j]) for j in range(self.m)]
    1.51 +        T = [self.paillier.encrypt(self.Z[j], player_id=self.prover_id, random_elm=self.W[j])
    1.52 +             for j in range(self.m)]
    1.53          #print 'Z', len(self.Z)
    1.54          #print 'W', len(self.W)
    1.55          
    1.56          for j in xrange(self.m):
    1.57 -            n = self.runtime.players[self.prover_id].pubkey['n']
    1.58 -            print
    1.59 -            print '---'
    1.60 -            print self.runtime.id, j, S[j] % n
    1.61 -            print self.runtime.id, j, T[j] % n
    1.62 -
    1.63 -            # TODO: Verify!
    1.64 +            #print
    1.65 +            #print '---'
    1.66 +            #print self.runtime.id, j, S[j] % n**2
    1.67 +            #print self.runtime.id, j, T[j]
    1.68 +            # TODO: Return false if S[j] != T[j].
    1.69 +            if abs(self.Z[j]) > 2**(2 * self.k):
    1.70 +                print "WOOOOOOOOOOPS, PROOF NOT ACCEPTED"
    1.71  
    1.72  
    1.73      def _generate_u_v_and_d(self):
    1.74 @@ -109,6 +110,7 @@
    1.75          for i in range(self.m):
    1.76              ui = rand_int_signed(self.random, 2**(2 * self.k))
    1.77              vi, di = self.paillier.encrypt_r(ui)
    1.78 +            assert abs(ui) <= 2**(2 * self.k)
    1.79              self.u.append(ui)
    1.80              self.v.append(vi)
    1.81              self.d.append(di)
    1.82 @@ -118,6 +120,13 @@
    1.83      def _generate_Z_and_W(self):
    1.84          self.Z = self._vec_add(self.u, self._vec_mul_E(self.x))
    1.85          self.W = self._vec_mul(self.v, self._vec_pow_E(self.r))
    1.86 +
    1.87 +        #print self.runtime.id
    1.88 +        #print self.prover_id
    1.89 +        n = self.runtime.players[self.prover_id].pubkey['n']
    1.90 +        #print "N_1:", n
    1.91 +        self.W = [w % n**2 for w in self.W]
    1.92 +
    1.93          #print "Player", self.runtime.id, " Z =", self.Z
    1.94          #print "Player", self.runtime.id, " W =", self.W
    1.95  
    1.96 @@ -181,7 +190,7 @@
    1.97              h.update(repr(d))
    1.98          hash = h.digest()
    1.99          self.e = self._extract_bits(hash, self.s)
   1.100 -        print "Player", self.runtime.id, " e =", self.e
   1.101 +        #print "Player", self.runtime.id, " e =", self.e
   1.102  
   1.103      def _broadcast(self, values):
   1.104          msg = repr(values) if self.prover_id == self.runtime.id else None
     2.1 --- a/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 11:57:48 2010 +0200
     2.2 +++ b/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 14:33:35 2010 +0200
     2.3 @@ -28,13 +28,19 @@
     2.4  from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
     2.5  
     2.6  
     2.7 +class RuntimeStub(object):
     2.8 +    def __init__(self, players=[1, 2, 3], id=1):
     2.9 +        self.players = players
    2.10 +        self.id = id
    2.11 +
    2.12  class BeDOZaZeroKnowledgeTest(BeDOZaTestCase):
    2.13  
    2.14      num_players = 3
    2.15  
    2.16      def test_zk_matrix_entries_are_correct(self):
    2.17 -        s = 5
    2.18 -        zk = ZKProof(s, None, None, 0, None, None)
    2.19 +        s, k, prover_id = 5, 1, 1
    2.20 +        c = [None] * s
    2.21 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.22          zk.e = [1, 0, 0, 1, 1]
    2.23          for i in range(zk.s):
    2.24              for j in range(zk.m):
    2.25 @@ -44,34 +50,38 @@
    2.26                      self.assertEquals(0, zk._E(j, i))
    2.27  
    2.28      def test_vec_pow_is_correct(self):
    2.29 -        s, Zn = 5, GF(17)
    2.30 +        s, prover_id, k, Zn = 5, 1, 0, GF(17)
    2.31 +        c = [None] * s
    2.32          y = [Zn(i) for i in range(1, 6)]
    2.33 -        zk = ZKProof(s, None, Zn, 0, None, None)
    2.34 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.35          zk.e = [1, 0, 1, 1, 0]
    2.36          y_pow_E = zk._vec_pow_E(y)
    2.37          self.assertEquals([Zn(v) for v in [1, 2, 3, 8, 13, 12, 3, 5, 1]],
    2.38                            y_pow_E)
    2.39  
    2.40      def test_vec_pow_is_correct_2(self):
    2.41 -        s, Zn = 3, GF(17)
    2.42 +        s, k, Zn, prover_id = 3, 0, GF(17), 1
    2.43 +        c = [None] * s
    2.44          y = [Zn(i) for i in [1, 7, 2]]
    2.45 -        zk = ZKProof(s, None, Zn, 0, None, None)
    2.46 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.47          zk.e = [0, 1, 1]
    2.48          y_pow_E = zk._vec_pow_E(y)
    2.49          self.assertEquals([Zn(v) for v in [1, 1, 7, 14, 2]], y_pow_E)
    2.50  
    2.51      def test_vec_mul_E_is_correct(self):
    2.52 -        s, Zn = 5, GF(17)
    2.53 +        s, prover_id, k, Zn = 5, 1, 0, GF(17)
    2.54 +        c = [None] * s
    2.55          y = [Zn(i) for i in range(1, 6)]
    2.56 -        zk = ZKProof(s, None, Zn, 0, None, None)
    2.57 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.58          zk.e = [1, 0, 1, 1, 0]
    2.59          x = [1, 2, 0, 1, 0]
    2.60          x_mul_E = zk._vec_mul_E(x)
    2.61          self.assertEquals([v for v in [1, 2, 1, 4, 2, 1, 1, 0, 0]], x_mul_E)
    2.62  
    2.63      def test_vec_mul_E_is_correct_2(self):
    2.64 -        s, Zn = 3, GF(17)
    2.65 -        zk = ZKProof(s, None, Zn, 0, None, None)
    2.66 +        s, k, prover_id = 3, 0, 1
    2.67 +        c = [None] * s
    2.68 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
    2.69          zk.e = [0, 1, 1]
    2.70          x = [2, -3, 0]
    2.71          x_mul_E = zk._vec_mul_E(x)
    2.72 @@ -79,7 +89,9 @@
    2.73  
    2.74      @protocol
    2.75      def test_broadcast(self, runtime):
    2.76 -        zk = ZKProof(0, 2, None, 0, runtime, None)
    2.77 +        s, k, prover_id = 0, 2, 1
    2.78 +        c = []
    2.79 +        zk = ZKProof(s, prover_id, k, runtime, c)
    2.80          res = zk._broadcast([5, 6, 7])
    2.81          def verify(res):
    2.82              self.assertEquals(eval(res), [5, 6, 7])
    2.83 @@ -87,8 +99,10 @@
    2.84          return res
    2.85  
    2.86      def test_extract_bits(self):
    2.87 -        s = 5
    2.88 -        zk = ZKProof(s, None, None, 0, None, None)
    2.89 +        s, k, prover_id = 5, 1, 1
    2.90 +        c = [None] * s
    2.91 +        runtime = RuntimeStub()
    2.92 +        zk = ZKProof(s, prover_id, k, runtime, c)
    2.93          self.assertEquals([], zk._extract_bits('test', 0))
    2.94          self.assertEquals([0], zk._extract_bits('test', 1))
    2.95          self.assertEquals([0, 1], zk._extract_bits('test', 2))
    2.96 @@ -98,26 +112,28 @@
    2.97          self.assertEquals([0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1], zk._extract_bits('test', 14))
    2.98  
    2.99      def test_generate_e_generates_e_of_right_length(self):
   2.100 -        s = 5
   2.101 +        s, prover_id, k = 9, 1, 0
   2.102          c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
   2.103 -        zk = ZKProof(s, None, None, 0, None, c)
   2.104 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
   2.105          zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
   2.106          zk._generate_e()
   2.107 -        self.assertEquals(5, len(zk.e))
   2.108 +        self.assertEquals(s, len(zk.e))
   2.109  
   2.110      def test_generate_e_is_deterministic(self):
   2.111 -        s = 5
   2.112 +        s, prover_id, k = 9, 1, 0
   2.113          c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
   2.114 -        zk = ZKProof(s, None, None, 0, None, c)
   2.115 +        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
   2.116          zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
   2.117          zk._generate_e()
   2.118          e1 = zk.e
   2.119          zk._generate_e()
   2.120          self.assertEquals(e1, zk.e)
   2.121  
   2.122 -    def test_generate_Z_and_W_is_correct(self):
   2.123 -        s, Zn = 3, GF(17)
   2.124 -        zk = ZKProof(s, 1, Zn, 0, None, None)
   2.125 +    @protocol
   2.126 +    def test_generate_Z_and_W_is_correct(self, runtime):
   2.127 +        s, prover_id, k = 3, 1, 0
   2.128 +        c = [None] * s
   2.129 +        zk = ZKProof(s, prover_id, k, runtime, c)
   2.130          zk.u = [1, -2, 0, 6, -3]
   2.131          zk.v = [3, 5, 2, 1, 7]
   2.132          zk.x = [2, -3, 0]
   2.133 @@ -140,20 +156,20 @@
   2.134          return xs, rs, cs
   2.135  
   2.136      @protocol
   2.137 -    def test_proof(self, runtime):
   2.138 +    def test_succeeding_proof(self, runtime):
   2.139          seed = 2348838
   2.140 -        k, s, Zn, prover_id = 3, 3, GF(17), 1
   2.141 +        k, s, prover_id = 5, 3, 1
   2.142          player_random = Random(seed + runtime.id)
   2.143          shared_random = Random(seed)
   2.144          paillier = ModifiedPaillier(runtime, Random(player_random.getrandbits(128)))
   2.145          x, r, c = self._generate_test_ciphertexts(shared_random, runtime, k, s, prover_id)
   2.146 -        print "Player", runtime.id, " x =", x
   2.147 -        print "Player", runtime.id, " r =", r
   2.148 -        print "Player", runtime.id, " c =", c
   2.149 +        #print "Player", runtime.id, " x =", x
   2.150 +        #print "Player", runtime.id, " r =", r
   2.151 +        #print "Player", runtime.id, " c =", c
   2.152          if runtime.id == prover_id: 
   2.153 -            zk = ZKProof(s, prover_id, Zn, k, runtime, c, paillier=paillier, random=player_random, x=x, r=r)
   2.154 +            zk = ZKProof(s, prover_id, k, runtime, c, paillier=paillier, random=player_random, x=x, r=r)
   2.155          else:
   2.156 -            zk = ZKProof(s, prover_id, Zn, k, runtime, c, paillier=paillier, random=player_random)
   2.157 +            zk = ZKProof(s, prover_id, k, runtime, c, paillier=paillier, random=player_random)
   2.158  
   2.159          deferred_proof = zk.start()
   2.160          return deferred_proof
     3.1 --- a/viff/test/bedoza/util.py	Tue Sep 28 11:57:48 2010 +0200
     3.2 +++ b/viff/test/bedoza/util.py	Tue Sep 28 14:33:35 2010 +0200
     3.3 @@ -44,7 +44,7 @@
     3.4          # In production, paillier keys should be something like 2000
     3.5          # bit. For test purposes, it is ok to use small keys.
     3.6          # TODO: paillier freezes if key size is too small, e.g. 13.
     3.7 -        return generate_configs(paillier=NaClPaillier(250), *args)
     3.8 +        return generate_configs(paillier=NaClPaillier(100), *args)
     3.9  
    3.10  
    3.11  def skip_if_missing_packages(*test_cases):