viff

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 diff
     1.1 --- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     1.2 +++ b/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     1.3 @@ -19,8 +19,9 @@
     1.4  
     1.5  from viff.runtime import Runtime, Share, ShareList, gather_shares
     1.6  from viff.util import rand
     1.7 -from viff.constants import TEXT
     1.8 +from viff.constants import TEXT, PAILLIER
     1.9  from viff.field import FieldElement
    1.10 +from viff.paillier import encrypt_r, decrypt
    1.11  
    1.12  from hash_broadcast import HashBroadcastMixin
    1.13  
    1.14 @@ -771,6 +772,200 @@
    1.15  
    1.16          return result
    1.17  
    1.18 +    def triple_gen(self, field):
    1.19 +        """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
    1.20 +
    1.21 +        1) Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
    1.22 +        compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
    1.23 +        broadcast them.
    1.24 +
    1.25 +        2) Every party ``P_j`` does:
    1.26 +           (a) choose random ``b_j, s_j in Z_p X (Z_p)^2``.
    1.27 +
    1.28 +           (b) compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
    1.29 +
    1.30 +           (c) ``P_j`` do towards every other party:
    1.31 +                i. choose random ``d_ij in Z_p^3``
    1.32 +               ii. compute and send 
    1.33 +                   ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
    1.34 +
    1.35 +        3) Every party ``P_i`` does:
    1.36 +           (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
    1.37 +
    1.38 +           (b) pick random ``t_i in (Z_p)^2``, compute and 
    1.39 +               broadcast ``C_i = Com_ck(c_i, t_i)``
    1.40 +
    1.41 +        4) Everyone computes:
    1.42 +           ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
    1.43 +        
    1.44 +        5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
    1.45 +           ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
    1.46 +
    1.47 +        """
    1.48 +        self.program_counter[-1] += 1
    1.49 +
    1.50 +        def random_number(p):
    1.51 +            return field(rand.randint(0, p - 1))
    1.52 +
    1.53 +        def product(ls):
    1.54 +            """Compute the product of the elements in the list *ls*."""
    1.55 +            b = commitment.deserialize(ls[0])
    1.56 +            for x in ls[1:]:
    1.57 +                b *= commitment.deserialize(x)
    1.58 +            return b
    1.59 +
    1.60 +        def sum(ls):
    1.61 +            """Compute the sum of the elements in the list *ls*."""
    1.62 +            b = field(0)
    1.63 +            for x in ls:
    1.64 +                b += x
    1.65 +            return b
    1.66 +
    1.67 +        def step45(Cs, alphas, gammas, alpha_randomness,
    1.68 +                   As, Bs, ai, bi, ci, r, s, t, dijs):
    1.69 +            """4) Everyone computes:
    1.70 +                  ``A = PRODUCT_i A_i``
    1.71 +                  ``B = PRODUCT_i B_i``
    1.72 +                  ``C = PRODUCT_i C_i``
    1.73 +        
    1.74 +               5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
    1.75 +                  ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
    1.76 +            """
    1.77 +            A = product(As)
    1.78 +            B = product(Bs)
    1.79 +            C = product(Cs)
    1.80 +            a = OrlandiShare(self, field, ai, r, A)
    1.81 +            b = OrlandiShare(self, field, bi, s, B)
    1.82 +            c = OrlandiShare(self, field, ci, t, C)
    1.83 +            return (a, b, c, (alphas, alpha_randomness, gammas, dijs))
    1.84 +
    1.85 +        def decrypt_gammas(ls):
    1.86 +            """Decrypt all the elements of the list *ls*."""
    1.87 +            rs = []
    1.88 +            for x in ls:
    1.89 +                rs.append(field(decrypt(x, self.players[self.id].seckey)))
    1.90 +            return rs
    1.91 +
    1.92 +        def step3(gammas, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs):
    1.93 +            """3) Every party ``P_i`` does:
    1.94 +                  (a) compute 
    1.95 +                  ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p``
    1.96 +
    1.97 +                  (b) pick random ``t_i in (Z_p)^2``, compute and 
    1.98 +                      broadcast ``C_i = Com_ck(c_i, t_i)``
    1.99 +            """
   1.100 +            # c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p.
   1.101 +            ls = decrypt_gammas(gammas)
   1.102 +            ci = sum(ls) - sum(dijs)
   1.103 +            # (b) pick random t_i in (Z_p)^2.
   1.104 +            t1 = random_number(field. modulus)
   1.105 +            t2 = random_number(field. modulus)
   1.106 +            t = (t1, t2)
   1.107 +            # C_i = Com_ck(c_i, t_i).
   1.108 +            Ci = commitment.commit(ci.value, t1.value, t2.value)
   1.109 +            
   1.110 +            # Broadcast Ci.
   1.111 +            Cs = self.broadcast(self.players.keys(), self.players.keys(), repr(Ci))
   1.112 +            result = gatherResults(Cs)
   1.113 +            result.addCallbacks(step45, self.error_handler, callbackArgs=(alphas, gammas, alpha_randomness, 
   1.114 +                                                                          As, Bs, ai, bi, ci, r, s, t, dijs))
   1.115 +            return result
   1.116 +
   1.117 +        def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s):
   1.118 +            """(c) P_j do, towards every other party:
   1.119 +                   i. choose random d_i,j in Z_p^3
   1.120 +                   ii. compute and send 
   1.121 +            gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i.
   1.122 +            """
   1.123 +
   1.124 +            # (c) P_j do, towards every other party:
   1.125 +            dijs = [None] * len(self.players.keys())
   1.126 +            results = [None] * len(self.players.keys())
   1.127 +            pc = tuple(self.program_counter)
   1.128 +            for pi in self.players.keys():
   1.129 +                n = self.players[pi].pubkey[0]
   1.130 +                nsq = n * n
   1.131 +                # choose random d_i,j in Z_p^3
   1.132 +                dij = random_number(field.modulus**3)
   1.133 +                # Enc_ek_i(1;1)^d_ij
   1.134 +                enc = encrypt_r(1, 1, self.players[pi].pubkey)
   1.135 +                t1 = pow(enc, dij.value, nsq)
   1.136 +                # alpha_i^b_j.
   1.137 +                t2 = pow(alphas[pi - 1], bj.value, nsq)
   1.138 +                # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
   1.139 +                gammaij = (t2) * (t1) % nsq
   1.140 +                # Broadcast gamma_ij
   1.141 +                if pi != self.id:
   1.142 +                    self.protocols[pi].sendData(pc, PAILLIER, str(gammaij))
   1.143 +                    d = Deferred()
   1.144 +                    d.addCallbacks(lambda value: long(value), self.error_handler)
   1.145 +                    self._expect_data(pi, PAILLIER, d)
   1.146 +                else:
   1.147 +                    d = Deferred()
   1.148 +                    d.callback(gammaij)
   1.149 +                dijs[pi - 1] = dij
   1.150 +                results[pi - 1] = d
   1.151 +            result = gatherResults(results)
   1.152 +            self.schedule_callback(result, step3, alphas, alpha_randomness, 
   1.153 +                                   As, Bs, ai, bj, r, s, dijs)
   1.154 +            result.addErrback(self.error_handler)
   1.155 +            return result
   1.156 +
   1.157 +        def step2ab((alphas, As), ai, r, alpha_randomness):
   1.158 +            """2) Every party P_j does:
   1.159 +                  (a) choose random b_j, s_j in Z_p X (Z_p)^2.
   1.160 +
   1.161 +                  (b) compute B_j = Com_ck(b_j, s_j) and broadcast it.
   1.162 +            """
   1.163 +            # (a) choose random b_j, s_j in Z_p X (Z_p)^2.
   1.164 +            bj = random_number(field.modulus)
   1.165 +            s1 = random_number(field.modulus)
   1.166 +            s2 = random_number(field.modulus)
   1.167 +            # (b) compute B_j = Com_ck(b_j, s_j).
   1.168 +            Bj = commitment.commit(bj.value, s1.value, s2.value)
   1.169 +
   1.170 +            # Broadcast B_j.
   1.171 +            results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj))
   1.172 +            result = gatherResults(results)
   1.173 +            self.schedule_callback(result, step2c, As, alphas, alpha_randomness, 
   1.174 +                                   ai, bj, r, (s1, s2))
   1.175 +            result.addErrback(self.error_handler)
   1.176 +            return result
   1.177 +        
   1.178 +        # 1) Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2,
   1.179 +        #    compute alpha_i = Enc_eki(a_i) and Ai = Com_ck(a_i, r_i), and
   1.180 +        #    broadcast them.
   1.181 +
   1.182 +        # Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2
   1.183 +        ai = random_number(field.modulus)
   1.184 +        r1 = random_number(field.modulus)
   1.185 +        r2 = random_number(field.modulus)
   1.186 +
   1.187 +        # compute alpha_i = Enc_eki(a_i) 
   1.188 +        n, g = self.players[self.id].pubkey
   1.189 +        alpha_randomness = rand.randint(1, long(n))
   1.190 +        alphai = encrypt_r(ai.value, alpha_randomness, (n, g))
   1.191 +        # and A_i = Com_ck(a_i, r_i).
   1.192 +        Ai = commitment.commit(ai.value, r1.value, r2.value)
   1.193 +
   1.194 +        # broadcast alpha_i and A_i.
   1.195 +        ds = self.broadcast(sorted(self.players.keys()), sorted(self.players.keys()), str(alphai) + ":" + repr(Ai))
   1.196 +
   1.197 +        result = gatherResults(ds)
   1.198 +        def split_alphas_and_As(ls):
   1.199 +            alphas = []
   1.200 +            As = []
   1.201 +            for x in ls:
   1.202 +                alpha, Ai = x.split(':')
   1.203 +                alphas.append(long(alpha))
   1.204 +                As.append(Ai)
   1.205 +            return alphas, As
   1.206 +        self.schedule_callback(result, split_alphas_and_As)
   1.207 +        self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
   1.208 +        result.addErrback(self.error_handler)
   1.209 +        return result
   1.210 +                
   1.211 +
   1.212      def error_handler(self, ex):
   1.213          print "Error: ", ex
   1.214          return ex
     2.1 --- a/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     2.2 +++ b/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     2.3 @@ -567,3 +567,60 @@
     2.4          z2 = runtime._cmul(y2, x2, self.Zp)
     2.5          self.assertEquals(z2, None)
     2.6          return z2
     2.7 +
     2.8 +
     2.9 +class TripleGenTest(RuntimeTestCase):
    2.10 +    """Test for generation of triples."""
    2.11 +    
    2.12 +    # Number of players.
    2.13 +    num_players = 3
    2.14 + 
    2.15 +    runtime_class = OrlandiRuntime
    2.16 + 
    2.17 +    timeout = 240
    2.18 +
    2.19 +    @protocol
    2.20 +    def test_tripleGen(self, runtime):
    2.21 +        """Test the triple_gen command."""
    2.22 +
    2.23 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.24 +
    2.25 +        def check((a, b, c)):
    2.26 +            self.assertEquals(c, a * b)
    2.27 +
    2.28 +        def open((a, b, c, _)):
    2.29 +            d1 = runtime.open(a)
    2.30 +            d2 = runtime.open(b)
    2.31 +            d3 = runtime.open(c)
    2.32 +            d = gatherResults([d1, d2, d3])
    2.33 +            d.addCallback(check)
    2.34 +            return d
    2.35 +        d = runtime.triple_gen(self.Zp)
    2.36 +        d.addCallbacks(open, runtime.error_handler)
    2.37 +        return d
    2.38 +
    2.39 +    @protocol
    2.40 +    def test_tripleGen2(self, runtime):
    2.41 +        """Test the triple_gen command."""
    2.42 +
    2.43 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.44 +
    2.45 +        def check((a, b, c, dx, dy, dz)):
    2.46 +            self.assertEquals(c, a * b)
    2.47 +            self.assertEquals(dz, dx * dy)
    2.48 +
    2.49 +        def open(((a, b, c, control), (x, y, z, _))):
    2.50 +            d1 = runtime.open(a)
    2.51 +            d2 = runtime.open(b)
    2.52 +            d3 = runtime.open(c)
    2.53 +            dx = runtime.open(x)
    2.54 +            dy = runtime.open(y)
    2.55 +            dz = runtime.open(z)
    2.56 +            d = gatherResults([d1, d2, d3, dx, dy, dz])
    2.57 +            d.addCallback(check)
    2.58 +            return d
    2.59 +        t1 = runtime.triple_gen(self.Zp)
    2.60 +        t2 = runtime.triple_gen(self.Zp)
    2.61 +        d = gatherResults([t1, t2])
    2.62 +        d.addCallbacks(open, runtime.error_handler)
    2.63 +        return d