viff

changeset 1517:054a27514891

BeDOZa: Refactored _add_macs to a toplevel function add_macs.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Thu, 22 Jul 2010 15:53:25 +0200
parents 7beb12b97911
children 4d229908e78f
files viff/bedoza_triple.py viff/test/test_bedoza_triple.py
diffstat 2 files changed, 141 insertions(+), 119 deletions(-) [+]
line diff
     1.1 --- a/viff/bedoza_triple.py	Thu Jul 22 12:21:19 2010 +0200
     1.2 +++ b/viff/bedoza_triple.py	Thu Jul 22 15:53:25 2010 +0200
     1.3 @@ -146,7 +146,7 @@
     1.4          enc_share = self.paillier.encrypt(share.value)
     1.5          enc_shares = _convolute(self.runtime, enc_share)
     1.6          def create_partial_share(enc_shares, share):
     1.7 -            return PartialShare(self.runtime, value.field, share, enc_shares)
     1.8 +            return PartialShare(self.runtime, self.Zp, share, enc_shares)
     1.9          self.runtime.schedule_callback(enc_shares, create_partial_share, share)
    1.10          return enc_shares
    1.11  
    1.12 @@ -166,9 +166,17 @@
    1.13                                             ri,
    1.14                                             shares[inx],
    1.15                                             N_squared_list)
    1.16 -            
    1.17          return shares
    1.18  
    1.19 +class ShareGenerator(PartialShareGenerator):
    1.20 +
    1.21 +    def __init__(self, Zp, runtime, random, paillier):
    1.22 +        PartialShareGenerator.__init__(self, Zp, runtime, random, paillier)
    1.23 +
    1.24 +    def generate_random_shares(self, n):
    1.25 +        partial_shares = PartialShareGenerator.generate_random_shares(self, n)
    1.26 +
    1.27 +
    1.28  class ModifiedPaillier(object):
    1.29      """A slight modification of the Paillier cryptosystem.
    1.30  
    1.31 @@ -231,6 +239,67 @@
    1.32      def get_modulus_square(self, player_id):
    1.33          return self.runtime.players[player_id].pubkey['n_square']
    1.34  
    1.35 +def add_macs(runtime, field, u_bound, alpha, random, paillier, partial_shares):
    1.36 +    """Adds macs to the set of PartialBeDOZaShares.
    1.37 +        
    1.38 +    Returns a deferred which yields a list of full shares, e.g.
    1.39 +    including macs.  (the full shares are deferreds of type
    1.40 +    BeDOZaShare.)
    1.41 +    """        
    1.42 +    # TODO: Would be nice with a class ShareContents like the class
    1.43 +    # PartialShareContents used here.
    1.44 +        
    1.45 +    runtime.increment_pc() # Huh!?
    1.46 +
    1.47 +    def do_add_macs(partial_share_contents, result_shares):
    1.48 +        num_players = runtime.num_players
    1.49 +        lists_of_mac_keys = [ [] for x in runtime.players ]
    1.50 +        lists_of_c_list = [ [] for x in runtime.players ]
    1.51 +        for partial_share_content in partial_share_contents:
    1.52 +            for j in xrange(0, num_players):
    1.53 +                # TODO: This is probably not the fastes way to generate
    1.54 +                # the betas.
    1.55 +                beta = random.randint(0, u_bound)
    1.56 +                # TODO: Outcommented until mod paillier works for negative numbers.
    1.57 +                # if rand.choice([True, False]):
    1.58 +                #    beta = -beta
    1.59 +                enc_beta = paillier.encrypt(beta, player_id=j + 1)
    1.60 +                c_j = partial_share_content.enc_shares[j]
    1.61 +                n2 = paillier.get_modulus_square(j + 1)
    1.62 +                c = (pow(c_j, alpha, n2) * enc_beta) % n2
    1.63 +                lists_of_c_list[j].append(c)
    1.64 +                lists_of_mac_keys[j].append(field(beta))
    1.65 +
    1.66 +        received_cs = _send(runtime, lists_of_c_list, deserialize=eval)
    1.67 +
    1.68 +        def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
    1.69 +            shares = []               
    1.70 +            for inx in xrange(0, len(partial_share_contents)):
    1.71 +                mac_keys = []
    1.72 +                decrypted_cs = []
    1.73 +                for c_list, mkeys in zip(recevied_cs,
    1.74 +                                         lists_of_mac_keys):
    1.75 +                    decrypted_cs.append(field(paillier.decrypt(c_list[inx])))
    1.76 +                    mac_keys.append(mkeys[inx])
    1.77 +                partial_share = partial_share_contents[inx]
    1.78 +                mac_key_list = BeDOZaKeyList(alpha, mac_keys)
    1.79 +
    1.80 +                mac_msg_list = BeDOZaMACList(decrypted_cs)
    1.81 +                result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
    1.82 +                                                                mac_key_list,
    1.83 +                                                                mac_msg_list))
    1.84 +            return shares
    1.85 +
    1.86 +        runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
    1.87 +        return received_cs
    1.88 +
    1.89 +    result_shares = [Share(runtime, field) for x in xrange(len(partial_shares))]
    1.90 +    runtime.schedule_callback(gatherResults(partial_shares),
    1.91 +                              do_add_macs,
    1.92 +                              result_shares)
    1.93 +    return result_shares
    1.94 +
    1.95 +
    1.96  class TripleGenerator(object):
    1.97  
    1.98      def __init__(self, runtime, p, random):
    1.99 @@ -298,7 +367,7 @@
   1.100          for _ in xrange(n):
   1.101               random_shares.append(gen.generate_share(self.random.randint(0, self.Zp.modulus - 1)))
   1.102  
   1.103 -        random_shares = self._add_macs(random_shares)
   1.104 +        random_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, random_shares)
   1.105  
   1.106          results = [Deferred() for _ in xrange(n)]
   1.107          
   1.108 @@ -336,69 +405,9 @@
   1.109  
   1.110          partial_shares_c = self._full_mul(partial_shares[0:n], partial_shares[n:2*n])
   1.111  
   1.112 -        full_shares = self._add_macs(partial_shares + partial_shares_c)
   1.113 +        full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, partial_shares + partial_shares_c)
   1.114  
   1.115 -        return full_shares
   1.116 -    
   1.117 -    def _add_macs(self, partial_shares):
   1.118 -        """Adds macs to the set of PartialBeDOZaShares.
   1.119 -        
   1.120 -        Returns a deferred which yields a list of full shares, e.g.
   1.121 -        including macs.  (the full shares are deferreds of type
   1.122 -        BeDOZaShare.)
   1.123 -        """        
   1.124 -        # TODO: Would be nice with a class ShareContents like the class
   1.125 -        # PartialShareContents used here.
   1.126 -        
   1.127 -        self.runtime.increment_pc() # Huh!?
   1.128 -
   1.129 -        def do_add_macs(partial_share_contents, result_shares):
   1.130 -            num_players = self.runtime.num_players
   1.131 -            lists_of_mac_keys = [ [] for x in self.runtime.players ]
   1.132 -            lists_of_c_list = [ [] for x in self.runtime.players ]
   1.133 -            for partial_share_content in partial_share_contents:
   1.134 -                for j in xrange(0, num_players):
   1.135 -                    # TODO: This is probably not the fastes way to generate
   1.136 -                    # the betas.
   1.137 -                    beta = self.random.randint(0, self.u_bound)
   1.138 -                    # TODO: Outcommented until mod paillier works for negative numbers.
   1.139 -                    # if rand.choice([True, False]):
   1.140 -                    #    beta = -beta
   1.141 -                    enc_beta = self.paillier.encrypt(beta, player_id=j + 1)
   1.142 -                    c_j = partial_share_content.enc_shares[j]
   1.143 -                    n2 = self.paillier.get_modulus_square(j + 1)
   1.144 -                    c = (pow(c_j, self.alpha, n2) * enc_beta) % n2
   1.145 -                    lists_of_c_list[j].append(c)
   1.146 -                    lists_of_mac_keys[j].append(self.Zp(beta))
   1.147 -
   1.148 -            received_cs = _send(self.runtime, lists_of_c_list, deserialize=eval)
   1.149 -
   1.150 -            def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
   1.151 -                shares = []               
   1.152 -                for inx in xrange(0, len(partial_share_contents)):
   1.153 -                    mac_keys = []
   1.154 -                    decrypted_cs = []
   1.155 -                    for c_list, mkeys in zip(recevied_cs,
   1.156 -                                             lists_of_mac_keys):
   1.157 -                        decrypted_cs.append(self.Zp(self.paillier.decrypt(c_list[inx])))
   1.158 -                        mac_keys.append(mkeys[inx])
   1.159 -                    partial_share = partial_share_contents[inx]
   1.160 -                    mac_key_list = BeDOZaKeyList(self.alpha, mac_keys)
   1.161 -
   1.162 -                    mac_msg_list = BeDOZaMACList(decrypted_cs)
   1.163 -                    result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
   1.164 -                                                                   mac_key_list,
   1.165 -                                                                   mac_msg_list))
   1.166 -                return shares
   1.167 -
   1.168 -            self.runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
   1.169 -            return received_cs
   1.170 -
   1.171 -        result_shares = [Share(self.runtime, self.Zp) for x in xrange(len(partial_shares))]
   1.172 -        self.runtime.schedule_callback(gatherResults(partial_shares),
   1.173 -                                       do_add_macs,
   1.174 -                                       result_shares)
   1.175 -        return result_shares
   1.176 +        return full_shares  
   1.177  
   1.178          # for player i:
   1.179          #     receive c from player i and set 
     2.1 --- a/viff/test/test_bedoza_triple.py	Thu Jul 22 12:21:19 2010 +0200
     2.2 +++ b/viff/test/test_bedoza_triple.py	Thu Jul 22 15:53:25 2010 +0200
     2.3 @@ -32,7 +32,7 @@
     2.4  from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaKeyList
     2.5  
     2.6  from viff.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier, PartialShareGenerator
     2.7 -from viff.bedoza_triple import _send, _convolute, _convolute_gf_elm
     2.8 +from viff.bedoza_triple import _send, _convolute, _convolute_gf_elm, add_macs
     2.9  
    2.10  from viff.field import FieldElement, GF
    2.11  from viff.config import generate_configs
    2.12 @@ -209,7 +209,6 @@
    2.13      gen = PartialShareGenerator(Zp, runtime, share_random, paillier)
    2.14      return gen.generate_random_shares(n)
    2.15  
    2.16 -
    2.17  class ParialShareGeneratorTest(BeDOZaTestCase):
    2.18      num_players = 3
    2.19   
    2.20 @@ -281,11 +280,76 @@
    2.21              
    2.22          return shares
    2.23  
    2.24 +class AddMacsTest(BeDOZaTestCase): 
    2.25 +    num_players = 3
    2.26 +
    2.27 +    timeout = 10
    2.28 +
    2.29 +    @protocol
    2.30 +    def test_add_macs_produces_correct_sharing(self, runtime):
    2.31 +        # TODO: Here we use the open method of the BeDOZa runtime in
    2.32 +        # order to verify the macs of the generated full share. In
    2.33 +        # order to be more unit testish, this test should use its own
    2.34 +        # way of verifying these.
    2.35 +        p = 17
    2.36 +        Zp = GF(p)
    2.37 +        secret = 6
    2.38 +        random = Random(283883)
    2.39 +        paillier_random = Random(random.getrandbits(128))
    2.40 +        paillier = ModifiedPaillier(runtime, random)
    2.41 +
    2.42 +        add_macs_random = Random(random.getrandbits(128))
    2.43 +
    2.44 +        shares_random = Random(random.getrandbits(128))
    2.45 +        shares = []
    2.46 +        shares.append(partial_share(shares_random, runtime, Zp, secret, paillier=paillier))
    2.47 +        shares.append(partial_share(shares_random, runtime, Zp, secret + 1, paillier=paillier))
    2.48 +        shares.append(partial_share(shares_random, runtime, Zp, secret + 2, paillier=paillier))
    2.49 +        shares.append(partial_share(shares_random, runtime, Zp, secret + 3, paillier=paillier))
    2.50 +
    2.51 +        bits_in_p = 5
    2.52 +        u_bound = 2**(4 * bits_in_p)
    2.53 +        alpha = 15
    2.54 +
    2.55 +        zs = add_macs(runtime, Zp, u_bound, alpha,
    2.56 +                      add_macs_random, paillier, shares)
    2.57 +        def verify(open_shares):
    2.58 +            inx = secret
    2.59 +            for open_share in open_shares:
    2.60 +                self.assertEquals(inx, open_share.value)
    2.61 +                inx += 1
    2.62 +
    2.63 +        opened_shares = []
    2.64 +        for s in zs:
    2.65 +            opened_shares.append(runtime.open(s))
    2.66 +        d = gather_shares(opened_shares)
    2.67 +        d.addCallback(verify)
    2.68 +        return d
    2.69 +
    2.70 +        
    2.71 +#    @protocol
    2.72 +#    def test_add_macs_preserves_value_of_sharing(self, runtime):
    2.73 +#        partial_share = self._generate_partial_share_of(42)
    2.74 +#        full_share = TripleGenerator()._add_macs(partial_share)
    2.75 +#        secret = self._open_sharing(full_share)
    2.76 +#        self.assertEquals(42, secret)
    2.77 +#        return partial_share
    2.78 +#    #test_add_macs_preserves_value_of_sharing.skip = "nyi"
    2.79 +#        
    2.80 +#    @protocol
    2.81 +#    def test_add_macs_preserves_value_of_zero_sharing(self, runtime):
    2.82 +#        partial_share = self._generate_partial_share_of(0)
    2.83 +#        full_share = TripleGenerator()._add_macs(partial_share)
    2.84 +#        secret = self._open_sharing(full_share)
    2.85 +#        self.assertEquals(0, secret)
    2.86 +#        return partial_share
    2.87 +#    #test_add_macs_preserves_value_of_zero_sharing.skip = "nyi"
    2.88 +# 
    2.89  
    2.90  class TripleTest(BeDOZaTestCase): 
    2.91      num_players = 3
    2.92  
    2.93 -    timeout = 120
    2.94 +    timeout = 12
    2.95  
    2.96      @protocol
    2.97      def test_generate_triples_generates_correct_triples(self, runtime):
    2.98 @@ -333,57 +397,6 @@
    2.99          d.addCallback(verify)
   2.100          return d
   2.101  
   2.102 -    @protocol
   2.103 -    def test_add_macs_produces_correct_sharing(self, runtime):
   2.104 -        # TODO: Here we use the open method of the BeDOZa runtime in
   2.105 -        # order to verify the macs of the generated full share. In
   2.106 -        # order to be more unit testish, this test should use its own
   2.107 -        # way of verifying these.
   2.108 -        p = 17
   2.109 -        Zp = GF(p)
   2.110 -        secret = 6
   2.111 -        random = Random(283883)        
   2.112 -        triple_generator = TripleGenerator(runtime, p, random)
   2.113 -        paillier = triple_generator.paillier
   2.114 -        shares = []
   2.115 -        shares.append(partial_share(random, runtime, Zp, secret, paillier=paillier))
   2.116 -        shares.append(partial_share(random, runtime, Zp, secret + 1, paillier=paillier))
   2.117 -        shares.append(partial_share(random, runtime, Zp, secret + 2, paillier=paillier))
   2.118 -        shares.append(partial_share(random, runtime, Zp, secret + 3, paillier=paillier))
   2.119 -
   2.120 -        zs = triple_generator._add_macs(shares)
   2.121 -        def verify(open_shares):
   2.122 -            inx = secret
   2.123 -            for open_share in open_shares:
   2.124 -                self.assertEquals(inx, open_share.value)
   2.125 -                inx += 1
   2.126 -        opened_shares = []
   2.127 -        for s in zs:
   2.128 -            opened_shares.append(runtime.open(s))
   2.129 -        d = gather_shares(opened_shares)
   2.130 -        d.addCallback(verify)
   2.131 -        return d
   2.132 -
   2.133 -        
   2.134 -#    @protocol
   2.135 -#    def test_add_macs_preserves_value_of_sharing(self, runtime):
   2.136 -#        partial_share = self._generate_partial_share_of(42)
   2.137 -#        full_share = TripleGenerator()._add_macs(partial_share)
   2.138 -#        secret = self._open_sharing(full_share)
   2.139 -#        self.assertEquals(42, secret)
   2.140 -#        return partial_share
   2.141 -#    #test_add_macs_preserves_value_of_sharing.skip = "nyi"
   2.142 -#        
   2.143 -#    @protocol
   2.144 -#    def test_add_macs_preserves_value_of_zero_sharing(self, runtime):
   2.145 -#        partial_share = self._generate_partial_share_of(0)
   2.146 -#        full_share = TripleGenerator()._add_macs(partial_share)
   2.147 -#        secret = self._open_sharing(full_share)
   2.148 -#        self.assertEquals(0, secret)
   2.149 -#        return partial_share
   2.150 -#    #test_add_macs_preserves_value_of_zero_sharing.skip = "nyi"
   2.151 -# 
   2.152 -
   2.153  class MulTest(BeDOZaTestCase): 
   2.154      num_players = 3
   2.155