# [viff-devel] [PATCH 11 of 12] Implementation of the TripleGen protocol

```# HG changeset patch
# User Janus Dam Nielsen <janus.niel...@alexandra.dk>
# Date 1245395102 -7200
# Node ID 4c46e8eeb719682da1a91b7ad96e7e902363e204
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
+
+        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)
+            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)
+            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))
+            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))
+        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)
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])
+            return d
+        d = runtime.triple_gen(self.Zp)
+        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])
+            return d
+        t1 = runtime.triple_gen(self.Zp)
+        t2 = runtime.triple_gen(self.Zp)
+        d = gatherResults([t1, t2])