changeset 1543:7db2fafaab44

BeDOZa: Partly implemented zero-knowledge protocol.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Tue, 21 Sep 2010 10:05:02 +0200
parents 8e06a2598579
children dae353266aa6
files viff/bedoza/zero_knowledge.py viff/test/test_bedoza_runtime.py
diffstat 2 files changed, 114 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/zero_knowledge.py	Tue Sep 21 10:05:02 2010 +0200
@@ -0,0 +1,84 @@
+# Copyright 2010 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+
+class ZKProof(object):
+    """Protocol proving that a player's plaintexts are of limited size.
+    
+    This is a zero-knowledge protocol in which player player_id 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 player_id's modified Paillier cipher.
+    
+    While player player_id must input the ciphertexts, the other players
+    should call the method with c = None.
+    
+    """
+    
+    def __init__(self, player_id, Zn, c=None):
+        self.player_id = player_id
+        self.Zn = Zn
+        self.c = c
+        self.e = None
+
+    def start():
+        
+        pass
+
+    def _set_e(self, e):
+        self.e = e
+        self.s = len(e)
+        self.m = 2 * len(e) - 1
+
+    def _generate_challenge(self):
+        # TODO: Implement.
+        self.e = [0, 0, 1, 0, 1]
+        self.s = len(e)
+        self.m = 2 * len(e) - 1
+
+
+    def _E(self, row, col):
+        """Computes the value of the entry in the matrix E at the given row
+        and column.
+        
+        The first column of E consists of the bits of e followed by 0's;
+        The next column has one zero, then the bits of e, followed by 0's,
+        etc.
+        """
+        if row >= col and row < col + self.s:
+            return self.e[row - col]
+        else:
+            return 0
+
+    def vec_add(self, x, y):
+        return [xi + yi for x, y in zip(x,y)]
+    
+    def vec_mul(self, x, y):
+        return [xi * yi for x, y in zip(x,y)]
+
+    def vec_pow_E(self, y):
+        """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))
+        res = [self.Zn(1)] * self.m
+        for j in range(2 * self.s - 1):
+            for i in range(self.s):
+                if self._E(j, i) == 1:
+                    res[j] *= y[i]
+        return res
--- a/viff/test/test_bedoza_runtime.py	Mon Sep 20 21:56:39 2010 +0200
+++ b/viff/test/test_bedoza_runtime.py	Tue Sep 21 10:05:02 2010 +0200
@@ -34,6 +34,7 @@
 from viff.bedoza.modified_paillier import ModifiedPaillier
 from viff.bedoza.share_generators import ShareGenerator
 from viff.bedoza.bedoza_triple import TripleGenerator
+from viff.bedoza.zero_knowledge import ZKProof
 
 # The PyPaillier and commitment packages are not standard parts of VIFF so we
 # skip them instead of letting them fail if the packages are not available. 
@@ -524,7 +525,35 @@
         d = runtime.open_two_values(x, y)
         d.addCallback(check)
         return d
-    
+
+
+# TODO: Move to test.bedoza.test_zero_knowledge.
+class BeDOZaZeroKnowledgeTest(RuntimeTestCase):
+
+    num_players = 3
+
+    timeout = 3
+
+    runtime_class = BeDOZaRuntime
+
+    def test_zk_matrix_entries_are_correct(self):
+        zk = ZKProof(None, None)
+        zk._set_e([1, 0, 0, 1, 1])
+        for i in range(zk.s):
+            for j in range(zk.m):
+                if j >= i and j < i + zk.s:
+                    self.assertEquals(zk.e[j - i], zk._E(j, i))
+                else:
+                    self.assertEquals(0, zk._E(j, i))
+
+    def test_vec_pow_is_correct(self):
+        Zn = GF(17)
+        y = [Zn(i) for i in range(1, 6)]
+        zk = ZKProof(None, Zn)
+        zk._set_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 skip_tests(module_name):
     BeDOZaBasicCommandsTest.skip = "Skipped due to missing " + module_name + " module."