changeset 1231:db2d970885f4

Implementation of the TripleGen protocol.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Oct 2009 10:05:24 +0200
parents 86e0c7d54f22
children f5b89b88b8c8
files viff/orlandi.py viff/test/test_orlandi_runtime.py
diffstat 2 files changed, 253 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
+++ b/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
@@ -19,8 +19,9 @@
 
 from viff.runtime import Runtime, Share, ShareList, gather_shares
 from viff.util import rand
-from viff.constants import TEXT
+from viff.constants import TEXT, PAILLIER
 from viff.field import FieldElement
+from viff.paillier import encrypt_r, decrypt
 
 from hash_broadcast import HashBroadcastMixin
 
@@ -771,6 +772,200 @@
 
         return result
 
+    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_ij in Z_p^3``
+               ii. compute and send 
+                   ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
+
+        3) Every party ``P_i`` does:
+           (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij 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)``.
+
+        """
+        self.program_counter[-1] += 1
+
+        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 = commitment.deserialize(ls[0])
+            for x in ls[1:]:
+                b *= commitment.deserialize(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, alphas, gammas, alpha_randomness,
+                   As, Bs, ai, bi, ci, r, s, t, dijs):
+            """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, (alphas, alpha_randomness, gammas, dijs))
+
+        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, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs):
+            """3) Every party ``P_i`` does:
+                  (a) compute 
+                  ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji 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_ij) - SUM_j d_ji 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 = commitment.commit(ci.value, t1.value, t2.value)
+            
+            # Broadcast Ci.
+            Cs = self.broadcast(self.players.keys(), self.players.keys(), repr(Ci))
+            result = gatherResults(Cs)
+            result.addCallbacks(step45, self.error_handler, callbackArgs=(alphas, gammas, alpha_randomness, 
+                                                                          As, Bs, ai, bi, ci, r, s, t, dijs))
+            return result
+
+        def step2c(Bs, As, alphas, alpha_randomness, 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_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i.
+            """
+
+            # (c) P_j do, towards every other party:
+            dijs = [None] * len(self.players.keys())
+            results = [None] * len(self.players.keys())
+            pc = tuple(self.program_counter)
+            for pi in self.players.keys():
+                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_ij
+                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_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
+                gammaij = (t2) * (t1) % nsq
+                # Broadcast gamma_ij
+                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[pi - 1] = dij
+                results[pi - 1] = d
+            result = gatherResults(results)
+            self.schedule_callback(result, step3, alphas, alpha_randomness, 
+                                   As, Bs, ai, bj, r, s, dijs)
+            result.addErrback(self.error_handler)
+            return result
+
+        def step2ab((alphas, As), ai, r, alpha_randomness):
+            """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 = commitment.commit(bj.value, s1.value, s2.value)
+
+            # Broadcast B_j.
+            results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj))
+            result = gatherResults(results)
+            self.schedule_callback(result, step2c, As, alphas, alpha_randomness, 
+                                   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) 
+        n, g = self.players[self.id].pubkey
+        alpha_randomness = rand.randint(1, long(n))
+        alphai = encrypt_r(ai.value, alpha_randomness, (n, g))
+        # and A_i = Com_ck(a_i, r_i).
+        Ai = commitment.commit(ai.value, r1.value, r2.value)
+
+        # broadcast alpha_i and A_i.
+        ds = self.broadcast(sorted(self.players.keys()), sorted(self.players.keys()), str(alphai) + ":" + repr(Ai))
+
+        result = gatherResults(ds)
+        def split_alphas_and_As(ls):
+            alphas = []
+            As = []
+            for x in ls:
+                alpha, Ai = x.split(':')
+                alphas.append(long(alpha))
+                As.append(Ai)
+            return alphas, As
+        self.schedule_callback(result, split_alphas_and_As)
+        self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
+        result.addErrback(self.error_handler)
+        return result
+                
+
     def error_handler(self, ex):
         print "Error: ", ex
         return ex
--- a/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
+++ b/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
@@ -567,3 +567,60 @@
         z2 = runtime._cmul(y2, x2, self.Zp)
         self.assertEquals(z2, None)
         return z2
+
+
+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."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        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."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        def check((a, b, c, dx, dy, dz)):
+            self.assertEquals(c, a * b)
+            self.assertEquals(dz, dx * dy)
+
+        def open(((a, b, c, control), (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