changeset 838:bba8a625972a

Two-player runtime based on Paillier encryption. This implements a multiplication protocol for two players described here by Claudio Orlandi: http://article.gmane.org/gmane.comp.cryptography.viff.devel/290 The key ingredient is the homomorphic Paillier encryption scheme.
author Martin Geisler <mg@daimi.au.dk>
date Tue, 15 Jul 2008 23:35:59 +0200
parents 99dc1bb4cddf
children 45dfc10a1363
files viff/paillier.py
diffstat 1 files changed, 126 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/viff/paillier.py	Sat Jun 21 13:02:57 2008 +0200
+++ b/viff/paillier.py	Tue Jul 15 23:35:59 2008 +0200
@@ -15,9 +15,12 @@
 # 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, gatherResults
 import gmpy
 
+from viff.runtime import BasicRuntime, increment_pc, Share, gather_shares
 from viff.util import rand, find_random_prime
+from viff.field import GF
 
 def L(u, n):
     return (u-1)/n
@@ -51,3 +54,126 @@
     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((a, b)):
+            pc = tuple(self.program_counter)
+            send_data = self.protocols[self.peer.id].sendData
+
+            if hash(pc) % 2 == self.id:
+                # We play the role of P1.
+                a1, b1 = a, b
+                enc_a1 = encrypt(a1.value, self.player.pubkey)
+                enc_b1 = encrypt(b1.value, self.player.pubkey)
+                send_data(pc, "paillier", enc_a1)
+                send_data(pc, "paillier", enc_b1)
+
+                enc_c1 = Share(self, field)
+                self._expect_data(self.peer.id, "paillier", enc_c1)
+                c1 = enc_c1.addCallback(decrypt, self.player.seckey)
+                c1.addCallback(lambda c: long(c) + a1 * b1)
+                return c1
+            else:
+                # We play the role of P2.
+                a2, b2 = a, b
+                enc_a1 = Deferred()
+                self._expect_data(self.peer.id, "paillier", enc_a1)
+                enc_b1 = Deferred()
+                self._expect_data(self.peer.id, "paillier", enc_b1)
+
+                nsq = self.peer.pubkey[0]**2
+                # Calculate a1 * b2 and b1 * a2 inside the encryption.
+                enc_a1_b2 = enc_a1.addCallback(pow, b2.value, nsq)
+                enc_b1_a2 = enc_b1.addCallback(pow, a2.value, nsq)
+
+                # Chose and encrypt r.
+                r = rand.randint(0, 2 * field.modulus**2 + 2**k)
+                enc_r = encrypt(r, self.peer.pubkey)
+
+                c1 = gatherResults([enc_a1_b2, enc_b1_a2])
+                c1.addCallback(lambda (a,b): a * b * enc_r)
+                c1.addCallback(lambda c: send_data(pc, "paillier", c))
+
+                c2 = a2 * b2 - r
+                return Share(self, field, c2)
+
+        result = gather_shares([share_a, share_b])
+        result.addCallback(finish_mul)
+        return result