## viff

### 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 Tue, 15 Jul 2008 23:35:59 +0200 99dc1bb4cddf 45dfc10a1363 viff/paillier.py 1 files changed, 126 insertions(+), 0 deletions(-) [+]
line diff
```     1.1 --- a/viff/paillier.py	Sat Jun 21 13:02:57 2008 +0200
1.2 +++ b/viff/paillier.py	Tue Jul 15 23:35:59 2008 +0200
1.3 @@ -15,9 +15,12 @@
1.4  # You should have received a copy of the GNU Lesser General Public
1.6
1.7 +from twisted.internet.defer import Deferred, gatherResults
1.8  import gmpy
1.9
1.10 +from viff.runtime import BasicRuntime, increment_pc, Share, gather_shares
1.11  from viff.util import rand, find_random_prime
1.12 +from viff.field import GF
1.13
1.14  def L(u, n):
1.15      return (u-1)/n
1.16 @@ -51,3 +54,126 @@
1.17      numer = L(pow(c, lm, n*n), n)
1.18      denom = L(pow(g, lm, n*n), n)
1.19      return (numer*gmpy.invert(denom, n)) % n
1.20 +
1.21 +
1.22 +class PaillierRuntime(BasicRuntime):
1.23 +
1.24 +    def add_player(self, player, protocol):
1.26 +        if player.id == self.id:
1.27 +            self.player = player
1.28 +        else:
1.29 +            self.peer = player
1.30 +
1.31 +    @increment_pc
1.32 +    def share(self, inputters, field, number=None):
1.34 +        assert number is None or self.id in inputters
1.35 +
1.36 +        results = []
1.37 +        for peer_id in inputters:
1.38 +            if peer_id == self.id:
1.39 +                a = field(rand.randint(0, field.modulus - 1))
1.40 +                b = number - a
1.41 +
1.42 +                results.append(Share(self, a.field, a))
1.43 +                pc = tuple(self.program_counter)
1.44 +                self.protocols[self.peer.id].sendShare(pc, b)
1.45 +            else:
1.46 +                share = self._expect_share(peer_id, field)
1.47 +                results.append(share)
1.48 +
1.49 +        # Unpack a singleton list.
1.50 +        if len(results) == 1:
1.51 +            return results[0]
1.52 +        else:
1.53 +            return results
1.54 +
1.55 +    @increment_pc
1.56 +    def open(self, share, receivers=None):
1.57 +        """Open *share* to *receivers* (defaults to both players)."""
1.58 +
1.59 +        def exchange(a):
1.60 +            pc = tuple(self.program_counter)
1.61 +            self.protocols[self.peer.id].sendShare(pc, a)
1.62 +            result = self._expect_share(self.peer.id, share.field)
1.63 +            result.addCallback(lambda b: a + b)
1.64 +            return result
1.65 +
1.66 +        result = share.clone()
1.67 +        self.schedule_callback(result, exchange)
1.68 +        return result
1.69 +
1.70 +    def add(self, share_a, share_b):
1.72 +
1.73 +        Communication cost: none.
1.74 +        """
1.75 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
1.76 +        if not isinstance(share_a, Share):
1.77 +            share_a = Share(self, field, share_a)
1.78 +        if not isinstance(share_b, Share):
1.79 +            share_b = Share(self, field, share_b)
1.80 +
1.81 +        result = gather_shares([share_a, share_b])
1.82 +        result.addCallback(lambda (a, b): a + b)
1.83 +        return result
1.84 +
1.85 +    def mul(self, share_a, share_b):
1.86 +        """Multiplication of shares."""
1.87 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
1.88 +
1.89 +        k = self.options.security_parameter
1.90 +        n = min(self.player.pubkey[0], self.peer.pubkey[0])
1.91 +        assert field.modulus**2 + 2**k < n, \
1.92 +            "Need bigger Paillier keys to multiply."
1.93 +
1.94 +        if not isinstance(share_a, Share):
1.95 +            share_a = Share(self, field, share_a)
1.96 +        if not isinstance(share_b, Share):
1.97 +            share_b = Share(self, field, share_b)
1.98 +
1.99 +        def finish_mul((a, b)):
1.100 +            pc = tuple(self.program_counter)
1.101 +            send_data = self.protocols[self.peer.id].sendData
1.102 +
1.103 +            if hash(pc) % 2 == self.id:
1.104 +                # We play the role of P1.
1.105 +                a1, b1 = a, b
1.106 +                enc_a1 = encrypt(a1.value, self.player.pubkey)
1.107 +                enc_b1 = encrypt(b1.value, self.player.pubkey)
1.108 +                send_data(pc, "paillier", enc_a1)
1.109 +                send_data(pc, "paillier", enc_b1)
1.110 +
1.111 +                enc_c1 = Share(self, field)
1.112 +                self._expect_data(self.peer.id, "paillier", enc_c1)
1.113 +                c1 = enc_c1.addCallback(decrypt, self.player.seckey)
1.114 +                c1.addCallback(lambda c: long(c) + a1 * b1)
1.115 +                return c1
1.116 +            else:
1.117 +                # We play the role of P2.
1.118 +                a2, b2 = a, b
1.119 +                enc_a1 = Deferred()
1.120 +                self._expect_data(self.peer.id, "paillier", enc_a1)
1.121 +                enc_b1 = Deferred()
1.122 +                self._expect_data(self.peer.id, "paillier", enc_b1)
1.123 +
1.124 +                nsq = self.peer.pubkey[0]**2
1.125 +                # Calculate a1 * b2 and b1 * a2 inside the encryption.
1.126 +                enc_a1_b2 = enc_a1.addCallback(pow, b2.value, nsq)
1.127 +                enc_b1_a2 = enc_b1.addCallback(pow, a2.value, nsq)
1.128 +
1.129 +                # Chose and encrypt r.
1.130 +                r = rand.randint(0, 2 * field.modulus**2 + 2**k)
1.131 +                enc_r = encrypt(r, self.peer.pubkey)
1.132 +
1.133 +                c1 = gatherResults([enc_a1_b2, enc_b1_a2])
1.134 +                c1.addCallback(lambda (a,b): a * b * enc_r)
1.135 +                c1.addCallback(lambda c: send_data(pc, "paillier", c))
1.136 +
1.137 +                c2 = a2 * b2 - r
1.138 +                return Share(self, field, c2)
1.139 +
1.140 +        result = gather_shares([share_a, share_b])