# HG changeset patch # User Janus Dam Nielsen <janus.niel...@alexandra.dk> # Date 1245395102 -7200 # Node ID 4c46e8eeb719682da1a91b7ad96e7e902363e204 # Parent ad19cc189a5bf04ba37c0a9e25600040585cc1e9 Implementation of the TripleGen protocol.
diff --git a/viff/orlandi.py b/viff/orlandi.py --- a/viff/orlandi.py +++ b/viff/orlandi.py @@ -15,10 +15,11 @@ # You should have received a copy of the GNU Lesser General Public # License along with VIFF. If not, see <http://www.gnu.org/licenses/>. -from twisted.internet.defer import DeferredList, gatherResults +from twisted.internet.defer import Deferred, DeferredList, gatherResults -from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares +from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares, PAILLIER from viff.util import rand, dprint +from viff.paillier import encrypt, encrypt_r, decrypt class OrlandiException(Exception): pass @@ -713,6 +714,226 @@ return result + @increment_pc + def triple_gen(self, field): + """Generate a triple a, b, c s.t. c = a * b. + + 1) Every party P_{i} chooses random values a_{i}, r_{i} in Z_{p} x (Z_{p})^2, + compute alpha_{i} = Enc_{eki}(a_{i}) and Ai = Com_{ck}(a_{i}, r_{i}), and + broadcast them. + + 2) Every party P_{j} does: + (a) choose random b_{j}, s_{j} in Z_{p} x (Z_{p})^2. + + (b) compute B_{j} = Com_{ck}(b_{j}, s_{j}) and broadcast it. + + (c) P_{j} do, towards every other party: + i. choose random d_{i,j} in Z_{p^{3}} + ii. compute and send + gamma_{i,j} = alpha_{i}^{b_{j}} Enc_{ek_{i}}(1;1)^{d_{i, j}} to P_{i}. + + 3) Every party P_{i} does: + (a) compute c_{i} = SUM_{j} Dec_{sk_{i}}(gamma_{i,j}) - SUM_{j} d_{i,j} mod p + + (b) pick random t_{i} in (Z_{p})^2, compute and + broadcast C_{i} = Com_{ck}(c_{i}, t_{i}) + + 4) Everyone computes: + (A, B, C) = (PRODUCT_{i} A_{i}, PRODUCT_{i} B_{i}, PRODUCT_{i} C_{i}) + + 5) Every party P_{i} outputs shares [a_{i}] = (a_{i}, r_{i}, A), + [b_{i}] = (b_{i}, s_{i}, B), and [c_{i}] = (c_{i}, t_{i}, C). + + """ + def random_number(p): + return field(rand.randint(0, p - 1)) + + def product(ls): + """Compute the product of the elements in the list ls.""" + b = field(1) + for x in ls: + b *= x + return b + + def sum(ls): + """Compute the sum of the elements in the list ls.""" + b = field(0) + for x in ls: + b += x + return b + + def step45(Cs, As, Bs, ai, bi, ci, r, s, t): + """4) Everyone computes: + A = PRODUCT_{i} A_{i} + B = PRODUCT_{i} B_{i} + C = PRODUCT_{i} C_{i} + + 5) Every party P_{i} outputs shares [a_{i}] = (a_{i}, r_{i}, A), + [b_{i}] = (b_{i}, s_{i}, B), and [c_{i}] = (c_{i}, t_{i}, C). + """ + A = product(As) + B = product(Bs) + C = product(Cs) + a = OrlandiShare(self, field, ai, r, A) + b = OrlandiShare(self, field, bi, s, B) + c = OrlandiShare(self, field, ci, t, C) + return (a, b, c) + + def decrypt_gammas(ls): + """Decrypt all the elements of the list ls.""" + rs = [] + for x in ls: + rs.append(field(decrypt(x, self.players[self.id].seckey))) + return rs + + def step3(gammas, As, Bs, ai, bi, r, s, dijs): + """3) Every party P_{i} does: + (a) compute + c_{i} = SUM_{j} Dec_{sk_{i}}(gamma_{i,j}) - SUM_{j} d_{j,i} mod p + + (b) pick random t_{i} in (Z_{p})^2, compute and + broadcast C_{i} = Com_{ck}(c_{i}, t_{i}) + """ + # c_{i} = SUM_{j} Dec_{sk_{i}}(gamma_{i,j}) - SUM_{j} d_{j,i} mod p. + ls = decrypt_gammas(gammas) + ci = sum(ls) - sum(dijs) + # (b) pick random t_{i} in (Z_{p})^2. + t1 = random_number(field.modulus) + t2 = random_number(field.modulus) + t = (t1, t2) + # C_{i} = Com_{ck}(c_{i}, t_{i}). + Ci = self._Com(ci, t) + + # Broadcast Ci. + Cs = [None] * len(self.players) + pc = tuple(self.program_counter) + for peer_id in self.players: + if peer_id != self.id: + self.protocols[peer_id].sendShare(pc, Ci) + d = self._expect_share(peer_id, field) + else: + d = Deferred() + d.callback(Ci) + Cs[peer_id - 1] = d + result = gatherResults(Cs) + result.addCallback(step45, As, Bs, ai, bi, ci, r, s, t) + result.addErrback(self.error_handler) + return result + + def step2c(Bs, As, alphas, ai, bj, r, s): + """(c) P_{j} do, towards every other party: + i. choose random d_{i,j} in Z_{p^{3}} + ii. compute and send + gamma_{i,j} = alpha_{i}^{b_{j}} Enc_{ek_{i}}(1;1)^{d_{i, j}} to P_{i}. + """ + + # (c) P_{j} do, towards every other party: + dijs = [] + results = [None] * len(self.players) + pc = tuple(self.program_counter) + for pi in self.players: + n = self.players[pi].pubkey[0] + nsq = n * n + # choose random d_{i,j} in Z_{p^{3}} + dij = random_number(field.modulus**3) + # Enc_{ek_{i}}(1;1)^{d_{i, j}} + enc = encrypt_r(1, 1, self.players[pi].pubkey) + t1 = pow(enc, dij.value, nsq) + # alpha_{i}^{b_{j}}. + t2 = pow(alphas[pi - 1], bj.value, nsq) + # gamma_{i,j} = alpha_{i}^{b_{j}} Enc_{ek_{i}}(1;1)^{d_{i, j}} + gammaij = (t2) * (t1) % nsq + # Broadcast gamma_{i,j} + if pi != self.id: + self.protocols[pi].sendData(pc, PAILLIER, str(gammaij)) + d = Deferred() + d.addCallbacks(lambda value: long(value), self.error_handler) + self._expect_data(pi, PAILLIER, d) + else: + d = Deferred() + d.callback(gammaij) + dijs.append(dij) + results[pi - 1] = d + result = gatherResults(results) + self.schedule_callback(result, step3, As, Bs, ai, bj, r, s, dijs) + result.addErrback(self.error_handler) + return result + + def step2ab((alphas, As), ai, r): + """2) Every party P_{j} does: + (a) choose random b_{j}, s_{j} in Z_{p} x (Z_{p})^2. + + (b) compute B_{j} = Com_{ck}(b_{j}, s_{j}) and broadcast it. + """ + # (a) choose random b_{j}, s_{j} in Z_{p} x (Z_{p})^2. + bj = random_number(field.modulus) + s1 = random_number(field.modulus) + s2 = random_number(field.modulus) + # (b) compute B_{j} = Com_{ck}(b_{j}, s_{j}). + Bj = self._Com(bj, (s1, s2)) + + # Broadcast B_{j}. + results = [None] * len(self.players) + for peer_id in self.players: + if peer_id == self.id: + pc = tuple(self.program_counter) + for other_id in self.players: + if other_id != self.id: + self.protocols[other_id].sendShare(pc, Bj) + d = Deferred() + d.callback(Bj) + else: + d = self._expect_share(peer_id, field) + results[peer_id - 1] = d + result = gatherResults(results) + self.schedule_callback(result, step2c, As, alphas, ai, bj, r, (s1, s2)) + result.addErrback(self.error_handler) + return result + + # 1) Every party P_{i} chooses random values a_{i}, r_{i} in Z_{p} x (Z_{p})^2, + # compute alpha_{i} = Enc_{eki}(a_{i}) and Ai = Com_{ck}(a_{i}, r_{i}), and + # broadcast them. + + # Every party P_{i} chooses random values a_{i}, r_{i} in Z_{p} x (Z_{p})^2 + ai = random_number(field.modulus) + r1 = random_number(field.modulus) + r2 = random_number(field.modulus) + + # compute alpha_{i} = Enc_{eki}(a_{i}) + alphai = encrypt(ai.value, self.players[self.id].pubkey) + # and A_{i} = Com_{ck}(a_{i}, r_{i}). + Ai = self._Com(ai, (r1, r2)) + + # broadcast alpha_{i} and A_{i}. + alpha_results = [None] * len(self.players) + A_results = [None] * len(self.players) + for peer_id in self.players: + if peer_id == self.id: + pc = tuple(self.program_counter) + for other_id in self.players: + if other_id != self.id: + self.protocols[other_id].sendData(pc, PAILLIER, str(alphai)) + self.protocols[other_id].sendShare(pc, Ai) + d1 = Deferred() + d1.callback(alphai) + d2 = Deferred() + d2.callback(Ai) + else: + d1 = Deferred() + d1.addCallbacks(lambda value: long(value), self.error_handler) + self._expect_data(peer_id, PAILLIER, d1) + d2 = self._expect_share(peer_id, field) + alpha_results[peer_id - 1] = d1 + A_results[peer_id - 1] = d2 + + result1 = gatherResults(alpha_results) + result2 = gatherResults(A_results) + result = gatherResults([result1, result2]) + self.schedule_callback(result, step2ab, ai, (r1, r2)) + result.addErrback(self.error_handler) + return result + + def error_handler(self, ex): print "Error: ", ex return ex diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py --- a/viff/test/test_orlandi_runtime.py +++ b/viff/test/test_orlandi_runtime.py @@ -18,8 +18,8 @@ from twisted.internet.defer import gatherResults, DeferredList from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase -from viff.runtime import Share -from viff.orlandi import OrlandiRuntime +from viff.runtime import Share, gather_shares +from viff.orlandi import OrlandiRuntime, OrlandiShare from viff.field import FieldElement from viff.passive import PassiveRuntime @@ -442,3 +442,56 @@ d = runtime.open(z2) d.addCallback(check) return d + +class TripleGenTest(RuntimeTestCase): + """Test for generation of triples.""" + + # Number of players. + num_players = 3 + + runtime_class = OrlandiRuntime + + timeout = 240 + + @protocol + def test_tripleGen(self, runtime): + """Test the triple_gen command.""" + + def check((a, b, c)): + self.assertEquals(c, a * b) + + def open((a, b, c)): + d1 = runtime.open(a) + d2 = runtime.open(b) + d3 = runtime.open(c) + d = gatherResults([d1, d2, d3]) + d.addCallback(check) + return d + d = runtime.triple_gen(self.Zp) + d.addCallbacks(open, runtime.error_handler) + return d + + @protocol + def test_tripleGen2(self, runtime): + """Test the triple_gen command.""" + + def check((a, b, c, dx, dy, dz)): + self.assertEquals(c, a * b) + self.assertEquals(dz, dx * dy) + + def open(((a, b, c), (x, y, z))): + d1 = runtime.open(a) + d2 = runtime.open(b) + d3 = runtime.open(c) + dx = runtime.open(x) + dy = runtime.open(y) + dz = runtime.open(z) + d = gatherResults([d1, d2, d3, dx, dy, dz]) + d.addCallback(check) + return d + t1 = runtime.triple_gen(self.Zp) + t2 = runtime.triple_gen(self.Zp) + d = gatherResults([t1, t2]) + d.addCallbacks(open, runtime.error_handler) + return d + _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
