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 wrap: on
line diff
--- a/viff/bedoza/zero_knowledge.py	Tue Sep 28 11:57:48 2010 +0200
+++ b/viff/bedoza/zero_knowledge.py	Tue Sep 28 14:33:35 2010 +0200
@@ -28,12 +28,9 @@
     inputs s ciphertexts c[i] = E(x[j], r[j]), i = 1, ..., s, created
     using the modified Paillier cipher and proves to the other players
     that the x[i]'s are of limited size, e.g. that abs(x[i]) <= 2**k.
-    
-    Zn is the plaintext field of player prover_id's modified Paillier
-    cipher.
     """
     
-    def __init__(self, s, prover_id, Zn, k, runtime, c, random=None, paillier=None, x=None, r=None):
+    def __init__(self, s, prover_id, k, runtime, c, random=None, paillier=None, x=None, r=None):
         """
         random: a random source (e.g. viff.util.Random)
 
@@ -43,12 +40,14 @@
         """
         assert len(c) == s
         assert prover_id in runtime.players
+        if x != None:
+            for xi in x:
+                assert abs(xi) <= 2**k
         self.x = x
         self.r = r
         self.s = s
         self.m = 2 * s - 1
         self.prover_id = prover_id
-        self.Zn = Zn
         self.k = k
         self.runtime = runtime
         self.c = c
@@ -56,7 +55,6 @@
         self.random = random
 
 
-
     def start(self):
         """Executes this zero-knowledge proof.
 
@@ -87,21 +85,24 @@
             #print 'e', len(self.e)
             #print 'u', len(self.u)
             return True # TODO
+        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))
-        T = [self.paillier.encrypt(self.Z[j], player_id=self.prover_id, random_elm=self.W[j]) for j in range(self.m)]
+        T = [self.paillier.encrypt(self.Z[j], player_id=self.prover_id, random_elm=self.W[j])
+             for j in range(self.m)]
         #print 'Z', len(self.Z)
         #print 'W', len(self.W)
         
         for j in xrange(self.m):
-            n = self.runtime.players[self.prover_id].pubkey['n']
-            print
-            print '---'
-            print self.runtime.id, j, S[j] % n
-            print self.runtime.id, j, T[j] % n
-
-            # TODO: Verify!
+            #print
+            #print '---'
+            #print self.runtime.id, j, S[j] % n**2
+            #print self.runtime.id, j, T[j]
+            # TODO: Return false if S[j] != T[j].
+            if abs(self.Z[j]) > 2**(2 * self.k):
+                print "WOOOOOOOOOOPS, PROOF NOT ACCEPTED"
 
 
     def _generate_u_v_and_d(self):
@@ -109,6 +110,7 @@
         for i in range(self.m):
             ui = rand_int_signed(self.random, 2**(2 * self.k))
             vi, di = self.paillier.encrypt_r(ui)
+            assert abs(ui) <= 2**(2 * self.k)
             self.u.append(ui)
             self.v.append(vi)
             self.d.append(di)
@@ -118,6 +120,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))
+
+        #print self.runtime.id
+        #print self.prover_id
+        n = self.runtime.players[self.prover_id].pubkey['n']
+        #print "N_1:", n
+        self.W = [w % n**2 for w in self.W]
+
         #print "Player", self.runtime.id, " Z =", self.Z
         #print "Player", self.runtime.id, " W =", self.W
 
@@ -181,7 +190,7 @@
             h.update(repr(d))
         hash = h.digest()
         self.e = self._extract_bits(hash, self.s)
-        print "Player", self.runtime.id, " e =", self.e
+        #print "Player", self.runtime.id, " e =", self.e
 
     def _broadcast(self, values):
         msg = repr(values) if self.prover_id == self.runtime.id else None
--- a/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 11:57:48 2010 +0200
+++ b/viff/test/bedoza/test_zero_knowledge.py	Tue Sep 28 14:33:35 2010 +0200
@@ -28,13 +28,19 @@
 from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
 
 
+class RuntimeStub(object):
+    def __init__(self, players=[1, 2, 3], id=1):
+        self.players = players
+        self.id = id
+
 class BeDOZaZeroKnowledgeTest(BeDOZaTestCase):
 
     num_players = 3
 
     def test_zk_matrix_entries_are_correct(self):
-        s = 5
-        zk = ZKProof(s, None, None, 0, None, None)
+        s, k, prover_id = 5, 1, 1
+        c = [None] * s
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [1, 0, 0, 1, 1]
         for i in range(zk.s):
             for j in range(zk.m):
@@ -44,34 +50,38 @@
                     self.assertEquals(0, zk._E(j, i))
 
     def test_vec_pow_is_correct(self):
-        s, Zn = 5, GF(17)
+        s, prover_id, k, Zn = 5, 1, 0, GF(17)
+        c = [None] * s
         y = [Zn(i) for i in range(1, 6)]
-        zk = ZKProof(s, None, Zn, 0, None, None)
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [1, 0, 1, 1, 0]
         y_pow_E = zk._vec_pow_E(y)
         self.assertEquals([Zn(v) for v in [1, 2, 3, 8, 13, 12, 3, 5, 1]],
                           y_pow_E)
 
     def test_vec_pow_is_correct_2(self):
-        s, Zn = 3, GF(17)
+        s, k, Zn, prover_id = 3, 0, GF(17), 1
+        c = [None] * s
         y = [Zn(i) for i in [1, 7, 2]]
-        zk = ZKProof(s, None, Zn, 0, None, None)
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [0, 1, 1]
         y_pow_E = zk._vec_pow_E(y)
         self.assertEquals([Zn(v) for v in [1, 1, 7, 14, 2]], y_pow_E)
 
     def test_vec_mul_E_is_correct(self):
-        s, Zn = 5, GF(17)
+        s, prover_id, k, Zn = 5, 1, 0, GF(17)
+        c = [None] * s
         y = [Zn(i) for i in range(1, 6)]
-        zk = ZKProof(s, None, Zn, 0, None, None)
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [1, 0, 1, 1, 0]
         x = [1, 2, 0, 1, 0]
         x_mul_E = zk._vec_mul_E(x)
         self.assertEquals([v for v in [1, 2, 1, 4, 2, 1, 1, 0, 0]], x_mul_E)
 
     def test_vec_mul_E_is_correct_2(self):
-        s, Zn = 3, GF(17)
-        zk = ZKProof(s, None, Zn, 0, None, None)
+        s, k, prover_id = 3, 0, 1
+        c = [None] * s
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.e = [0, 1, 1]
         x = [2, -3, 0]
         x_mul_E = zk._vec_mul_E(x)
@@ -79,7 +89,9 @@
 
     @protocol
     def test_broadcast(self, runtime):
-        zk = ZKProof(0, 2, None, 0, runtime, None)
+        s, k, prover_id = 0, 2, 1
+        c = []
+        zk = ZKProof(s, prover_id, k, runtime, c)
         res = zk._broadcast([5, 6, 7])
         def verify(res):
             self.assertEquals(eval(res), [5, 6, 7])
@@ -87,8 +99,10 @@
         return res
 
     def test_extract_bits(self):
-        s = 5
-        zk = ZKProof(s, None, None, 0, None, None)
+        s, k, prover_id = 5, 1, 1
+        c = [None] * s
+        runtime = RuntimeStub()
+        zk = ZKProof(s, prover_id, k, runtime, c)
         self.assertEquals([], zk._extract_bits('test', 0))
         self.assertEquals([0], zk._extract_bits('test', 1))
         self.assertEquals([0, 1], zk._extract_bits('test', 2))
@@ -98,26 +112,28 @@
         self.assertEquals([0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1], zk._extract_bits('test', 14))
 
     def test_generate_e_generates_e_of_right_length(self):
-        s = 5
+        s, prover_id, k = 9, 1, 0
         c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
-        zk = ZKProof(s, None, None, 0, None, c)
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
         zk._generate_e()
-        self.assertEquals(5, len(zk.e))
+        self.assertEquals(s, len(zk.e))
 
     def test_generate_e_is_deterministic(self):
-        s = 5
+        s, prover_id, k = 9, 1, 0
         c = [1, 1, 0, 0, 1, 0, 1, 0, 1]
-        zk = ZKProof(s, None, None, 0, None, c)
+        zk = ZKProof(s, prover_id, k, RuntimeStub(), c)
         zk.d = [1, 0, 0, 1, 1, 0, 1, 1, 1]
         zk._generate_e()
         e1 = zk.e
         zk._generate_e()
         self.assertEquals(e1, zk.e)
 
-    def test_generate_Z_and_W_is_correct(self):
-        s, Zn = 3, GF(17)
-        zk = ZKProof(s, 1, Zn, 0, None, None)
+    @protocol
+    def test_generate_Z_and_W_is_correct(self, runtime):
+        s, prover_id, k = 3, 1, 0
+        c = [None] * s
+        zk = ZKProof(s, prover_id, k, runtime, c)
         zk.u = [1, -2, 0, 6, -3]
         zk.v = [3, 5, 2, 1, 7]
         zk.x = [2, -3, 0]
@@ -140,20 +156,20 @@
         return xs, rs, cs
 
     @protocol
-    def test_proof(self, runtime):
+    def test_succeeding_proof(self, runtime):
         seed = 2348838
-        k, s, Zn, prover_id = 3, 3, GF(17), 1
+        k, s, prover_id = 5, 3, 1
         player_random = Random(seed + runtime.id)
         shared_random = Random(seed)
         paillier = ModifiedPaillier(runtime, Random(player_random.getrandbits(128)))
         x, r, c = self._generate_test_ciphertexts(shared_random, runtime, k, s, prover_id)
-        print "Player", runtime.id, " x =", x
-        print "Player", runtime.id, " r =", r
-        print "Player", runtime.id, " c =", c
+        #print "Player", runtime.id, " x =", x
+        #print "Player", runtime.id, " r =", r
+        #print "Player", runtime.id, " c =", c
         if runtime.id == prover_id: 
-            zk = ZKProof(s, prover_id, Zn, k, runtime, c, paillier=paillier, random=player_random, x=x, r=r)
+            zk = ZKProof(s, prover_id, k, runtime, c, paillier=paillier, random=player_random, x=x, r=r)
         else:
-            zk = ZKProof(s, prover_id, Zn, k, runtime, c, paillier=paillier, random=player_random)
+            zk = ZKProof(s, prover_id, k, runtime, c, paillier=paillier, random=player_random)
 
         deferred_proof = zk.start()
         return deferred_proof
--- a/viff/test/bedoza/util.py	Tue Sep 28 11:57:48 2010 +0200
+++ b/viff/test/bedoza/util.py	Tue Sep 28 14:33:35 2010 +0200
@@ -44,7 +44,7 @@
         # In production, paillier keys should be something like 2000
         # bit. For test purposes, it is ok to use small keys.
         # TODO: paillier freezes if key size is too small, e.g. 13.
-        return generate_configs(paillier=NaClPaillier(250), *args)
+        return generate_configs(paillier=NaClPaillier(100), *args)
 
 
 def skip_if_missing_packages(*test_cases):