[viff-devel] [PATCH 11 of 12] Implementation of the TripleGen protocol
Janus Dam Nielsen
janus.nielsen at alexandra.dk
Fri Jun 19 02:32:23 PDT 2009
# HG changeset patch
# User Janus Dam Nielsen <janus.nielsen at 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
+
More information about the viff-devel
mailing list