changeset 1574:0d3b99e1e3eb

BeDOZa: Connected zero-knowledge proof to the remaining protocol.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Mon, 04 Oct 2010 21:51:33 +0200
parents d2d8fda44084
children cfb8e1485006
files viff/bedoza/bedoza_triple.py viff/bedoza/share.py viff/test/bedoza/test_bedoza_triple.py
diffstat 3 files changed, 78 insertions(+), 29 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza/bedoza_triple.py	Mon Oct 04 12:04:47 2010 +0200
+++ b/viff/bedoza/bedoza_triple.py	Mon Oct 04 21:51:33 2010 +0200
@@ -65,6 +65,7 @@
         self.k = self._bit_length_of(p)
         self.security_parameter = security_parameter
         self.u_bound = 2**(self.security_parameter + 4 * self.k)
+        self.zk_random = Random(self.random.getrandbits(128))
 
         paillier_random = Random(self.random.getrandbits(128))
         alpha_random = Random(self.random.getrandbits(128))
@@ -374,7 +375,7 @@
                 return None
             
             d.addCallback(lambda values: generate_partial_share_contents(
-                    values, self.runtime, self.paillier))
+                    values, self.runtime, self.paillier, self.k, self.zk_random))
             d.addCallback(callBackPartialShareContents, result_shares)
             return d
         result_shares = [PartialShare(self.runtime, self.Zp) for _ in a]
--- a/viff/bedoza/share.py	Mon Oct 04 12:04:47 2010 +0200
+++ b/viff/bedoza/share.py	Mon Oct 04 21:51:33 2010 +0200
@@ -15,12 +15,14 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
 
+from gmpy import mpz
+
 from twisted.internet.defer import gatherResults
 
+from viff.bedoza.zero_knowledge import ZKProof
 from viff.bedoza.shares import PartialShareContents
-from viff.bedoza.util import _convolute
 
-def generate_partial_share_contents(field_elements, runtime, paillier):
+def generate_partial_share_contents(field_elements, runtime, paillier, k, random):
     """Protocol for generating partial shares.
 
     This protocol corresponds to the "Share" protocol in the document
@@ -34,34 +36,71 @@
     plaintexts are of limited size.
 
     Returns a deferred, which yields a list of PartialShareContents.
-    """
-    
+
+    """    
+    # TODO: We should assert that len(field_elements) == s.
+
+    # TODO: The gatherResults is used several times in this method in
+    # a way that prevents maximal asynchronicity. E.g. all players
+    # wait until all zero-knowledge proofs are completed before they
+    # start constructing partial shares. However, the callback for a
+    # particular partial share could be triggered as soon as the
+    # players have completed the zk proof for that share.
+
     runtime.increment_pc()
 
     N_squared_list = [paillier.get_modulus_square(player_id)
                       for player_id in runtime.players]
 
     list_of_enc_shares = []
+    list_of_random_elements = []
     for field_element in field_elements:
-        list_of_enc_shares.append(paillier.encrypt(field_element.value))
+        r, e = paillier.encrypt_r(field_element.value)
+        list_of_enc_shares.append(e)
+        list_of_random_elements.append(r)
        
-    list_of_enc_shares = runtime.broadcast(runtime.players.keys(), runtime.players.keys(),
-                                           str(list_of_enc_shares))
-    
-    def create_partial_share(list_of_enc_shares, field_elements):
-        list_of_enc_shares = [eval(x) for x in list_of_enc_shares]
+    list_of_enc_shares = runtime.broadcast(
+        runtime.players.keys(), runtime.players.keys(),
+        str(list_of_enc_shares))
 
+    def construct_partial_shares(zk_results, list_of_enc_shares, field_elements):
+        if False in zk_results:
+            raise Exception("Zero-knowledge proof failed")
         reordered_encrypted_shares = [[] for _ in list_of_enc_shares[0]]
         for enc_shares in list_of_enc_shares:
             for inx, enc_share in enumerate(enc_shares):
                 reordered_encrypted_shares[inx].append(enc_share)
+        partial_share_contents = []
+        for enc_shares, field_element \
+                in zip(reordered_encrypted_shares, field_elements):
+            partial_share_contents.append(PartialShareContents(
+                    field_element, enc_shares, N_squared_list))
+        return partial_share_contents
 
-        partialShareContents = []
-        for enc_shares, field_element in zip(reordered_encrypted_shares, field_elements):
-            partialShareContents.append(PartialShareContents(field_element, enc_shares, N_squared_list))
-        return partialShareContents
+    def do_zk_proofs(list_of_enc_shares, field_elements):
+        zk_results = []
+        list_of_enc_shares = [eval(x) for x in list_of_enc_shares]
+
+        # We expect all players to broadcast the same number of
+        # encrypted shares.
+        assert all([len(enc_shares) == len(list_of_enc_shares[0]) 
+                    for enc_shares in list_of_enc_shares])
+
+        for i in range(runtime.num_players):
+            x, r = None, None
+            if runtime.id == i + 1:
+                x, r = [mpz(e.value) 
+                        for e in field_elements], list_of_random_elements
+            zk_proof = ZKProof(
+                len(field_elements), i + 1, k, runtime, list_of_enc_shares[i],
+                random=random, x=x, r=r, paillier=paillier)
+            zk_result = zk_proof.start()
+            zk_results.append(zk_result)
+        d = gatherResults(zk_results)
+        runtime.schedule_callback(
+            d, construct_partial_shares, list_of_enc_shares, field_elements)
+        return d
 
     d = gatherResults(list_of_enc_shares)
-    runtime.schedule_callback(d, create_partial_share, field_elements)
+    runtime.schedule_callback(d, do_zk_proofs, field_elements)
     return d
-        
--- a/viff/test/bedoza/test_bedoza_triple.py	Mon Oct 04 12:04:47 2010 +0200
+++ b/viff/test/bedoza/test_bedoza_triple.py	Mon Oct 04 21:51:33 2010 +0200
@@ -39,6 +39,7 @@
 from viff.bedoza.util import _send, _convolute, _convolute_gf_elm
 from viff.bedoza.add_macs import add_macs
 from viff.bedoza.share_generators import ShareGenerator, PartialShareGenerator
+from viff.bedoza.share import generate_partial_share_contents
 
 from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
 from viff.test.bedoza.util import TestShareGenerator
@@ -497,18 +498,20 @@
 
     @protocol
     def test_share_protocol_single(self, runtime):
-        p = 17
+        p, k = 17, 5
         Zp = GF(p)
         random = Random(3455433 + runtime.id)
         elms = [Zp(runtime.id)]
         paillier_random = Random(random.getrandbits(128))
+        zk_random = Random(random.getrandbits(128))
         paillier = ModifiedPaillier(runtime, paillier_random)
-        from viff.bedoza.share import generate_partial_share_contents
-        partial_shares = generate_partial_share_contents(elms, runtime, paillier)
+        partial_shares = generate_partial_share_contents(
+            elms, runtime, paillier, k, zk_random)
 
         def decrypt(share_contents):
             self.assertEquals(1, len(share_contents))
-            decrypted_share = paillier.decrypt(share_contents[0].enc_shares[runtime.id - 1])
+            decrypted_share = paillier.decrypt(
+                share_contents[0].enc_shares[runtime.id - 1])
             decrypted_shares = _convolute(runtime, decrypted_share)
             def test_sum(vals):
                 self.assertEquals([Zp(e) for e in [1, 2, 3]], vals)
@@ -519,24 +522,29 @@
 
     @protocol
     def test_share_protocol_multi(self, runtime):
-        p = 17
+        p, k = 17, 5
         Zp = GF(p)
-        random = Random(3455433 + runtime.id)
+        random = Random(345453 + runtime.id)
         elms = [Zp(runtime.id), Zp(runtime.id * 3)]
         paillier_random = Random(random.getrandbits(128))
+        zk_random = Random(random.getrandbits(128))
         paillier = ModifiedPaillier(runtime, paillier_random)
-        from viff.bedoza.share import generate_partial_share_contents
-        partial_shares = generate_partial_share_contents(elms, runtime, paillier)
+        partial_shares = generate_partial_share_contents(
+            elms, runtime, paillier, k, zk_random)
 
         def decrypt(share_contents):
             self.assertEquals(2, len(share_contents))
-            decrypted_shares = [paillier.decrypt(share_contents[i].enc_shares[runtime.id - 1])
+            decrypted_shares = [paillier.decrypt(
+                    share_contents[i].enc_shares[runtime.id - 1])
                                 for i in range(2)]
-            decrypted_shares = [_convolute(runtime, decrypted_shares[i]) for i in range(2)]
+            decrypted_shares = [_convolute(runtime, decrypted_shares[i])
+                                for i in range(2)]
             def test_sum(vals, should_be):
                 self.assertEquals([Zp(e) for e in should_be], vals)
-            runtime.schedule_callback(decrypted_shares[0], test_sum, [1, 2, 3])
-            runtime.schedule_callback(decrypted_shares[1], test_sum, [3, 6, 9])
+            runtime.schedule_callback(
+                decrypted_shares[0], test_sum, [1, 2, 3])
+            runtime.schedule_callback(
+                decrypted_shares[1], test_sum, [3, 6, 9])
 
         runtime.schedule_callback(partial_shares, decrypt)
         return partial_shares
@@ -627,6 +635,7 @@
         
 
 skip_if_missing_packages(
+    ShareTest,
     ModifiedPaillierTest,
     PartialShareGeneratorTest,
     TripleTest,