changeset 1545:8b1b64b3ea5b

Implemented security parameter and added it to u_bound.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Mon, 20 Sep 2010 14:30:03 +0200
parents ba687bceca20
children da966a4620f4
files viff/bedoza/bedoza_triple.py viff/test/test_bedoza_runtime.py viff/test/test_bedoza_triple.py
diffstat 3 files changed, 71 insertions(+), 117 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza/bedoza_triple.py	Mon Sep 20 10:46:31 2010 +0200
+++ b/viff/bedoza/bedoza_triple.py	Mon Sep 20 14:30:03 2010 +0200
@@ -52,7 +52,7 @@
 
 class TripleGenerator(object):
 
-    def __init__(self, runtime, p, random):
+    def __init__(self, runtime, security_parameter, p, random):
         assert p > 1
         self.random = random
         # TODO: Generate Paillier cipher with N_i sufficiently larger than p
@@ -60,7 +60,8 @@
         self.p = p
         self.Zp = GF(p)
         self.k = self._bit_length_of(p)
-        self.u_bound = 2**(4 * self.k)
+        self.security_parameter = security_parameter
+        self.u_bound = 2**(self.security_parameter + 4 * self.k)
 
         paillier_random = Random(self.random.getrandbits(128))
         alpha_random = Random(self.random.getrandbits(128))
@@ -85,6 +86,10 @@
             bit_length += 1
         return bit_length
 
+    def generate_triples(self):
+        """Generates and returns a set with *self.security_parameter* triples."""
+        return generate_triples(self, self.security_parameter)
+        
     def generate_triples(self, n):
         """Generates and returns a set of n triples.
         
@@ -172,12 +177,10 @@
         """Multiply each of the field elements in *ais* with the
         corresponding encrypted elements in *cjs*.
         
-        Returns a deferred which will yield a list of PartialShareContents.
+        Returns a deferred which will yield a list of field elements.
         """
         CKIND = 1
-        DiKIND = 2
-        DjKIND = 3
-
+ 
         """The transmission_restraint_constant is the number of
         encrypted shares we can safely transmit in one call to
         sendData. The sendData method can only transmit up to
@@ -197,33 +200,24 @@
 
         pc = tuple(self.runtime.program_counter)
 
-        deferreds = []
+        deferred = []
         zis = []
         if self.runtime.id == inx:
             Nj_square = self.paillier.get_modulus_square(jnx)
             all_cs = []
-            all_dis = []
             for iny, (ai, cj) in enumerate(zip(ais, cjs)):
                 if iny % transmission_restraint_constant == 0:
                     cs = []
                     all_cs.append(cs)
-                    dis = []
-                    all_dis.append(dis)
                 u = rand.randint(0, self.u_bound)
                 Ej_u = self.paillier.encrypt(u, jnx)
                 cs.append( (fast_pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
                 zi = self.Zp(-u)
                 zis.append(zi)
-                dis.append(self.paillier.encrypt(zi.value, inx))
                 
             for cs in all_cs:
                 self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
 
-            for dis in all_dis:
-                for player_id in self.runtime.players:
-                    self.runtime.protocols[player_id].sendData(pc, DiKIND,
-                                                               str(dis))
-
         if self.runtime.id == jnx:
             all_cs = []
             for _ in xrange(number_of_packets):
@@ -234,65 +228,23 @@
             def decrypt(all_cs, pc, zis):
                 zjs = []
                 cs = reduce(lambda x, y: x + eval(y), all_cs, [])
-                all_djs = []
                 for iny, c in enumerate(cs):
-                    if iny % transmission_restraint_constant == 0:
-                        djs = []
-                        all_djs.append(djs)
                     t = self.paillier.decrypt(c)
                     zj = self.Zp(t)
                     zjs.append(zj)
-                    djs.append(self.paillier.encrypt(zj.value, jnx))
-                for djs in all_djs:
-                    for player_id in self.runtime.players:
-                        self.runtime.protocols[player_id].sendData(pc, DjKIND,
-                                                                   str(djs))
                 if not zis == []:
                     return [x + y for x, y in zip(zis, zjs)]
                 else:
                     return zjs 
             all_cs_d = gatherResults(all_cs)
             all_cs_d.addCallback(decrypt, pc, zis)
-            deferreds.append(all_cs_d)
+            deferred = all_cs_d
         else:
             zis_deferred = Deferred()
             zis_deferred.callback(zis)
-            deferreds.append(zis_deferred)
+            deferred = zis_deferred
 
-        all_dis = []
-        for _ in xrange(number_of_packets):
-            dis = Deferred()
-            self.runtime._expect_data(inx, DiKIND, dis)
-            all_dis.append(dis)
-        all_djs = []
-        for _ in xrange(number_of_packets):
-            djs = Deferred()
-            self.runtime._expect_data(jnx, DjKIND, djs)
-            all_djs.append(djs)
-
-        deferreds.append(gatherResults(all_dis))
-        deferreds.append(gatherResults(all_djs))
-        r = gatherResults(deferreds)
-        def wrap((values, dis, djs), inx, jnx):
-            dis = reduce(lambda x, y: x + eval(y), dis, [])
-            djs = reduce(lambda x, y: x + eval(y), djs, [])
-            n_square_i = self.paillier.get_modulus_square(inx)
-            n_square_j = self.paillier.get_modulus_square(jnx)
-            N_squared_list = [self.paillier.get_modulus_square(player_id)
-                              for player_id in self.runtime.players]
-            ps = []
-            
-            for v, di, dj in itertools.izip_longest(values, dis, djs,
-                                                    fillvalue=self.Zp(0)):
-                value = v
-                enc_shares = len(self.runtime.players) * [1]
-                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
-                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
-                ps.append(PartialShareContents(value, enc_shares,
-                                               N_squared_list))
-            return ps
-        r.addCallback(wrap, inx, jnx)
-        return r
+        return deferred
 
     def _full_mul(self, a, b):
         """Multiply each of the PartialShares in the list *a* with the
@@ -302,39 +254,41 @@
         """
         self.runtime.increment_pc()
         
-        def do_full_mul(shares, result_shares):
+        def do_full_mul(shareContents, result_shares):
             """Share content belonging to ai, bi are at:
-            shares[i], shares[len(shares) + i].
+            shareContents[i], shareContents[len(shareContents) + i].
             """
             deferreds = []
-            len_shares = len(shares)
-            a_values = [s.value for s in shares[0:len_shares/2]]
+            len_shares = len(shareContents)
+
+            ais = [shareContent.value for shareContent in shareContents[0:len_shares/2]]
+            bis = [shareContent.value for shareContent in shareContents[len_shares/2:]]
+            
             b_enc_shares = []
-            for inx in self.runtime.players:              
+            for inx in self.runtime.players:
                 b_enc_shares.append([s.enc_shares[inx - 1]
-                                     for s in shares[len_shares/2:]])
+                                     for s in shareContents[len_shares/2:]])
+
+            values = len(ais) * [0]
+
             for inx in xrange(0, len(self.runtime.players)):
                 for jnx in xrange(0, len(self.runtime.players)):
                     deferreds.append(self._mul(inx + 1,
                                                jnx + 1,
-                                               len(a_values),
-                                               a_values,
+                                               len(ais),
+                                               ais,
                                                b_enc_shares[jnx]))
-                        
-            def compute_shares(partialShareContents, len_shares, result_shares):
-                num_players = len(self.runtime.players)
-                pcs = len(partialShareContents[0]) * [None]
-                for ps in partialShareContents:
-                    for inx in xrange(0, len(ps)):
-                        if pcs[inx] == None:
-                            pcs[inx] = ps[inx]
-                        else:
-                            pcs[inx] += ps[inx]
-                for p, s in zip(pcs, result_shares):
-                    s.callback(p)
+            
+            def compute_shares(list_of_list_of_field_elements, values, result_shares):
+                for field_elements in list_of_list_of_field_elements:
+                    for inx, field_element in enumerate(field_elements):
+                        values[inx] += field_element
+
+                for v, s in zip(values, result_shares):
+                    s.callback(v)
                 return None
             d = gatherResults(deferreds)
-            d.addCallback(compute_shares, len_shares, result_shares)
+            d.addCallback(compute_shares, values, result_shares)
             return d
         result_shares = [Share(self.runtime, self.Zp) for x in a]
         self.runtime.schedule_callback(gatherResults(a + b),
--- a/viff/test/test_bedoza_runtime.py	Mon Sep 20 10:46:31 2010 +0200
+++ b/viff/test/test_bedoza_runtime.py	Mon Sep 20 14:30:03 2010 +0200
@@ -78,7 +78,8 @@
         RuntimeTestCase.setUp(self)
         self.Zp = GF(17)
         bits_in_p = 5
-        self.u_bound = 2**(4 * bits_in_p)
+        self.security_parameter = 32
+        self.u_bound = 2**(self.security_parameter + 4 * bits_in_p)
         self.alpha = 15
 
     @protocol
@@ -343,7 +344,7 @@
             return d
 
         random = Random(3423993)
-        gen = TripleGenerator(runtime, self.Zp.modulus, random)
+        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, random)
         [triple] = gen.generate_triples(1)
         triple.addCallback(open)
         return triple
@@ -376,7 +377,7 @@
             d.addCallback(check)
             return d
 
-        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
+        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
         alpha = gen.alpha
         [triple] = gen.generate_triples(1)
         runtime.schedule_callback(triple, do_stuff, alpha)
@@ -392,7 +393,7 @@
         def check(v):
             self.assertEquals(v, self.Zp(x1 * y1))
 
-        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
+        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
         alpha = gen.alpha
         triples = gen.generate_triples(1)
         
@@ -443,7 +444,7 @@
             d.addCallback(check)
             return d
 
-        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
+        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
         alpha = gen.alpha
         [triple] = gen.generate_triples(1)
         runtime.schedule_callback(triple, do_stuff, alpha)
@@ -477,7 +478,7 @@
             d.addCallback(check)
             return d
 
-        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
+        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
         alpha = gen.alpha
         [triple] = gen.generate_triples(1)
         runtime.schedule_callback(triple, do_stuff, alpha)
--- a/viff/test/test_bedoza_triple.py	Mon Sep 20 10:46:31 2010 +0200
+++ b/viff/test/test_bedoza_triple.py	Mon Sep 20 14:30:03 2010 +0200
@@ -76,6 +76,10 @@
 
     runtime_class = BeDOZaRuntime
 
+    def setUp(self):
+        RuntimeTestCase.setUp(self)
+        self.security_parameter = 32
+
     # TODO: During test, we would like generation of Paillier keys to
     # be deterministic. How do we obtain that?
     def generate_configs(self, *args):
@@ -407,9 +411,9 @@
         p = 17
 
         Zp = GF(p)
-        
+      
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
 
         triples = triple_generator.generate_triples(10)
 
@@ -433,9 +437,9 @@
         p = 17
 
         Zp = GF(p)
-        
+       
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
 
         triples = triple_generator._generate_passive_triples(5)
         def verify(triples):
@@ -456,8 +460,9 @@
     @protocol
     def test_mul_computes_correct_result(self, runtime):
         p = 17
+       
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, 32, p, random)
 
         Zp = GF(p)
 
@@ -471,35 +476,28 @@
         
         if runtime.id == 1:
             r1 = triple_generator._mul(1, 2, n, ais, cs)
-            def check1(partialShares):
-                for partialShare in partialShares:
-                    zi = triple_generator.paillier.decrypt(partialShare.enc_shares[0])
-                    self.assertEquals(partialShare.value.value, zi)
+            def check1(shares):
+                for share in shares:
                     pc = tuple(runtime.program_counter)
-                    runtime.protocols[2].sendData(pc, TEXT, str(zi))
+                    runtime.protocols[2].sendData(pc, TEXT, str(share.value))
                 return True
             r1.addCallback(check1)
             return r1
         else:
             r1 = triple_generator._mul(1, 2, n)
-            def check(partialShares):
+            def check(shares):
                 deferreds = []
-                for partialShare in partialShares:
+                for share in shares:
                     if runtime.id == 2:
-                        zj = triple_generator.paillier.decrypt(partialShare.enc_shares[1])
-                        self.assertEquals(partialShare.value.value, zj)
                         def check_additivity(zi, zj):
                             self.assertEquals((Zp(long(zi)) + zj).value, 8)
                             return None
                         d = Deferred()
-                        d.addCallback(check_additivity, partialShare.value)
+                        d.addCallback(check_additivity, share.value)
                         runtime._expect_data(1, TEXT, d)
                         deferreds.append(d)
                     else:
-                        self.assertEquals(partialShare.value, 0)
-                        self.assertNotEquals(partialShare.enc_shares[0], 0)
-                        self.assertNotEquals(partialShare.enc_shares[1], 0)
-                        self.assertEquals(partialShare.enc_shares[2], 1)
+                        self.assertEquals(share.value, 0)
                 return gatherResults(deferreds)
             r1.addCallback(check)
             return r1
@@ -507,8 +505,9 @@
     @protocol
     def test_mul_same_player_inputs_and_receives(self, runtime):
         p = 17
+      
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
 
         Zp = GF(p)
 
@@ -521,12 +520,10 @@
         n = len(ais)
         
         r1 = triple_generator._mul(2, 2, n, ais, cs)
-        def check(partialShareContents):
-            for partialShareContent in partialShareContents:
+        def check(shares):
+            for share in shares:
                 if runtime.id == 2:
-                    zi_enc = Zp(triple_generator.paillier.decrypt(partialShareContent.enc_shares[1]))
-                    self.assertEquals(zi_enc, partialShareContent.value)
-                    self.assertEquals(partialShareContent.value, 8)
+                    self.assertEquals(share.value, 8)
             return True
             
         r1.addCallback(check)
@@ -535,7 +532,9 @@
 
 class FullMulTest(BeDOZaTestCase): 
     num_players = 3
-    
+
+    timeout = 10
+        
     @protocol
     def test_fullmul_computes_the_correct_result(self, runtime):
         p = 17
@@ -543,7 +542,7 @@
         Zp = GF(p)
         
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
 
         paillier = triple_generator.paillier
         
@@ -565,7 +564,7 @@
                 self.assertEquals(6, Zp(sum(ls[2])))
             values = []
             for share in shares:
-                value = _convolute(runtime, share.value.value)
+                value = _convolute(runtime, share.value)
                 values.append(value)
             d = gatherResults(values)
             runtime.schedule_callback(d, test_sum)
@@ -582,7 +581,7 @@
         Zp = GF(p)
         
         random = Random(283883)        
-        triple_generator = TripleGenerator(runtime, p, random)
+        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
 
         paillier = triple_generator.paillier