changeset 1491:5daa155c1d0b

BeDOZa: Partial implementation of triple generation for the BeDOZa protocol.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed, 14 Jul 2010 13:32:10 +0200
parents e837d8eec15d
children 3627b0e969c9
files viff/bedoza_triple.py viff/test/test_bedoza_triple.py
diffstat 2 files changed, 578 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza_triple.py	Wed Jul 14 13:32:10 2010 +0200
@@ -0,0 +1,287 @@
+# Copyright 2010 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+"""Triple generation for the BeDOZa protocol.
+    TODO: Explain more.
+"""
+
+from twisted.internet.defer import Deferred, gatherResults, succeed
+
+from viff.runtime import Runtime, Share, ShareList, gather_shares
+from viff.field import FieldElement, GF
+from viff.constants import TEXT
+from viff.simplearithmetic import SimpleArithmetic
+from viff.util import rand
+
+from bedoza import BeDOZaKeyList, BeDOZaMessageList, BeDOZaShare
+
+# TODO: Use secure random instead!
+from random import Random
+
+from hash_broadcast import HashBroadcastMixin
+
+try:
+    import pypaillier
+except ImportError:
+    # The pypaillier module is not released yet, so we cannot expect
+    # the import to work.
+    print "Error: The pypaillier module or one of the used functions " \
+        "are not available."
+
+class Triple(object):
+    def __init__(self, a, b, c):
+        self.a, self.b, self.c = a, b, c
+    def __str__(self):
+        return "(%s,%s,%s)" % (self.a, self.b, self.c)
+
+
+def _send(runtime, vals, serialize=str, deserialize=int):
+    """Send vals[i] to player i + 1. Returns deferred list.
+
+    Works as default for integers. If other stuff has to be
+    sent, supply another serialization, deserialition.
+    """
+    pc = tuple(runtime.program_counter)
+    for p in runtime.players:
+        msg = serialize(vals[p - 1])
+        runtime.protocols[p].sendData(pc, TEXT, msg)
+    def err_handler(err):
+        print err
+    values = []
+    for p in runtime.players:
+        d = Deferred()
+        d.addCallbacks(deserialize, err_handler)
+        runtime._expect_data(p, TEXT, d)
+        values.append(d)
+    result = gatherResults(values)
+    return result
+
+def _convolute(runtime, val, serialize=str, deserialize=int):
+    """As send, but sends the same val to all players."""
+    return _send(runtime, [val] * runtime.num_players,
+                 serialize=serialize, deserialize=deserialize)
+
+def _convolute_gf_elm(runtime, gf_elm):
+    return _convolute(runtime, gf_elm,
+                      serialize=lambda x: str(x.value),
+                      deserialize=lambda x: gf_elm.field(int(x)))
+
+def _send_gf_elm(runtime, vals):
+    return _send(runtime, vals, 
+                 serialize=lambda x: str(x.value),
+                 deserialize=lambda x: gf_elm.field(int(x)))
+
+
+
+
+class PartialShareContents(object):
+    """A BeDOZa share without macs, e.g. < a >.
+    TODO: BeDOZaShare should extend this class?
+    
+    TODO: Should the partial share contain the public encrypted shares?
+    TODO: It may be wrong to pass encrypted_shares to super constructor; 
+      does it mean that the already public values get passed along on the
+      network even though all players already posess them?
+    """
+    def __init__(self, value, enc_shares):
+        self.value = value
+        self.enc_shares = enc_shares
+
+    def __str__(self):
+        return "PartialShareContents(%d; %s)" % (self.value, self.enc_shares)
+
+# In VIFF, callbacks get the *contents* of a share as input. Hence, in order
+# to get a PartialShare as input to callbacks, we need this extra level of
+# wrapper indirection.
+class PartialShare(Share):
+    def __init__(self, runtime, value, enc_shares):
+        partial_share_contents = PartialShareContents(value, enc_shares)
+        Share.__init__(self, runtime, value.field, partial_share_contents)
+
+
+
+class ModifiedPaillier(object):
+    """See Ivan's paper, beginning of section 6."""
+
+    def __init__(self, runtime, random):
+        self.runtime = runtime;
+        self.random = random
+
+    def encrypt(self, value, player_id=None):
+        """Encrypt using public key of player player_id. Defaults to own public key."""
+        assert isinstance(value, int), \
+            "paillier encrypts only integers, got %s" % value.__class__        
+        # TODO: Assert value in the right range.
+        
+        if not player_id:
+            player_id = self.runtime.id
+
+        pubkey = self.runtime.players[player_id].pubkey
+
+        randomness = self.random.randint(1, long(pubkey['n']))
+        # TODO: Transform value.
+        enc = pypaillier.encrypt_r(value, randomness, pubkey)
+        return enc
+
+    def decrypt(self, enc_value):
+        """Decrypt using own private key."""
+        assert isinstance(enc_value, long), \
+            "paillier decrypts only longs, got %s" % enc_value.__class__
+        # TODO: Assert enc_value in the right range.
+        seckey = self.runtime.players[self.runtime.id].seckey
+        return pypaillier.decrypt(enc_value, seckey)
+
+
+class TripleGenerator(object):
+
+    def __init__(self, runtime, p, random):
+        assert p > 1
+        self.random = random
+        # TODO: Generate Paillier cipher with N_i sufficiently larger than p
+        self.runtime = runtime
+        self.p = p
+        self.Zp = GF(p)
+        self.k = self._bit_length_of(p)
+
+        paillier_random = Random(self.random.getrandbits(128))
+        alpha_random = Random(self.random.getrandbits(128))
+        self.paillier = ModifiedPaillier(runtime, paillier_random)
+        
+        # Debug output.
+        #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
+        #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
+        #print "n_%d bitlength: %d" % (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
+
+        #self.Zp = GF(p)
+        #self.Zn2 = GF(self.paillier.pubkey['n_square'])
+        #self.alpha = self.Zp(self.random.randint(0, p - 1))
+        self.alpha = alpha_random.randint(0, p - 1)
+        self.n2 = runtime.players[runtime.id].pubkey['n_square']
+
+    def _bit_length_of(self, i):
+        bit_length = 0
+        while i:
+            i >>= 1
+            bit_length += 1
+        return bit_length
+
+    def generate_triples(self, n):
+        """Generates and returns a set of n triples.
+        
+        Data sent over the network is packaged in large hunks in order
+        to optimize. TODO: Explain better.
+
+        TODO: This method needs to have enough RAM to represent all n
+        triples in memory at the same time. Is there a nice way to
+        stream this, e.g. by using Python generators?
+        """
+        triples = self._generate_passive_triples(n)
+        # TODO: Do some ZK stuff.
+
+    def _generate_passive_triples(self, n):
+        """Generates and returns a set of n passive tuples.
+        
+        E.g. where consistency is only guaranteed if all players follow the
+        protool.
+        """
+        pass
+    
+    def _add_macs(self, partial_shares):
+        """Adds macs to the set of PartialBeDOZaShares.
+        
+        Returns a list of full shares, e.g. including macs.
+        (the full shares are deferreds of type BeDOZaShare.)
+        """
+        
+        # TODO: Currently only does this for one partial share.
+
+        # TODO: Would be nice with a class ShareContents like the class
+        # PartialShareContents used here.
+        
+        self.runtime.increment_pc() # Huh!?
+
+        mac_keys = []
+
+        i = 0
+
+        c_list = []
+        for j in range(self.runtime.num_players):
+            # TODO: This is probably not the fastes way to generate
+            # the betas.
+            beta = self.random.randint(0, 2**(4 * self.k))
+        
+            # TODO: Outcommented until mod paillier works for negative numbers.
+            #if rand.choice([True, False]):
+            #    beta = -beta
+            
+            enc_beta = self.paillier.encrypt(beta, player_id=j+1)
+            c_j = partial_shares[i].enc_shares[j]
+            c = (pow(c_j, self.alpha, self.n2) * enc_beta) % self.n2
+            if self.runtime.id == 1 and j + 1 == 2:
+                print
+                print
+                print "p=", self.p
+                print "player 1: public key of player %s is %s" % (j+1, 
+                                                                   self.runtime.players[j+1].pubkey)
+                print "player %s encrypted share: %s" % (j+1, partial_shares[i].enc_shares[j])
+                print "alpha = %s = %s" % (self.alpha, self.Zp(self.alpha))
+                print "beta = %s = %s" %  (beta, self.Zp(beta))
+                print "enc_beta =", enc_beta
+                print "Player 1 sends c = %s to player %d" % (c, j+1)
+                print
+                print
+            c_list.append(c)
+            mac_keys.append(self.Zp(beta))
+        received_cs = _send(self.runtime, c_list)
+
+        def finish_sharing(recevied_cs):
+            mac_key_list = BeDOZaKeyList(self.alpha, mac_keys)
+            # print "received cs:", received_cs.result
+            decrypted_cs = [self.Zp(self.paillier.decrypt(c)) for c in received_cs.result]
+            if self.runtime.id == 2:
+                print
+                print
+                print "PLAYER2: Got %s from player 1" % received_cs.result[0]
+                print "PLAYER2: Decrypted c from player 1: %s" % decrypted_cs[0]
+                print "PLAYER2: My share a_2 =", partial_shares[0].value
+                print
+
+            mac_msg_list = BeDOZaMessageList(decrypted_cs)
+            # Twisted HACK: Need to pack share into tuple.
+            return BeDOZaShare(self.runtime,
+                               partial_shares[i].value.field,
+                               partial_shares[i].value,
+                               mac_key_list,
+                               mac_msg_list),
+
+        self.runtime.schedule_callback(received_cs, finish_sharing)
+        return [received_cs]
+
+        # for player i:
+        #     receive c from player i and set 
+        #         m^i=Decrypt(c)
+    
+    def _mul(self):
+        pass
+    
+    def _full_mul(self):
+        pass
+
+
+# TODO: Represent all numbers by GF objects, Zp, Zn, etc.
+# E.g. paillier encrypt should return Zn^2 elms and decrypt should
+# return Zp elements.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/test/test_bedoza_triple.py	Wed Jul 14 13:32:10 2010 +0200
@@ -0,0 +1,291 @@
+# Copyright 2010 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+import sys
+
+# We don't need secure random numbers for test purposes.
+from random import Random
+
+from twisted.internet.defer import gatherResults, Deferred, DeferredList
+
+from viff.test.util import RuntimeTestCase, protocol
+from viff.constants import TEXT
+from viff.runtime import gather_shares, Share
+from viff.config import generate_configs
+from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaKeyList, BeDOZaMessageList
+
+from viff.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier
+from viff.bedoza_triple import _send, _convolute, _convolute_gf_elm
+
+from viff.field import FieldElement, GF
+from viff.config import generate_configs
+
+
+# Ok to use non-secure random generator in tests.
+#from viff.util import rand
+import random
+
+# The PyPaillier and commitment packages are not standard parts of VIFF so we
+# skip them instead of letting them fail if the packages are not available. 
+try:
+    import pypaillier
+except ImportError:
+    pypaillier = None
+
+# HACK: The paillier keys that are available as standard in VIFF tests
+# are not suited for use with pypaillier. Hence, we use NaClPaillier
+# to generate test keys. This confusion will disappear when pypaillier
+# replaces the current Python-based paillier implementation.
+from viff.paillierutil import NaClPaillier
+
+# HACK^2: Currently, the NaClPaillier hack only works when triple is
+# imported. It should ideally work without the triple package.
+try:
+    import tripple
+except ImportError:
+    tripple = None
+
+
+
+def _log(rt, msg):
+    print "player%d ------> %s" % (rt.id, msg)
+
+
+# TODO: Code duplication. There should be only one share generator, it should
+# be placed along with the tests, and it should be able to generate partial
+# as well as full bedoza shares.
+class PartialShareGenerator:
+
+    def __init__(self, Zp, runtime, random, paillier):
+        self.paillier = paillier
+        self.Zp = Zp
+        self.runtime = runtime
+        self.random = random
+
+    def generate_share(self, value):
+        r = [self.Zp(self.random.randint(0, self.Zp.modulus - 1)) # TODO: Exclusve?
+             for _ in range(self.runtime.num_players - 1)]
+        if self.runtime.id == 1:
+            share = value - sum(r)
+        else:
+            share = r[self.runtime.id - 2]
+        enc_share = self.paillier.encrypt(share.value)
+        enc_shares = _convolute(self.runtime, enc_share)
+        def create_partial_share(enc_shares, share):
+            return PartialShare(self.runtime, share, enc_shares)
+        self.runtime.schedule_callback(enc_shares, create_partial_share, share)
+        return enc_shares
+
+class BeDOZaTestCase(RuntimeTestCase):
+
+    runtime_class = BeDOZaRuntime
+
+    # TODO: During test, we would like generation of Paillier keys to
+    # be deterministic. How do we obtain that?
+    def generate_configs(self, *args):
+        # In production, paillier keys should be something like 2000
+        # bit. For test purposes, it is ok to use small keys.
+        # TODO: paillier freezes if key size is too small, e.g. 13.
+        return generate_configs(paillier=NaClPaillier(70), *args)
+
+
+class DataTransferTest(BeDOZaTestCase):
+    num_players = 3
+
+    @protocol
+    def test_convolute_int(self, runtime):
+        res = _convolute(runtime, runtime.id)
+        def verify(result):
+            self.assertEquals(runtime.players.keys(), result)
+        runtime.schedule_callback(res, verify)
+        return res
+
+    @protocol
+    def test_send(self, runtime):
+        msg_send = [100 * p + runtime.id for p in runtime.players]
+        msg_receive = [100 * runtime.id + p for p in runtime.players]
+        res = _send(runtime, msg_send)
+        def verify(result):
+            self.assertEquals(msg_receive, result)
+        runtime.schedule_callback(res, verify)
+        return res
+ 
+    @protocol
+    def test_convolute_field_element(self, runtime):
+        Zp = GF(17)
+        res = _convolute_gf_elm(runtime, Zp(runtime.id))
+        def verify(result):
+            self.assertEquals(runtime.players.keys(), result)
+        runtime.schedule_callback(res, verify)
+        return res
+
+
+class ModifiedPaillierTest(BeDOZaTestCase):
+    num_players = 3
+
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_one(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(234838))
+        val = 1
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
+ 
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_positive(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(777737))
+        val = 7
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
+
+    @protocol
+    def test_modified_paillier_can_encrypt_to_other(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(57503))
+        msg = []
+        for p in runtime.players:
+            msg.append(paillier.encrypt(runtime.id, player_id=p))
+        received = _send(runtime, msg)
+        def verify(enc):
+            plain = [paillier.decrypt(e) for e in enc]
+            self.assertEquals(range(1, self.num_players + 1), plain)
+        runtime.schedule_callback(received, verify)
+        return received
+        
+
+#    @protocol
+#    def test_modified_paillier_can_decrypt_encrypted_negative(self, runtime):
+#        pass
+
+    # TODO: Boundary tests.
+
+def partial_share(random, runtime, Zp, val, paillier=None):
+    if not paillier:
+        paillier_random = Random(random.getrandbits(128))
+        paillier = ModifiedPaillier(runtime, paillier_random)
+    share_random = Random(random.getrandbits(128))
+    gen = PartialShareGenerator(Zp, runtime, share_random, paillier)
+    return gen.generate_share(Zp(val))
+
+
+class ParialShareGeneratorTest(BeDOZaTestCase):
+    num_players = 3
+ 
+    @protocol
+    def test_shares_have_correct_type(self, runtime):
+        Zp = GF(23)
+        share = partial_share(Random(23499), runtime, Zp, 7)
+        def test(share):
+            self.assertEquals(Zp, share.value.field)
+        runtime.schedule_callback(share, test)
+        return share
+ 
+    @protocol
+    def test_shares_are_additive(self, runtime):
+        secret = 7
+        share = partial_share(Random(34993), runtime, GF(23), secret)
+        def convolute(share):
+            values = _convolute_gf_elm(runtime, share.value)
+            def test_sum(vals):
+                self.assertEquals(secret, sum(vals))
+            runtime.schedule_callback(values, test_sum)
+        runtime.schedule_callback(share, convolute)
+        return share
+
+
+    @protocol
+    def test_encrypted_shares_decrypt_correctly(self, runtime):
+        random = Random(3423993)
+        modulus = 17
+        secret = 7
+        paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
+        share = partial_share(Random(random.getrandbits(128)), runtime, GF(modulus), secret, paillier=paillier)
+        def decrypt(share):
+            decrypted_share = paillier.decrypt(share.enc_shares[runtime.id - 1])
+            decrypted_shares = _convolute(runtime, decrypted_share)
+            def test_sum(vals):
+                self.assertEquals(secret, sum(vals) % modulus)
+            runtime.schedule_callback(decrypted_shares, test_sum)
+        runtime.schedule_callback(share, decrypt)
+        return share
+
+
+class TripleTest(BeDOZaTestCase): 
+    num_players = 3
+    
+    @protocol
+    def test_add_macs_produces_correct_sharing(self, runtime):
+        # TODO: Here we use the open method of the BeDOZa runtime in
+        # order to verify the macs of the generated full share. In
+        # order to be more unit testish, this test should use its own
+        # way of verifying these.
+        p = 17
+        secret = 9
+        random = Random(283883)        
+        triple_generator = TripleGenerator(runtime, p, random)
+        paillier = triple_generator.paillier
+        share = partial_share(random, runtime, GF(p), secret, paillier=paillier)
+        def add_macs(share):
+            full_share_list = triple_generator._add_macs([share])
+            d = gatherResults(full_share_list)
+            def foo(ls):
+                # Twisted HACK: Need to unpack value ls[0] from tuple.
+                opened_share = runtime.open(ls[0][0])
+                def verify(open_share):
+                    print "Share opened:", open_share
+                    self.assertEquals(secret, open_share.value)
+                runtime.schedule_callback(opened_share, verify)
+                return opened_share
+            d.addCallback(foo)
+            return d
+        runtime.schedule_callback(share, add_macs)
+        return share
+
+    test_add_macs_produces_correct_sharing.skip = "add_macs not implemented fully yet"
+
+        
+#    @protocol
+#    def test_add_macs_preserves_value_of_sharing(self, runtime):
+#        partial_share = self._generate_partial_share_of(42)
+#        full_share = TripleGenerator()._add_macs(partial_share)
+#        secret = self._open_sharing(full_share)
+#        self.assertEquals(42, secret)
+#        return partial_share
+#    #test_add_macs_preserves_value_of_sharing.skip = "nyi"
+#        
+#    @protocol
+#    def test_add_macs_preserves_value_of_zero_sharing(self, runtime):
+#        partial_share = self._generate_partial_share_of(0)
+#        full_share = TripleGenerator()._add_macs(partial_share)
+#        secret = self._open_sharing(full_share)
+#        self.assertEquals(0, secret)
+#        return partial_share
+#    #test_add_macs_preserves_value_of_zero_sharing.skip = "nyi"
+# 
+
+missing_package = None
+if not pypaillier:
+    missing_package = "pypaillier"
+if not tripple:
+    missing_package = "tripple"
+if missing_package:
+    test_cases = [ModifiedPaillierTest,
+                  PartialShareGeneratorTest,
+                  TripleTest
+                  ]
+    for test_case in test_cases:
+        test_case.skip =  "Skipped due to missing %s package." % missing_package