viff

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 diff
     1.1 --- a/viff/bedoza/bedoza_triple.py	Mon Sep 20 10:46:31 2010 +0200
     1.2 +++ b/viff/bedoza/bedoza_triple.py	Mon Sep 20 14:30:03 2010 +0200
     1.3 @@ -52,7 +52,7 @@
     1.4  
     1.5  class TripleGenerator(object):
     1.6  
     1.7 -    def __init__(self, runtime, p, random):
     1.8 +    def __init__(self, runtime, security_parameter, p, random):
     1.9          assert p > 1
    1.10          self.random = random
    1.11          # TODO: Generate Paillier cipher with N_i sufficiently larger than p
    1.12 @@ -60,7 +60,8 @@
    1.13          self.p = p
    1.14          self.Zp = GF(p)
    1.15          self.k = self._bit_length_of(p)
    1.16 -        self.u_bound = 2**(4 * self.k)
    1.17 +        self.security_parameter = security_parameter
    1.18 +        self.u_bound = 2**(self.security_parameter + 4 * self.k)
    1.19  
    1.20          paillier_random = Random(self.random.getrandbits(128))
    1.21          alpha_random = Random(self.random.getrandbits(128))
    1.22 @@ -85,6 +86,10 @@
    1.23              bit_length += 1
    1.24          return bit_length
    1.25  
    1.26 +    def generate_triples(self):
    1.27 +        """Generates and returns a set with *self.security_parameter* triples."""
    1.28 +        return generate_triples(self, self.security_parameter)
    1.29 +        
    1.30      def generate_triples(self, n):
    1.31          """Generates and returns a set of n triples.
    1.32          
    1.33 @@ -172,12 +177,10 @@
    1.34          """Multiply each of the field elements in *ais* with the
    1.35          corresponding encrypted elements in *cjs*.
    1.36          
    1.37 -        Returns a deferred which will yield a list of PartialShareContents.
    1.38 +        Returns a deferred which will yield a list of field elements.
    1.39          """
    1.40          CKIND = 1
    1.41 -        DiKIND = 2
    1.42 -        DjKIND = 3
    1.43 -
    1.44 + 
    1.45          """The transmission_restraint_constant is the number of
    1.46          encrypted shares we can safely transmit in one call to
    1.47          sendData. The sendData method can only transmit up to
    1.48 @@ -197,33 +200,24 @@
    1.49  
    1.50          pc = tuple(self.runtime.program_counter)
    1.51  
    1.52 -        deferreds = []
    1.53 +        deferred = []
    1.54          zis = []
    1.55          if self.runtime.id == inx:
    1.56              Nj_square = self.paillier.get_modulus_square(jnx)
    1.57              all_cs = []
    1.58 -            all_dis = []
    1.59              for iny, (ai, cj) in enumerate(zip(ais, cjs)):
    1.60                  if iny % transmission_restraint_constant == 0:
    1.61                      cs = []
    1.62                      all_cs.append(cs)
    1.63 -                    dis = []
    1.64 -                    all_dis.append(dis)
    1.65                  u = rand.randint(0, self.u_bound)
    1.66                  Ej_u = self.paillier.encrypt(u, jnx)
    1.67                  cs.append( (fast_pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
    1.68                  zi = self.Zp(-u)
    1.69                  zis.append(zi)
    1.70 -                dis.append(self.paillier.encrypt(zi.value, inx))
    1.71                  
    1.72              for cs in all_cs:
    1.73                  self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
    1.74  
    1.75 -            for dis in all_dis:
    1.76 -                for player_id in self.runtime.players:
    1.77 -                    self.runtime.protocols[player_id].sendData(pc, DiKIND,
    1.78 -                                                               str(dis))
    1.79 -
    1.80          if self.runtime.id == jnx:
    1.81              all_cs = []
    1.82              for _ in xrange(number_of_packets):
    1.83 @@ -234,65 +228,23 @@
    1.84              def decrypt(all_cs, pc, zis):
    1.85                  zjs = []
    1.86                  cs = reduce(lambda x, y: x + eval(y), all_cs, [])
    1.87 -                all_djs = []
    1.88                  for iny, c in enumerate(cs):
    1.89 -                    if iny % transmission_restraint_constant == 0:
    1.90 -                        djs = []
    1.91 -                        all_djs.append(djs)
    1.92                      t = self.paillier.decrypt(c)
    1.93                      zj = self.Zp(t)
    1.94                      zjs.append(zj)
    1.95 -                    djs.append(self.paillier.encrypt(zj.value, jnx))
    1.96 -                for djs in all_djs:
    1.97 -                    for player_id in self.runtime.players:
    1.98 -                        self.runtime.protocols[player_id].sendData(pc, DjKIND,
    1.99 -                                                                   str(djs))
   1.100                  if not zis == []:
   1.101                      return [x + y for x, y in zip(zis, zjs)]
   1.102                  else:
   1.103                      return zjs 
   1.104              all_cs_d = gatherResults(all_cs)
   1.105              all_cs_d.addCallback(decrypt, pc, zis)
   1.106 -            deferreds.append(all_cs_d)
   1.107 +            deferred = all_cs_d
   1.108          else:
   1.109              zis_deferred = Deferred()
   1.110              zis_deferred.callback(zis)
   1.111 -            deferreds.append(zis_deferred)
   1.112 +            deferred = zis_deferred
   1.113  
   1.114 -        all_dis = []
   1.115 -        for _ in xrange(number_of_packets):
   1.116 -            dis = Deferred()
   1.117 -            self.runtime._expect_data(inx, DiKIND, dis)
   1.118 -            all_dis.append(dis)
   1.119 -        all_djs = []
   1.120 -        for _ in xrange(number_of_packets):
   1.121 -            djs = Deferred()
   1.122 -            self.runtime._expect_data(jnx, DjKIND, djs)
   1.123 -            all_djs.append(djs)
   1.124 -
   1.125 -        deferreds.append(gatherResults(all_dis))
   1.126 -        deferreds.append(gatherResults(all_djs))
   1.127 -        r = gatherResults(deferreds)
   1.128 -        def wrap((values, dis, djs), inx, jnx):
   1.129 -            dis = reduce(lambda x, y: x + eval(y), dis, [])
   1.130 -            djs = reduce(lambda x, y: x + eval(y), djs, [])
   1.131 -            n_square_i = self.paillier.get_modulus_square(inx)
   1.132 -            n_square_j = self.paillier.get_modulus_square(jnx)
   1.133 -            N_squared_list = [self.paillier.get_modulus_square(player_id)
   1.134 -                              for player_id in self.runtime.players]
   1.135 -            ps = []
   1.136 -            
   1.137 -            for v, di, dj in itertools.izip_longest(values, dis, djs,
   1.138 -                                                    fillvalue=self.Zp(0)):
   1.139 -                value = v
   1.140 -                enc_shares = len(self.runtime.players) * [1]
   1.141 -                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
   1.142 -                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
   1.143 -                ps.append(PartialShareContents(value, enc_shares,
   1.144 -                                               N_squared_list))
   1.145 -            return ps
   1.146 -        r.addCallback(wrap, inx, jnx)
   1.147 -        return r
   1.148 +        return deferred
   1.149  
   1.150      def _full_mul(self, a, b):
   1.151          """Multiply each of the PartialShares in the list *a* with the
   1.152 @@ -302,39 +254,41 @@
   1.153          """
   1.154          self.runtime.increment_pc()
   1.155          
   1.156 -        def do_full_mul(shares, result_shares):
   1.157 +        def do_full_mul(shareContents, result_shares):
   1.158              """Share content belonging to ai, bi are at:
   1.159 -            shares[i], shares[len(shares) + i].
   1.160 +            shareContents[i], shareContents[len(shareContents) + i].
   1.161              """
   1.162              deferreds = []
   1.163 -            len_shares = len(shares)
   1.164 -            a_values = [s.value for s in shares[0:len_shares/2]]
   1.165 +            len_shares = len(shareContents)
   1.166 +
   1.167 +            ais = [shareContent.value for shareContent in shareContents[0:len_shares/2]]
   1.168 +            bis = [shareContent.value for shareContent in shareContents[len_shares/2:]]
   1.169 +            
   1.170              b_enc_shares = []
   1.171 -            for inx in self.runtime.players:              
   1.172 +            for inx in self.runtime.players:
   1.173                  b_enc_shares.append([s.enc_shares[inx - 1]
   1.174 -                                     for s in shares[len_shares/2:]])
   1.175 +                                     for s in shareContents[len_shares/2:]])
   1.176 +
   1.177 +            values = len(ais) * [0]
   1.178 +
   1.179              for inx in xrange(0, len(self.runtime.players)):
   1.180                  for jnx in xrange(0, len(self.runtime.players)):
   1.181                      deferreds.append(self._mul(inx + 1,
   1.182                                                 jnx + 1,
   1.183 -                                               len(a_values),
   1.184 -                                               a_values,
   1.185 +                                               len(ais),
   1.186 +                                               ais,
   1.187                                                 b_enc_shares[jnx]))
   1.188 -                        
   1.189 -            def compute_shares(partialShareContents, len_shares, result_shares):
   1.190 -                num_players = len(self.runtime.players)
   1.191 -                pcs = len(partialShareContents[0]) * [None]
   1.192 -                for ps in partialShareContents:
   1.193 -                    for inx in xrange(0, len(ps)):
   1.194 -                        if pcs[inx] == None:
   1.195 -                            pcs[inx] = ps[inx]
   1.196 -                        else:
   1.197 -                            pcs[inx] += ps[inx]
   1.198 -                for p, s in zip(pcs, result_shares):
   1.199 -                    s.callback(p)
   1.200 +            
   1.201 +            def compute_shares(list_of_list_of_field_elements, values, result_shares):
   1.202 +                for field_elements in list_of_list_of_field_elements:
   1.203 +                    for inx, field_element in enumerate(field_elements):
   1.204 +                        values[inx] += field_element
   1.205 +
   1.206 +                for v, s in zip(values, result_shares):
   1.207 +                    s.callback(v)
   1.208                  return None
   1.209              d = gatherResults(deferreds)
   1.210 -            d.addCallback(compute_shares, len_shares, result_shares)
   1.211 +            d.addCallback(compute_shares, values, result_shares)
   1.212              return d
   1.213          result_shares = [Share(self.runtime, self.Zp) for x in a]
   1.214          self.runtime.schedule_callback(gatherResults(a + b),
     2.1 --- a/viff/test/test_bedoza_runtime.py	Mon Sep 20 10:46:31 2010 +0200
     2.2 +++ b/viff/test/test_bedoza_runtime.py	Mon Sep 20 14:30:03 2010 +0200
     2.3 @@ -78,7 +78,8 @@
     2.4          RuntimeTestCase.setUp(self)
     2.5          self.Zp = GF(17)
     2.6          bits_in_p = 5
     2.7 -        self.u_bound = 2**(4 * bits_in_p)
     2.8 +        self.security_parameter = 32
     2.9 +        self.u_bound = 2**(self.security_parameter + 4 * bits_in_p)
    2.10          self.alpha = 15
    2.11  
    2.12      @protocol
    2.13 @@ -343,7 +344,7 @@
    2.14              return d
    2.15  
    2.16          random = Random(3423993)
    2.17 -        gen = TripleGenerator(runtime, self.Zp.modulus, random)
    2.18 +        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, random)
    2.19          [triple] = gen.generate_triples(1)
    2.20          triple.addCallback(open)
    2.21          return triple
    2.22 @@ -376,7 +377,7 @@
    2.23              d.addCallback(check)
    2.24              return d
    2.25  
    2.26 -        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
    2.27 +        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    2.28          alpha = gen.alpha
    2.29          [triple] = gen.generate_triples(1)
    2.30          runtime.schedule_callback(triple, do_stuff, alpha)
    2.31 @@ -392,7 +393,7 @@
    2.32          def check(v):
    2.33              self.assertEquals(v, self.Zp(x1 * y1))
    2.34  
    2.35 -        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
    2.36 +        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    2.37          alpha = gen.alpha
    2.38          triples = gen.generate_triples(1)
    2.39          
    2.40 @@ -443,7 +444,7 @@
    2.41              d.addCallback(check)
    2.42              return d
    2.43  
    2.44 -        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
    2.45 +        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    2.46          alpha = gen.alpha
    2.47          [triple] = gen.generate_triples(1)
    2.48          runtime.schedule_callback(triple, do_stuff, alpha)
    2.49 @@ -477,7 +478,7 @@
    2.50              d.addCallback(check)
    2.51              return d
    2.52  
    2.53 -        gen = TripleGenerator(runtime, self.Zp.modulus, Random(3423993))
    2.54 +        gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    2.55          alpha = gen.alpha
    2.56          [triple] = gen.generate_triples(1)
    2.57          runtime.schedule_callback(triple, do_stuff, alpha)
     3.1 --- a/viff/test/test_bedoza_triple.py	Mon Sep 20 10:46:31 2010 +0200
     3.2 +++ b/viff/test/test_bedoza_triple.py	Mon Sep 20 14:30:03 2010 +0200
     3.3 @@ -76,6 +76,10 @@
     3.4  
     3.5      runtime_class = BeDOZaRuntime
     3.6  
     3.7 +    def setUp(self):
     3.8 +        RuntimeTestCase.setUp(self)
     3.9 +        self.security_parameter = 32
    3.10 +
    3.11      # TODO: During test, we would like generation of Paillier keys to
    3.12      # be deterministic. How do we obtain that?
    3.13      def generate_configs(self, *args):
    3.14 @@ -407,9 +411,9 @@
    3.15          p = 17
    3.16  
    3.17          Zp = GF(p)
    3.18 -        
    3.19 +      
    3.20          random = Random(283883)        
    3.21 -        triple_generator = TripleGenerator(runtime, p, random)
    3.22 +        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
    3.23  
    3.24          triples = triple_generator.generate_triples(10)
    3.25  
    3.26 @@ -433,9 +437,9 @@
    3.27          p = 17
    3.28  
    3.29          Zp = GF(p)
    3.30 -        
    3.31 +       
    3.32          random = Random(283883)        
    3.33 -        triple_generator = TripleGenerator(runtime, p, random)
    3.34 +        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
    3.35  
    3.36          triples = triple_generator._generate_passive_triples(5)
    3.37          def verify(triples):
    3.38 @@ -456,8 +460,9 @@
    3.39      @protocol
    3.40      def test_mul_computes_correct_result(self, runtime):
    3.41          p = 17
    3.42 +       
    3.43          random = Random(283883)        
    3.44 -        triple_generator = TripleGenerator(runtime, p, random)
    3.45 +        triple_generator = TripleGenerator(runtime, 32, p, random)
    3.46  
    3.47          Zp = GF(p)
    3.48  
    3.49 @@ -471,35 +476,28 @@
    3.50          
    3.51          if runtime.id == 1:
    3.52              r1 = triple_generator._mul(1, 2, n, ais, cs)
    3.53 -            def check1(partialShares):
    3.54 -                for partialShare in partialShares:
    3.55 -                    zi = triple_generator.paillier.decrypt(partialShare.enc_shares[0])
    3.56 -                    self.assertEquals(partialShare.value.value, zi)
    3.57 +            def check1(shares):
    3.58 +                for share in shares:
    3.59                      pc = tuple(runtime.program_counter)
    3.60 -                    runtime.protocols[2].sendData(pc, TEXT, str(zi))
    3.61 +                    runtime.protocols[2].sendData(pc, TEXT, str(share.value))
    3.62                  return True
    3.63              r1.addCallback(check1)
    3.64              return r1
    3.65          else:
    3.66              r1 = triple_generator._mul(1, 2, n)
    3.67 -            def check(partialShares):
    3.68 +            def check(shares):
    3.69                  deferreds = []
    3.70 -                for partialShare in partialShares:
    3.71 +                for share in shares:
    3.72                      if runtime.id == 2:
    3.73 -                        zj = triple_generator.paillier.decrypt(partialShare.enc_shares[1])
    3.74 -                        self.assertEquals(partialShare.value.value, zj)
    3.75                          def check_additivity(zi, zj):
    3.76                              self.assertEquals((Zp(long(zi)) + zj).value, 8)
    3.77                              return None
    3.78                          d = Deferred()
    3.79 -                        d.addCallback(check_additivity, partialShare.value)
    3.80 +                        d.addCallback(check_additivity, share.value)
    3.81                          runtime._expect_data(1, TEXT, d)
    3.82                          deferreds.append(d)
    3.83                      else:
    3.84 -                        self.assertEquals(partialShare.value, 0)
    3.85 -                        self.assertNotEquals(partialShare.enc_shares[0], 0)
    3.86 -                        self.assertNotEquals(partialShare.enc_shares[1], 0)
    3.87 -                        self.assertEquals(partialShare.enc_shares[2], 1)
    3.88 +                        self.assertEquals(share.value, 0)
    3.89                  return gatherResults(deferreds)
    3.90              r1.addCallback(check)
    3.91              return r1
    3.92 @@ -507,8 +505,9 @@
    3.93      @protocol
    3.94      def test_mul_same_player_inputs_and_receives(self, runtime):
    3.95          p = 17
    3.96 +      
    3.97          random = Random(283883)        
    3.98 -        triple_generator = TripleGenerator(runtime, p, random)
    3.99 +        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
   3.100  
   3.101          Zp = GF(p)
   3.102  
   3.103 @@ -521,12 +520,10 @@
   3.104          n = len(ais)
   3.105          
   3.106          r1 = triple_generator._mul(2, 2, n, ais, cs)
   3.107 -        def check(partialShareContents):
   3.108 -            for partialShareContent in partialShareContents:
   3.109 +        def check(shares):
   3.110 +            for share in shares:
   3.111                  if runtime.id == 2:
   3.112 -                    zi_enc = Zp(triple_generator.paillier.decrypt(partialShareContent.enc_shares[1]))
   3.113 -                    self.assertEquals(zi_enc, partialShareContent.value)
   3.114 -                    self.assertEquals(partialShareContent.value, 8)
   3.115 +                    self.assertEquals(share.value, 8)
   3.116              return True
   3.117              
   3.118          r1.addCallback(check)
   3.119 @@ -535,7 +532,9 @@
   3.120  
   3.121  class FullMulTest(BeDOZaTestCase): 
   3.122      num_players = 3
   3.123 -    
   3.124 +
   3.125 +    timeout = 10
   3.126 +        
   3.127      @protocol
   3.128      def test_fullmul_computes_the_correct_result(self, runtime):
   3.129          p = 17
   3.130 @@ -543,7 +542,7 @@
   3.131          Zp = GF(p)
   3.132          
   3.133          random = Random(283883)        
   3.134 -        triple_generator = TripleGenerator(runtime, p, random)
   3.135 +        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
   3.136  
   3.137          paillier = triple_generator.paillier
   3.138          
   3.139 @@ -565,7 +564,7 @@
   3.140                  self.assertEquals(6, Zp(sum(ls[2])))
   3.141              values = []
   3.142              for share in shares:
   3.143 -                value = _convolute(runtime, share.value.value)
   3.144 +                value = _convolute(runtime, share.value)
   3.145                  values.append(value)
   3.146              d = gatherResults(values)
   3.147              runtime.schedule_callback(d, test_sum)
   3.148 @@ -582,7 +581,7 @@
   3.149          Zp = GF(p)
   3.150          
   3.151          random = Random(283883)        
   3.152 -        triple_generator = TripleGenerator(runtime, p, random)
   3.153 +        triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
   3.154  
   3.155          paillier = triple_generator.paillier
   3.156