viff

changeset 1568:cec0ff157247

BeDOZa: Cleaned up various naming issues.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Mon, 04 Oct 2010 10:26:57 +0200
parents 3bf0533ed32c
children 7cfd212041ac
files viff/bedoza/bedoza_triple.py viff/bedoza/share_generators.py viff/test/bedoza/test_bedoza_runtime.py viff/test/bedoza/test_bedoza_triple.py
diffstat 4 files changed, 122 insertions(+), 76 deletions(-) [+]
line diff
     1.1 --- a/viff/bedoza/bedoza_triple.py	Thu Sep 30 11:47:57 2010 +0200
     1.2 +++ b/viff/bedoza/bedoza_triple.py	Mon Oct 04 10:26:57 2010 +0200
     1.3 @@ -29,7 +29,7 @@
     1.4  from viff.util import rand
     1.5  from viff.bedoza.shares import BeDOZaShare, BeDOZaShareContents, PartialShare
     1.6  from viff.bedoza.shares import PartialShareContents
     1.7 -from viff.bedoza.share_generators import PartialShareGenerator, ShareGenerator
     1.8 +from viff.bedoza.share_generators import ShareGenerator, PartialShareGenerator
     1.9  from viff.bedoza.keylist import BeDOZaKeyList
    1.10  from viff.bedoza.maclist import BeDOZaMACList
    1.11  from viff.bedoza.add_macs import add_macs
    1.12 @@ -81,76 +81,60 @@
    1.13          self.alpha = alpha_random.randint(0, p - 1)
    1.14          self.n2 = runtime.players[runtime.id].pubkey['n_square']
    1.15  
    1.16 -    def _bit_length_of(self, i):
    1.17 -        bit_length = 0
    1.18 -        while i:
    1.19 -            i >>= 1
    1.20 -            bit_length += 1
    1.21 -        return bit_length
    1.22  
    1.23      def generate_triples(self):
    1.24 -        """Generates and returns a set with *self.security_parameter* triples."""
    1.25 -        return generate_triples(self, self.security_parameter)
    1.26 -        
    1.27 -    def generate_triples(self, n):
    1.28 -        """Generates and returns a set of n triples.
    1.29 -        
    1.30 +        """Generates triples for use in the BeDOZa protocol.
    1.31 +
    1.32 +        Returns a deferred that will eventually yield a list
    1.33 +        containing *self.security_parameter* multiplicative
    1.34 +        triples. Each of these triples is an object of type
    1.35 +        viff.triple.Triple. The components of each triple t, e.g.
    1.36 +
    1.37 +            t.a, t.b, and t.c,
    1.38 +
    1.39 +        are each of type BeDOZaShare and guaranteed to satisfy the
    1.40 +        equation
    1.41 +
    1.42 +            t.c = t.a * t.b.
    1.43 +
    1.44 +        This method carries out the off-line work that is needed for
    1.45 +        the BeDOZa protocol to work.
    1.46 +
    1.47          Data sent over the network is packaged in large hunks in order
    1.48          to optimize. TODO: Explain better.
    1.49  
    1.50          TODO: This method needs to have enough RAM to represent all n
    1.51          triples in memory at the same time. Is there a nice way to
    1.52          stream this, e.g. by using Python generators?
    1.53 +
    1.54          """
    1.55 +        return self._generate_triples(self.security_parameter)
    1.56  
    1.57 +
    1.58 +    def _generate_triples(self, number_of_triples):
    1.59          self.runtime.increment_pc()
    1.60 +        triples = self._generate_triple_candidates(2 * number_of_triples)
    1.61 +        return self._verify_triple_candidates(number_of_triples, triples)
    1.62 +
    1.63 +
    1.64 +    def _generate_triple_candidates(self, n):
    1.65 +        """Generates triple candidates for use in the BeDOZa protocol.
    1.66 +
    1.67 +        Returns a deferred that will eventually yield a list of 3n
    1.68 +        shares of type viff.bedoza.shares.BeDOZaShare corresponding to
    1.69 +        n multiplicative tuples. The first n are the a's, then comes n
    1.70 +        b's followed by n c's.
    1.71          
    1.72 -        def check(v, a, b, c):
    1.73 -            if v.value != 0:
    1.74 -                raise Exception("TripleTest failed - The two triples were "
    1.75 -                                "inconsistent.")
    1.76 -            return Triple(a, b, c)
    1.77 -        
    1.78 -        def compute_value(r, a, b, c, x, y, z):
    1.79 -            l = self.runtime._cmul(r, x, self.Zp)
    1.80 -            m = self.runtime._cmul(r, y, self.Zp)
    1.81 -            k = self.runtime._cmul(r*r, z, self.Zp)
    1.82 -            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
    1.83 -            v = self.runtime.open(v)
    1.84 -            v.addCallback(check, a, b, c)
    1.85 -            return v
    1.86 +        The triples are only candidates because consistency of the
    1.87 +        triples is only half-way guaranteed in the precense of active
    1.88 +        adversaries. More concretely, the triples returned by this
    1.89 +        method are guaranteed - even in the precense of an active
    1.90 +        adversary - to be of the right size. But they may not satisfy
    1.91 +        the equation
    1.92  
    1.93 -        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier,
    1.94 -                             self.u_bound, self.alpha)
    1.95 -        
    1.96 -        random_shares = gen.generate_random_shares(n)
    1.97 +            c = a * b.
    1.98  
    1.99 -        results = [Deferred() for _ in xrange(n)]
   1.100 -        
   1.101 -        triples = self._generate_passive_triples(2 * n)
   1.102 -
   1.103 -        for inx in xrange(n):
   1.104 -            a = triples[inx]
   1.105 -            b = triples[inx + 2 * n]
   1.106 -            c = triples[inx + 4 * n]
   1.107 -            x = triples[inx + n]
   1.108 -            y = triples[inx + 3 * n]
   1.109 -            z = triples[inx + 5 * n]
   1.110 -            r = self.runtime.open(random_shares[inx])
   1.111 -            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
   1.112 -            r.chainDeferred(results[inx])
   1.113 -        return results
   1.114 -          
   1.115 -        # TODO: Do some ZK stuff.
   1.116 -
   1.117 -    def _generate_passive_triples(self, n):
   1.118 -        """Generates and returns a list of 3n shares corresponding to
   1.119 -        n passive tuples. The first n are the a's, then comes n b's
   1.120 -        followed by n c's.
   1.121 -        
   1.122 -        Consistency is only guaranteed if all players follow the protool.
   1.123          """
   1.124 -
   1.125          self.runtime.increment_pc()
   1.126          
   1.127          gen = PartialShareGenerator(self.Zp, self.runtime, self.random,
   1.128 @@ -160,21 +144,81 @@
   1.129               partial_shares.append(
   1.130                   gen.generate_share(
   1.131                       self.random.randint(0, self.Zp.modulus - 1)))
   1.132 -
   1.133 -
   1.134 -        partial_shares_c = self._full_mul(partial_shares[0:n],
   1.135 -                                          partial_shares[n:2*n])
   1.136 -
   1.137 +        partial_shares_c = self._full_mul(partial_shares[0: n],
   1.138 +                                          partial_shares[n: 2 * n])
   1.139          full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
   1.140                                 self.random, self.paillier,
   1.141                                 partial_shares + partial_shares_c)
   1.142 -
   1.143          return full_shares  
   1.144  
   1.145 -        # for player i:
   1.146 -        #     receive c from player i and set 
   1.147 -        #         m^i=Decrypt(c)
   1.148 -    
   1.149 +
   1.150 +    def _verify_triple_candidates(self, n, triple_candidates):
   1.151 +        """Verify remaining consistency of triple candidates.
   1.152 +
   1.153 +        Takes as input a deferred list of 2n triple candidates as
   1.154 +        generated by _generate_triple_candidates(2 * n) and returns
   1.155 +        another deferred that will eventually yield a list of
   1.156 +        viff.triple.Triple objects that are guaranteed to be fully
   1.157 +        consistent. That is, the shares of the triples are guaranteed
   1.158 +        to be of the right size and for each triple, the shares are
   1.159 +        quaranteed to satisfy c = a * b.
   1.160 +
   1.161 +        The technique implemented in this method is essentially that
   1.162 +        listed in Figure 5.5 in the progress report "LEGO and Other
   1.163 +        Cryptographic Constructions" by Claudio Orlandi.
   1.164 +
   1.165 +        However, since we only implement a protocol that is secure in
   1.166 +        the Random Oracle Model and not the Common Reference String
   1.167 +        Model, we can safely skip step 2 of Figure 5.5 and instead
   1.168 +        generate r by having all players P_i broadcast a random
   1.169 +        element r_i and then have each player compute r as the hash of
   1.170 +        the sum of all r_i's.
   1.171 +
   1.172 +        """
   1.173 +        assert n == len(triple_candidates) / 6
   1.174 +
   1.175 +        def check(v, a, b, c):
   1.176 +            if v.value != 0:
   1.177 +                raise Exception(
   1.178 +                    "TripleTest failed - The two triple candidates were "
   1.179 +                    "inconsistent.")
   1.180 +            return Triple(a, b, c)
   1.181 +        
   1.182 +        def compute_value(r, a, b, c, x, y, z):
   1.183 +            l = self.runtime._cmul(r, x, self.Zp)
   1.184 +            m = self.runtime._cmul(r, y, self.Zp)
   1.185 +            k = self.runtime._cmul(r * r, z, self.Zp)
   1.186 +            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
   1.187 +            v = self.runtime.open(v)
   1.188 +            v.addCallback(check, a, b, c)
   1.189 +            return v
   1.190 +
   1.191 +        results = [Deferred() for _ in xrange(n)]
   1.192 +        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier,
   1.193 +                             self.u_bound, self.alpha)
   1.194 +        random_shares = gen.generate_random_shares(n)
   1.195 +
   1.196 +        for inx in xrange(n):
   1.197 +            a = triple_candidates[inx]
   1.198 +            b = triple_candidates[inx + 2 * n]
   1.199 +            c = triple_candidates[inx + 4 * n]
   1.200 +            x = triple_candidates[inx + n]
   1.201 +            y = triple_candidates[inx + 3 * n]
   1.202 +            z = triple_candidates[inx + 5 * n]
   1.203 +            r = self.runtime.open(random_shares[inx])
   1.204 +            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
   1.205 +            r.chainDeferred(results[inx])
   1.206 +        return results
   1.207 +
   1.208 +
   1.209 +    def _bit_length_of(self, i):
   1.210 +        bit_length = 0
   1.211 +        while i:
   1.212 +            i >>= 1
   1.213 +            bit_length += 1
   1.214 +        return bit_length
   1.215 +
   1.216 +
   1.217      def _mul(self, inx, jnx, n, ais=None, cjs=None):
   1.218          """Multiply each of the field elements in *ais* with the
   1.219          corresponding encrypted elements in *cjs*.
   1.220 @@ -191,6 +235,7 @@
   1.221          TripleGenerator.generate_triples.
   1.222          TODO: How can we allow a user of the runtime to adjust this
   1.223          constraint at a higher level of abstraction?
   1.224 +
   1.225          """
   1.226          transmission_restraint_constant = 425
   1.227  
   1.228 @@ -247,7 +292,8 @@
   1.229              deferred = zis_deferred
   1.230  
   1.231          return deferred
   1.232 -       
   1.233 +
   1.234 +
   1.235      def _full_mul(self, a, b):
   1.236          """Multiply each of the PartialShares in the list *a* with the
   1.237          corresponding PartialShare in the list *b*.
     2.1 --- a/viff/bedoza/share_generators.py	Thu Sep 30 11:47:57 2010 +0200
     2.2 +++ b/viff/bedoza/share_generators.py	Mon Oct 04 10:26:57 2010 +0200
     2.3 @@ -20,7 +20,7 @@
     2.4  from viff.bedoza.util import _convolute
     2.5  from viff.bedoza.add_macs import add_macs
     2.6  
     2.7 -class PartialShareGenerator:
     2.8 +class PartialShareGenerator(object):
     2.9  
    2.10      def __init__(self, Zp, runtime, random, paillier):
    2.11          self.paillier = paillier
     3.1 --- a/viff/test/bedoza/test_bedoza_runtime.py	Thu Sep 30 11:47:57 2010 +0200
     3.2 +++ b/viff/test/bedoza/test_bedoza_runtime.py	Mon Oct 04 10:26:57 2010 +0200
     3.3 @@ -315,7 +315,7 @@
     3.4  
     3.5          random = Random(3423993)
     3.6          gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, random)
     3.7 -        [triple] = gen.generate_triples(1)
     3.8 +        [triple] = gen._generate_triples(1)
     3.9          triple.addCallback(open)
    3.10          return triple
    3.11  
    3.12 @@ -349,7 +349,7 @@
    3.13  
    3.14          gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    3.15          alpha = gen.alpha
    3.16 -        [triple] = gen.generate_triples(1)
    3.17 +        [triple] = gen._generate_triples(1)
    3.18          runtime.schedule_callback(triple, do_stuff, alpha)
    3.19          return triple
    3.20  
    3.21 @@ -365,7 +365,7 @@
    3.22  
    3.23          gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    3.24          alpha = gen.alpha
    3.25 -        triples = gen.generate_triples(1)
    3.26 +        triples = gen._generate_triples(1)
    3.27          
    3.28          def do_mult(triples, alpha):
    3.29              runtime.triples = triples
    3.30 @@ -416,7 +416,7 @@
    3.31  
    3.32          gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    3.33          alpha = gen.alpha
    3.34 -        [triple] = gen.generate_triples(1)
    3.35 +        [triple] = gen._generate_triples(1)
    3.36          runtime.schedule_callback(triple, do_stuff, alpha)
    3.37          return triple
    3.38  
    3.39 @@ -450,7 +450,7 @@
    3.40  
    3.41          gen = TripleGenerator(runtime, self.security_parameter, self.Zp.modulus, Random(3423993))
    3.42          alpha = gen.alpha
    3.43 -        [triple] = gen.generate_triples(1)
    3.44 +        [triple] = gen._generate_triples(1)
    3.45          runtime.schedule_callback(triple, do_stuff, alpha)
    3.46          return triple
    3.47  
     4.1 --- a/viff/test/bedoza/test_bedoza_triple.py	Thu Sep 30 11:47:57 2010 +0200
     4.2 +++ b/viff/test/bedoza/test_bedoza_triple.py	Mon Oct 04 10:26:57 2010 +0200
     4.3 @@ -392,7 +392,7 @@
     4.4          random = Random(283883)        
     4.5          triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
     4.6  
     4.7 -        triples = triple_generator.generate_triples(10)
     4.8 +        triples = triple_generator._generate_triples(10)
     4.9  
    4.10          def check((a, b, c)):
    4.11              self.assertEquals(c, a * b)
    4.12 @@ -410,7 +410,7 @@
    4.13          return gatherResults(triples)
    4.14  
    4.15      @protocol
    4.16 -    def test_passive_triples_generates_correct_triples(self, runtime):
    4.17 +    def test_generate_triple_candidates_generates_correct_triples(self, runtime):
    4.18          p = 17
    4.19  
    4.20          Zp = GF(p)
    4.21 @@ -418,7 +418,7 @@
    4.22          random = Random(283883)        
    4.23          triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
    4.24  
    4.25 -        triples = triple_generator._generate_passive_triples(5)
    4.26 +        triples = triple_generator._generate_triple_candidates(5)
    4.27          def verify(triples):
    4.28              for inx in xrange(len(triples) // 3):
    4.29                  self.assertEquals(triples[10 + inx], triples[inx] * triples[5 + inx])