viff
view viff/bedoza/bedoza_triple.py @ 1574:0d3b99e1e3eb
BeDOZa: Connected zero-knowledge proof to the remaining protocol.
| author | Thomas P Jakobsen <tpj@cs.au.dk> |
|---|---|
| date | Mon Oct 04 21:51:33 2010 +0200 (19 months ago) |
| parents | 6a727af6cb6c |
| children |
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/>.
18 """Triple generation for the BeDOZa protocol.
19 TODO: Explain more.
20 """
44 # TODO: Use secure random instead!
50 # The pypaillier module is not released yet, so we cannot expect
51 # the import to work.
53 "are not available."
61 # TODO: Generate Paillier cipher with N_i sufficiently larger than p
74 # Debug output.
75 #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
76 #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
77 #print "n_%d bitlength: %d" % \
78 # (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
80 #self.Zp = GF(p)
81 #self.Zn2 = GF(self.paillier.pubkey['n_square'])
82 #self.alpha = self.Zp(self.random.randint(0, p - 1))
88 """Generates triples for use in the BeDOZa protocol.
90 Returns a deferred that will eventually yield a list
91 containing *self.security_parameter* multiplicative
92 triples. Each of these triples is an object of type
93 viff.triple.Triple. The components of each triple t, e.g.
95 t.a, t.b, and t.c,
97 are each of type BeDOZaShare and guaranteed to satisfy the
98 equation
100 t.c = t.a * t.b.
102 This method carries out the off-line work that is needed for
103 the BeDOZa protocol to work.
105 Data sent over the network is packaged in large hunks in order
106 to optimize. TODO: Explain better.
108 TODO: This method needs to have enough RAM to represent all n
109 triples in memory at the same time. Is there a nice way to
110 stream this, e.g. by using Python generators?
112 """
123 """Generates triple candidates for use in the BeDOZa protocol.
125 Returns a deferred that will eventually yield a list of 3n
126 shares of type viff.bedoza.shares.BeDOZaShare corresponding to
127 n multiplicative tuples. The first n are the a's, then comes n
128 b's followed by n c's.
130 The triples are only candidates because consistency of the
131 triples is only half-way guaranteed in the precense of active
132 adversaries. More concretely, the triples returned by this
133 method are guaranteed - even in the precense of an active
134 adversary - to be of the right size. But they may not satisfy
135 the equation
137 c = a * b.
139 """
158 """Verify remaining consistency of triple candidates.
160 Takes as input a deferred list of 2n triple candidates as
161 generated by _generate_triple_candidates(2 * n) and returns
162 another deferred that will eventually yield a list of
163 viff.triple.Triple objects that are guaranteed to be fully
164 consistent. That is, the shares of the triples are guaranteed
165 to be of the right size and for each triple, the shares are
166 quaranteed to satisfy c = a * b.
168 The technique implemented in this method is essentially that
169 listed in Figure 5.5 in the progress report "LEGO and Other
170 Cryptographic Constructions" by Claudio Orlandi.
172 However, since we only implement a protocol that is secure in
173 the Random Oracle Model and not the Common Reference String
174 Model, we can safely skip step 2 of Figure 5.5 and instead
175 generate r by having all players P_i broadcast a random
176 element r_i and then have each player compute r as the hash of
177 the sum of all r_i's.
179 """
185 "TripleTest failed - The two triple candidates were "
190 # Repr/eval deserialization.
201 # Hash all received random values to agree on a single
202 # random value for each triple.
206 # TODO: We should use a secure random generator here.
218 # TODO: Handle errors better.
225 # TODO: We use repr/eval as simple marshalling. Should be
226 # factored out and maybe optimized by using better compression
227 # here.
234 # TODO: Which makes most sense?
235 #
236 # 1) Compute each triple separately and return list of
237 # deferred triples, or
238 #
239 # 2) Compute triples as a batch and return single deferred
240 # that evaluates to list of triples.
241 #
255 """Multiply each of the field elements in *ais* with the
256 corresponding encrypted elements in *cjs*.
258 Returns a deferred which will yield a list of field elements.
259 """
262 """The transmission_restraint_constant is the number of
263 encrypted shares we can safely transmit in one call to
264 sendData. The sendData method can only transmit up to
265 65536 bytes.
266 The constant has been imperically determined by running
267 TripleGenerator.generate_triples.
268 TODO: How can we allow a user of the runtime to adjust this
269 constraint at a higher level of abstraction?
271 """
330 """Multiply each of the PartialShares in the list *a* with the
331 corresponding PartialShare in the list *b*.
333 Returns a deferred which will yield a list of PartialShares.
334 """
338 """Share content belonging to ai, bi are at:
339 shareContents[i], shareContents[len(shareContents) + i].
340 """
388 # TODO: Represent all numbers by GF objects, Zp, Zn, etc.
389 # E.g. paillier encrypt should return Zn^2 elms and decrypt should
390 # return Zp elements.