viff

view viff/paillier.py @ 838:bba8a625972a

find changesets by author, revision, files, or words in the commit message
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 Jul 15 23:35:59 2008 +0200 (3 years ago)
parents 0422fa73ab29
children f7e987afbec3
line source
1 # Copyright 2008 VIFF Development Team.
2 #
3 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
4 #
5 # VIFF is free software: you can redistribute it and/or modify it
6 # under the terms of the GNU Lesser General Public License (LGPL) as
7 # published by the Free Software Foundation, either version 3 of the
8 # License, or (at your option) any later version.
9 #
10 # VIFF is distributed in the hope that it will be useful, but WITHOUT
11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 # Public License for more details.
14 #
15 # You should have received a copy of the GNU Lesser General Public
16 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
17
18 from twisted.internet.defer import Deferred, gatherResults
19 import gmpy
20
21 from viff.runtime import BasicRuntime, increment_pc, Share, gather_shares
22 from viff.util import rand, find_random_prime
23 from viff.field import GF
24
25 def L(u, n):
26 return (u-1)/n
27
28 def generate_keys(bit_length):
29 # Make an RSA modulus n.
30 p = find_random_prime(bit_length/2)
31 while True:
32 q = find_random_prime(bit_length/2)
33 if p<>q: break
34
35 n = p*q
36 nsq = n*n
37
38 # Calculate Carmichael's function.
39 lm = gmpy.lcm(p-1, q-1)
40
41 # Generate a generator g in B.
42 while True:
43 g = rand.randint(1, long(nsq))
44 if gmpy.gcd(L(pow(g, lm, nsq), n), n) == 1: break
45
46 return (n, g), (n, g, lm)
47
48 def encrypt(m, (n, g)):
49 r = rand.randint(1, long(n))
50 nsq = n*n
51 return (pow(g, m, nsq)*pow(r, n, nsq)) % nsq
52
53 def decrypt(c, (n, g, lm)):
54 numer = L(pow(c, lm, n*n), n)
55 denom = L(pow(g, lm, n*n), n)
56 return (numer*gmpy.invert(denom, n)) % n
57
58
59 class PaillierRuntime(BasicRuntime):
60
61 def add_player(self, player, protocol):
62 BasicRuntime.add_player(self, player, protocol)
63 if player.id == self.id:
64 self.player = player
65 else:
66 self.peer = player
67
68 @increment_pc
69 def share(self, inputters, field, number=None):
70 """Share *number* additively."""
71 assert number is None or self.id in inputters
72
73 results = []
74 for peer_id in inputters:
75 if peer_id == self.id:
76 a = field(rand.randint(0, field.modulus - 1))
77 b = number - a
78
79 results.append(Share(self, a.field, a))
80 pc = tuple(self.program_counter)
81 self.protocols[self.peer.id].sendShare(pc, b)
82 else:
83 share = self._expect_share(peer_id, field)
84 results.append(share)
85
86 # Unpack a singleton list.
87 if len(results) == 1:
88 return results[0]
89 else:
90 return results
91
92 @increment_pc
93 def open(self, share, receivers=None):
94 """Open *share* to *receivers* (defaults to both players)."""
95
96 def exchange(a):
97 pc = tuple(self.program_counter)
98 self.protocols[self.peer.id].sendShare(pc, a)
99 result = self._expect_share(self.peer.id, share.field)
100 result.addCallback(lambda b: a + b)
101 return result
102
103 result = share.clone()
104 self.schedule_callback(result, exchange)
105 return result
106
107 def add(self, share_a, share_b):
108 """Addition of shares.
109
110 Communication cost: none.
111 """
112 field = getattr(share_a, "field", getattr(share_b, "field", None))
113 if not isinstance(share_a, Share):
114 share_a = Share(self, field, share_a)
115 if not isinstance(share_b, Share):
116 share_b = Share(self, field, share_b)
117
118 result = gather_shares([share_a, share_b])
119 result.addCallback(lambda (a, b): a + b)
120 return result
121
122 def mul(self, share_a, share_b):
123 """Multiplication of shares."""
124 field = getattr(share_a, "field", getattr(share_b, "field", None))
125
126 k = self.options.security_parameter
127 n = min(self.player.pubkey[0], self.peer.pubkey[0])
128 assert field.modulus**2 + 2**k < n, \
129 "Need bigger Paillier keys to multiply."
130
131 if not isinstance(share_a, Share):
132 share_a = Share(self, field, share_a)
133 if not isinstance(share_b, Share):
134 share_b = Share(self, field, share_b)
135
136 def finish_mul((a, b)):
137 pc = tuple(self.program_counter)
138 send_data = self.protocols[self.peer.id].sendData
139
140 if hash(pc) % 2 == self.id:
141 # We play the role of P1.
142 a1, b1 = a, b
143 enc_a1 = encrypt(a1.value, self.player.pubkey)
144 enc_b1 = encrypt(b1.value, self.player.pubkey)
145 send_data(pc, "paillier", enc_a1)
146 send_data(pc, "paillier", enc_b1)
147
148 enc_c1 = Share(self, field)
149 self._expect_data(self.peer.id, "paillier", enc_c1)
150 c1 = enc_c1.addCallback(decrypt, self.player.seckey)
151 c1.addCallback(lambda c: long(c) + a1 * b1)
152 return c1
153 else:
154 # We play the role of P2.
155 a2, b2 = a, b
156 enc_a1 = Deferred()
157 self._expect_data(self.peer.id, "paillier", enc_a1)
158 enc_b1 = Deferred()
159 self._expect_data(self.peer.id, "paillier", enc_b1)
160
161 nsq = self.peer.pubkey[0]**2
162 # Calculate a1 * b2 and b1 * a2 inside the encryption.
163 enc_a1_b2 = enc_a1.addCallback(pow, b2.value, nsq)
164 enc_b1_a2 = enc_b1.addCallback(pow, a2.value, nsq)
165
166 # Chose and encrypt r.
167 r = rand.randint(0, 2 * field.modulus**2 + 2**k)
168 enc_r = encrypt(r, self.peer.pubkey)
169
170 c1 = gatherResults([enc_a1_b2, enc_b1_a2])
171 c1.addCallback(lambda (a,b): a * b * enc_r)
172 c1.addCallback(lambda c: send_data(pc, "paillier", c))
173
174 c2 = a2 * b2 - r
175 return Share(self, field, c2)
176
177 result = gather_shares([share_a, share_b])
178 result.addCallback(finish_mul)
179 return result