viff

view viff/bedoza/bedoza_triple.py @ 1535:b4451e4ac76d

find changesets by author, revision, files, or words in the commit message
BeDOZa: Use gmpy for modular exponentiation.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Tue Aug 10 16:03:54 2010 +0200 (21 months ago)
parents 315e1117928a
children 8b1b64b3ea5b
line source
1 # Copyright 2010 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 """Triple generation for the BeDOZa protocol.
19 TODO: Explain more.
20 """
21
22 import itertools
23
24 from twisted.internet.defer import Deferred, gatherResults, succeed
25
26 from viff.runtime import Runtime, Share, ShareList, gather_shares
27 from viff.field import FieldElement, GF
28 from viff.constants import TEXT
29 from viff.util import rand
30 from viff.bedoza.shares import BeDOZaShare, BeDOZaShareContents, PartialShare
31 from viff.bedoza.shares import PartialShareContents
32 from viff.bedoza.share_generators import PartialShareGenerator, ShareGenerator
33 from viff.bedoza.keylist import BeDOZaKeyList
34 from viff.bedoza.maclist import BeDOZaMACList
35 from viff.bedoza.add_macs import add_macs
36 from viff.bedoza.modified_paillier import ModifiedPaillier
37 from viff.bedoza.util import fast_pow
38
39 from viff.triple import Triple
40
41 # TODO: Use secure random instead!
42 from random import Random
43
44 try:
45 import pypaillier
46 except ImportError:
47 # The pypaillier module is not released yet, so we cannot expect
48 # the import to work.
49 print "Error: The pypaillier module or one of the used functions " \
50 "are not available."
51
52
53 class TripleGenerator(object):
54
55 def __init__(self, runtime, p, random):
56 assert p > 1
57 self.random = random
58 # TODO: Generate Paillier cipher with N_i sufficiently larger than p
59 self.runtime = runtime
60 self.p = p
61 self.Zp = GF(p)
62 self.k = self._bit_length_of(p)
63 self.u_bound = 2**(4 * self.k)
64
65 paillier_random = Random(self.random.getrandbits(128))
66 alpha_random = Random(self.random.getrandbits(128))
67 self.paillier = ModifiedPaillier(runtime, paillier_random)
68
69 # Debug output.
70 #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
71 #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
72 #print "n_%d bitlength: %d" % \
73 # (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
74
75 #self.Zp = GF(p)
76 #self.Zn2 = GF(self.paillier.pubkey['n_square'])
77 #self.alpha = self.Zp(self.random.randint(0, p - 1))
78 self.alpha = alpha_random.randint(0, p - 1)
79 self.n2 = runtime.players[runtime.id].pubkey['n_square']
80
81 def _bit_length_of(self, i):
82 bit_length = 0
83 while i:
84 i >>= 1
85 bit_length += 1
86 return bit_length
87
88 def generate_triples(self, n):
89 """Generates and returns a set of n triples.
90
91 Data sent over the network is packaged in large hunks in order
92 to optimize. TODO: Explain better.
93
94 TODO: This method needs to have enough RAM to represent all n
95 triples in memory at the same time. Is there a nice way to
96 stream this, e.g. by using Python generators?
97 """
98
99 self.runtime.increment_pc()
100
101 def check(v, a, b, c):
102 if v.value != 0:
103 raise Exception("TripleTest failed - The two triples were "
104 "inconsistent.")
105 return Triple(a, b, c)
106
107 def compute_value(r, a, b, c, x, y, z):
108 l = self.runtime._cmul(r, x, self.Zp)
109 m = self.runtime._cmul(r, y, self.Zp)
110 k = self.runtime._cmul(r*r, z, self.Zp)
111 v = c - self.runtime._basic_multiplication(a, b, l, m, k)
112 v = self.runtime.open(v)
113 v.addCallback(check, a, b, c)
114 return v
115
116 gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier,
117 self.u_bound, self.alpha)
118
119 random_shares = gen.generate_random_shares(n)
120
121 results = [Deferred() for _ in xrange(n)]
122
123 triples = self._generate_passive_triples(2 * n)
124
125 for inx in xrange(n):
126 a = triples[inx]
127 b = triples[inx + 2 * n]
128 c = triples[inx + 4 * n]
129 x = triples[inx + n]
130 y = triples[inx + 3 * n]
131 z = triples[inx + 5 * n]
132 r = self.runtime.open(random_shares[inx])
133 self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
134 r.chainDeferred(results[inx])
135 return results
136
137 # TODO: Do some ZK stuff.
138
139 def _generate_passive_triples(self, n):
140 """Generates and returns a list of 3n shares corresponding to
141 n passive tuples. The first n are the a's, then comes n b's
142 followed by n c's.
143
144 Consistency is only guaranteed if all players follow the protool.
145 """
146
147 self.runtime.increment_pc()
148
149 gen = PartialShareGenerator(self.Zp, self.runtime, self.random,
150 self.paillier)
151 partial_shares = []
152 for _ in xrange(2 * n):
153 partial_shares.append(
154 gen.generate_share(
155 self.random.randint(0, self.Zp.modulus - 1)))
156
157
158 partial_shares_c = self._full_mul(partial_shares[0:n],
159 partial_shares[n:2*n])
160
161 full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
162 self.random, self.paillier,
163 partial_shares + partial_shares_c)
164
165 return full_shares
166
167 # for player i:
168 # receive c from player i and set
169 # m^i=Decrypt(c)
170
171 def _mul(self, inx, jnx, n, ais=None, cjs=None):
172 """Multiply each of the field elements in *ais* with the
173 corresponding encrypted elements in *cjs*.
174
175 Returns a deferred which will yield a list of PartialShareContents.
176 """
177 CKIND = 1
178 DiKIND = 2
179 DjKIND = 3
180
181 """The transmission_restraint_constant is the number of
182 encrypted shares we can safely transmit in one call to
183 sendData. The sendData method can only transmit up to
184 65536 bytes.
185 The constant has been imperically determined by running
186 TripleGenerator.generate_triples.
187 TODO: How can we allow a user of the runtime to adjust this
188 constraint at a higher level of abstraction?
189 """
190 transmission_restraint_constant = 425
191
192 number_of_packets = n / transmission_restraint_constant
193 if n % transmission_restraint_constant != 0:
194 number_of_packets += 1
195
196 self.runtime.increment_pc()
197
198 pc = tuple(self.runtime.program_counter)
199
200 deferreds = []
201 zis = []
202 if self.runtime.id == inx:
203 Nj_square = self.paillier.get_modulus_square(jnx)
204 all_cs = []
205 all_dis = []
206 for iny, (ai, cj) in enumerate(zip(ais, cjs)):
207 if iny % transmission_restraint_constant == 0:
208 cs = []
209 all_cs.append(cs)
210 dis = []
211 all_dis.append(dis)
212 u = rand.randint(0, self.u_bound)
213 Ej_u = self.paillier.encrypt(u, jnx)
214 cs.append( (fast_pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
215 zi = self.Zp(-u)
216 zis.append(zi)
217 dis.append(self.paillier.encrypt(zi.value, inx))
218
219 for cs in all_cs:
220 self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
221
222 for dis in all_dis:
223 for player_id in self.runtime.players:
224 self.runtime.protocols[player_id].sendData(pc, DiKIND,
225 str(dis))
226
227 if self.runtime.id == jnx:
228 all_cs = []
229 for _ in xrange(number_of_packets):
230 cs = Deferred()
231 self.runtime._expect_data(inx, CKIND, cs)
232 all_cs.append(cs)
233
234 def decrypt(all_cs, pc, zis):
235 zjs = []
236 cs = reduce(lambda x, y: x + eval(y), all_cs, [])
237 all_djs = []
238 for iny, c in enumerate(cs):
239 if iny % transmission_restraint_constant == 0:
240 djs = []
241 all_djs.append(djs)
242 t = self.paillier.decrypt(c)
243 zj = self.Zp(t)
244 zjs.append(zj)
245 djs.append(self.paillier.encrypt(zj.value, jnx))
246 for djs in all_djs:
247 for player_id in self.runtime.players:
248 self.runtime.protocols[player_id].sendData(pc, DjKIND,
249 str(djs))
250 if not zis == []:
251 return [x + y for x, y in zip(zis, zjs)]
252 else:
253 return zjs
254 all_cs_d = gatherResults(all_cs)
255 all_cs_d.addCallback(decrypt, pc, zis)
256 deferreds.append(all_cs_d)
257 else:
258 zis_deferred = Deferred()
259 zis_deferred.callback(zis)
260 deferreds.append(zis_deferred)
261
262 all_dis = []
263 for _ in xrange(number_of_packets):
264 dis = Deferred()
265 self.runtime._expect_data(inx, DiKIND, dis)
266 all_dis.append(dis)
267 all_djs = []
268 for _ in xrange(number_of_packets):
269 djs = Deferred()
270 self.runtime._expect_data(jnx, DjKIND, djs)
271 all_djs.append(djs)
272
273 deferreds.append(gatherResults(all_dis))
274 deferreds.append(gatherResults(all_djs))
275 r = gatherResults(deferreds)
276 def wrap((values, dis, djs), inx, jnx):
277 dis = reduce(lambda x, y: x + eval(y), dis, [])
278 djs = reduce(lambda x, y: x + eval(y), djs, [])
279 n_square_i = self.paillier.get_modulus_square(inx)
280 n_square_j = self.paillier.get_modulus_square(jnx)
281 N_squared_list = [self.paillier.get_modulus_square(player_id)
282 for player_id in self.runtime.players]
283 ps = []
284
285 for v, di, dj in itertools.izip_longest(values, dis, djs,
286 fillvalue=self.Zp(0)):
287 value = v
288 enc_shares = len(self.runtime.players) * [1]
289 enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
290 enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
291 ps.append(PartialShareContents(value, enc_shares,
292 N_squared_list))
293 return ps
294 r.addCallback(wrap, inx, jnx)
295 return r
296
297 def _full_mul(self, a, b):
298 """Multiply each of the PartialShares in the list *a* with the
299 corresponding PartialShare in the list *b*.
300
301 Returns a deferred which will yield a list of PartialShares.
302 """
303 self.runtime.increment_pc()
304
305 def do_full_mul(shares, result_shares):
306 """Share content belonging to ai, bi are at:
307 shares[i], shares[len(shares) + i].
308 """
309 deferreds = []
310 len_shares = len(shares)
311 a_values = [s.value for s in shares[0:len_shares/2]]
312 b_enc_shares = []
313 for inx in self.runtime.players:
314 b_enc_shares.append([s.enc_shares[inx - 1]
315 for s in shares[len_shares/2:]])
316 for inx in xrange(0, len(self.runtime.players)):
317 for jnx in xrange(0, len(self.runtime.players)):
318 deferreds.append(self._mul(inx + 1,
319 jnx + 1,
320 len(a_values),
321 a_values,
322 b_enc_shares[jnx]))
323
324 def compute_shares(partialShareContents, len_shares, result_shares):
325 num_players = len(self.runtime.players)
326 pcs = len(partialShareContents[0]) * [None]
327 for ps in partialShareContents:
328 for inx in xrange(0, len(ps)):
329 if pcs[inx] == None:
330 pcs[inx] = ps[inx]
331 else:
332 pcs[inx] += ps[inx]
333 for p, s in zip(pcs, result_shares):
334 s.callback(p)
335 return None
336 d = gatherResults(deferreds)
337 d.addCallback(compute_shares, len_shares, result_shares)
338 return d
339 result_shares = [Share(self.runtime, self.Zp) for x in a]
340 self.runtime.schedule_callback(gatherResults(a + b),
341 do_full_mul,
342 result_shares)
343 return result_shares
344
345
346 # TODO: Represent all numbers by GF objects, Zp, Zn, etc.
347 # E.g. paillier encrypt should return Zn^2 elms and decrypt should
348 # return Zp elements.