viff

view viff/bedoza/zero_knowledge.py @ 1572:54f02cd75714

find changesets by author, revision, files, or words in the commit message
BeDOZa: Improved comments.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Mon Oct 04 10:58:23 2010 +0200 (19 months ago)
parents cb800e02f5bd
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/>.
17
18 from gmpy import mpz, digits
19
20 import hashlib
21
22 from viff.runtime import gatherResults
23 from viff.bedoza.util import rand_int_signed
24
25 class ZKProof(object):
26 """Zero-knowledge protocol used as part of the Share protocol.
27
28 In this proof, a player (the player with id prover_id) inputs s
29 ciphertexts c[i] = E(x[j], r[j]), for i = 1, ..., s, created using
30 the modified Paillier cipher and proves to the other players that
31 he knows the plaintexts x[j] and that the x[i]'s are of limited
32 size, e.g. that abs(x[i]) <= 2**k.
33 """
34
35 def __init__(self, s, prover_id, k, runtime, c, random=None, paillier=None, x=None, r=None):
36 """
37 random: a random source (e.g. viff.util.Random)
38
39 All players must submit the same vector c, but only the player
40 with id prover_id should submit the corresponding x and r, e.g. where
41 c_i = E_i(x_i, r_i).
42 """
43 assert len(c) == s
44 assert prover_id in runtime.players
45 if x != None:
46 for xi in x:
47 assert abs(xi) <= 2**k
48 self.x = x
49 self.r = r
50 self.s = s
51 self.m = 2 * s - 1
52 self.prover_id = prover_id
53 self.k = k
54 self.runtime = runtime
55 self.c = c
56 self.paillier = paillier
57 self.random = random
58 self.prover_n = mpz(self.runtime.players[self.prover_id].pubkey['n'])
59
60 # TODO: Use the n**2 already in the pubkey.
61 self.prover_n2 = self.prover_n**2
62
63 def start(self):
64 """Executes this zero-knowledge proof.
65
66 Returns a deferred evaluating to True if the proof succeeds
67 and False otherwise. The proof succeeds if the verifiers,
68 e.g. all players except the player with prover_id are able to
69 verify that each number inside the encryptions c are
70 numerically at most 2**(s + 2k).
71
72 The result also evaluates to True or False as above for the
73 proving player, even though this is not needed.
74 """
75 if self.runtime.id == self.prover_id:
76 self._generate_proof()
77 deferred_proof = self._get_proof_broadcasted_by_prover()
78 self.runtime.schedule_callback(deferred_proof, self._verify_proof)
79 return deferred_proof
80
81 def _generate_proof(self):
82 self._generate_u_v_and_d()
83 self._generate_e()
84 self._generate_Z_and_W()
85
86 def _verify_proof(self, serialized_proof):
87 # The prover don't need to prove to himself.
88 if self.runtime.id == self.prover_id:
89 return True
90 self._deserialize_proof(serialized_proof)
91 self._generate_e()
92 temp = self._vec_pow_E(self.c, self.prover_n2)
93 S = self._vec_mul(self.d, temp, self.prover_n2)
94 T = [mpz(self.paillier.encrypt(int(self.Z[j]), player_id=self.prover_id, random_elm=int(self.W[j])))
95 for j in range(self.m)]
96 for j in xrange(self.m):
97 # TODO: Return false if S[j] != T[j].
98 if S[j] != T[j]:
99 # TODO: Proof failed, return false!
100 pass
101 if abs(self.Z[j]) > 2**(2 * self.k):
102 # TODO: Proof failed, return false!
103 pass
104
105 # TODO: Fix zero-knowledge proof!!!
106 return True
107
108
109 def _generate_u_v_and_d(self):
110 self.u, self.v, self.d = [], [], []
111 for i in range(self.m):
112 ui = rand_int_signed(self.random, 2**(2 * self.k))
113 vi, di = self.paillier.encrypt_r(ui)
114 assert abs(ui) <= 2**(2 * self.k)
115 self.u.append(mpz(ui))
116 self.v.append(mpz(vi))
117 self.d.append(mpz(di))
118
119 def _generate_Z_and_W(self):
120 self.Z = self._vec_add(self.u, self._vec_mul_E(self.x))
121 self.W = self._vec_mul(self.v, self._vec_pow_E(self.r, self.prover_n2), self.prover_n2)
122
123 def _get_proof_broadcasted_by_prover(self):
124 serialized_proof = None
125 if self.runtime.id == self.prover_id:
126 # TODO: Should we somehow compress message for improved
127 # performance?
128 serialized_proof = self._serialize_proof()
129 deferred_proof = self._broadcast(serialized_proof)
130 return deferred_proof
131
132 def _serialize_proof(self):
133 return repr([self.d, self.Z, self.W])
134
135 def _deserialize_proof(self, serialized_proof):
136 # We remove quotes before evaluation in order to get a list.
137 proof = eval(serialized_proof[1:-1])
138 self.d = proof[0]
139 self.Z = proof[1]
140 self.W = proof[2]
141
142 def _extract_bits(self, string, no_of_bits):
143 """Returns list of first no_of_bits from the given string."""
144 word_size = 8 # No of bits in char.
145 assert no_of_bits <= word_size * len(string), "Not enough bits"
146 res = []
147 if no_of_bits == 0:
148 return res
149 no_of_chars = 1 + no_of_bits / word_size
150 for c in string[:no_of_chars]:
151 _digits = [int(v) for v in digits(ord(c), 2).zfill(word_size)]
152 if len(res) + word_size >= no_of_bits:
153 return res + _digits[:no_of_bits - len(res)]
154 res += _digits
155 return [mpz(b) for b in res]
156
157
158 def _generate_e(self):
159 """Generating an s-bit challenge e by the Fiat-Shamir heuristic.
160
161 In other security models, generating the challenge requires
162 interaction.
163
164 The challenge is a list of 0's and 1's of length s.
165 """
166 # This can be easily fixed by using the hash as seed for a
167 # secure prng.
168 assert self.s <= 160, "Error: Algorithm only supports s <= 160"
169 assert hasattr(self, 'c')
170 assert hasattr(self, 'd')
171 h = hashlib.sha1()
172 for c, d in zip(self.c, self.d):
173 h.update(repr(c))
174 h.update(repr(d))
175 hash = h.digest()
176 self.e = self._extract_bits(hash, self.s)
177
178 def _broadcast(self, values):
179 msg = repr(values) if self.prover_id == self.runtime.id else None
180 return self.runtime.broadcast(
181 [self.prover_id], self.runtime.players.keys(), message=msg)
182
183 def _err_handler(self, err):
184 print err
185 return err # raise or what?
186
187 def _E(self, row, col):
188 """Computes the value of the entry in the matrix E at the given row
189 and column.
190
191 The first column of E consists of the bits of e followed by 0's;
192 The next column has one zero, then the bits of e, followed by 0's,
193 etc.
194 """
195 if row >= col and row < col + self.s:
196 return self.e[row - col]
197 else:
198 return 0
199
200 def _vec_add(self, x, y):
201 return [x + y for x, y in zip(x,y)]
202
203 def _vec_mul_E(self, x):
204 """Takes an s x 1 vector x and returns the m x 1 vector xE."""
205 # TODO: This could probably be optimized since we know the
206 # structure of E.
207 res = []
208 for j in xrange(self.m):
209 t = 0
210 for i in xrange(self.s):
211 t = t + x[i] * self._E(j, i)
212 res.append(t)
213 return res
214
215 def _vec_mul(self, x, y, n):
216 return [(x * y) % n for x, y in zip(x,y)]
217
218 def _vec_pow_E(self, y, n):
219 """Computes and returns the m := 2s-1 length vector y**E."""
220 assert self.s == len(y), \
221 "not same length: %d != %d" % (self.s, len(y))
222 res = [mpz(1)] * self.m
223 for j in range(self.m):
224 for i in range(self.s):
225 if self._E(j, i) == mpz(1):
226 # TODO: Should we reduce modulo n each time?
227 res[j] = (res[j] * y[i]) % n
228 return res