# HG changeset patch # User Martin Geisler <[EMAIL PROTECTED]> # Date 1214740058 -7200 # Node ID 9187374f43b8069143f433d0c0d3c73dc5400a15 # Parent 9b48a61e040c8ec5ead21c104502edac9430f87f Two player Paillier based runtime.
This implements a multiplication protocol for two players described here by Claudio Orlandi: http://article.gmane.org/gmane.comp.cryptography.viff.devel/290 diff --git a/viff/paillier.py b/viff/paillier.py --- a/viff/paillier.py +++ b/viff/paillier.py @@ -15,10 +15,13 @@ # You should have received a copy of the GNU Lesser General Public # License along with VIFF. If not, see <http://www.gnu.org/licenses/>. +from twisted.internet.defer import Deferred import gmpy from gmpy import mpz -from viff.util import rand, find_random_prime +from viff.util import rand, find_random_prime, dprint +from viff.runtime import BasicRuntime, Share, increment_pc, gather_shares +from viff.field import GF def L(u, n): return (u-1)/n @@ -52,3 +55,136 @@ numer = L(pow(c, lm, n*n), n) denom = L(pow(g, lm, n*n), n) return (numer*gmpy.invert(denom, n)) % n + + +class PaillierRuntime(BasicRuntime): + + def add_player(self, player, protocol): + BasicRuntime.add_player(self, player, protocol) + if player.id == self.id: + self.player = player + else: + self.peer = player + + @increment_pc + def share(self, inputters, field, number=None): + """Share *number* additively.""" + assert number is None or self.id in inputters + + results = [] + for peer_id in inputters: + if peer_id == self.id: + a = field(rand.randint(0, field.modulus - 1)) + b = number - a + + results.append(Share(self, a.field, a)) + pc = tuple(self.program_counter) + self.protocols[self.peer.id].sendShare(pc, b) + else: + share = self._expect_share(peer_id, field) + results.append(share) + + # Unpack a singleton list. + if len(results) == 1: + return results[0] + else: + return results + + @increment_pc + def open(self, share, receivers=None): + """Open *share* to *receivers* (defaults to both players).""" + + def exchange(a): + pc = tuple(self.program_counter) + self.protocols[self.peer.id].sendShare(pc, a) + result = self._expect_share(self.peer.id, share.field) + result.addCallback(lambda b: a + b) + return result + + result = share.clone() + self.schedule_callback(result, exchange) + return result + + def add(self, share_a, share_b): + """Addition of shares. + + Communication cost: none. + """ + field = getattr(share_a, "field", getattr(share_b, "field", None)) + if not isinstance(share_a, Share): + share_a = Share(self, field, share_a) + if not isinstance(share_b, Share): + share_b = Share(self, field, share_b) + + result = gather_shares([share_a, share_b]) + result.addCallback(lambda (a, b): a + b) + return result + + def mul(self, share_a, share_b): + """Multiplication of shares.""" + field = getattr(share_a, "field", getattr(share_b, "field", None)) + + k = self.options.security_parameter + n = min(self.player.pubkey[0], self.peer.pubkey[0]) + assert field.modulus**2 + 2**k < n, \ + "Need bigger Paillier keys to multiply." + + if not isinstance(share_a, Share): + share_a = Share(self, field, share_a) + if not isinstance(share_b, Share): + share_b = Share(self, field, share_b) + + def finish_mul((a1, b1)): + # The computations are symmetric for P1 and P2, and the + # code uses notation for P1, but the code uses notation as + # seen frmo the perspective of P1. Both players calculate + # + # a1 b1 + a1 b2 + a2 b1 + a2 b2 + # + # but P1 has a zero share of the a2 b2 product and vice + # versa for P2. So the final sum has three parts which are + # additively secret shared like this: + # + # P1: a1 b1 + (a1 b2 + r2) + - r1 + # P2: - r2 + (a2 b1 + r1) + a2 b2 + + pc = tuple(self.program_counter) + send_share = self.protocols[self.peer.id].sendShare + send_data = self.protocols[self.peer.id].sendData + + # Our part of the sum which needs not be shared. + a1_b1 = a1 * b1 + + # Encrypt and send our sharing to our peer. + enc_a1 = encrypt(a1.value, self.player.pubkey) + send_data(pc, "paillier", enc_a1) + # and receive an encryption too. + enc_a2 = Deferred() + self._expect_data(self.peer.id, "paillier", enc_a2) + + nsq = self.peer.pubkey[0]**2 + + # Multiply a2 with b1 inside the encryption. + enc_a2_b1 = enc_a2.addCallback(pow, b1.value, nsq) + + # Chose and add r1 inside the encryption. + r1 = rand.randint(0, field.modulus**2 + 2**k) + + enc_r1 = encrypt(r1, self.peer.pubkey) + enc_a2_b1_r1 = enc_a2_b1.addCallback(lambda c: (c * enc_r1) % nsq) + enc_a2_b1_r1.addCallback(lambda c: send_data(pc, "paillier", c)) + + # Now receive E(a1 b2 + r2) from the peer. + enc_a1_b2_r2 = Share(self, field) + self._expect_data(self.peer.id, "paillier", enc_a1_b2_r2) + a1_b2_r2 = enc_a1_b2_r2.addCallback(decrypt, self.player.seckey) + # Convert the received value from mpz to GFElement. + a1_b2_r2.addCallback(long) + a1_b2_r2.addCallback(field) + + res = a1_b2_r2.addCallback(lambda a1_b2_r2: a1_b1 + a1_b2_r2 - r1) + return res + + result = gather_shares([share_a, share_b]) + result.addCallback(finish_mul) + return result _______________________________________________ viff-patches mailing list [email protected] http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
