viff

changeset 1233:a3d5284eea19

Generate a list of random triples based on the security parameter s.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Wed, 07 Oct 2009 12:02:12 +0200
parents f5b89b88b8c8
children 82e3597871ae
files viff/orlandi.py viff/test/test_orlandi_runtime.py
diffstat 2 files changed, 328 insertions(+), 4 deletions(-) [+]
line diff
     1.1 --- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     1.2 +++ b/viff/orlandi.py	Wed Oct 07 12:02:12 2009 +0200
     1.3 @@ -55,6 +55,9 @@
     1.4      """
     1.5  
     1.6      def __init__(self, runtime, field, value=None, rho=None, commitment=None):
     1.7 +        self.share = value
     1.8 +        self.rho = rho
     1.9 +        self.commitment = commitment
    1.10          Share.__init__(self, runtime, field, (value, rho, commitment))
    1.11  
    1.12  
    1.13 @@ -81,6 +84,9 @@
    1.14          """Initialize runtime."""
    1.15          Runtime.__init__(self, player, threshold, options)
    1.16          self.threshold = self.num_players - 1
    1.17 +        self.s = 1
    1.18 +        self.d = 0
    1.19 +        self.s_lambda = 1
    1.20  
    1.21      def compute_delta(self, d):
    1.22          def product(j):
    1.23 @@ -1005,6 +1011,293 @@
    1.24  
    1.25          return result
    1.26  
    1.27 +    def random_triple(self, field):
    1.28 +        """Generate a list of triples ``(a, b, c)`` where ``c = a * b``.
    1.29 +
    1.30 +        The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model.
    1.31 +
    1.32 +        """
    1.33 +        self.program_counter[-1] += 1
    1.34 +
    1.35 +        number_of_multiplications = 1
    1.36 +        M = []
    1.37 +        
    1.38 +        for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * number_of_multiplications):
    1.39 +            M.append(self.triple_test(field))
    1.40 +
    1.41 +        def step3(ls):
    1.42 +            """Coin-flip a subset test_set of M of size lambda(2d + 1)M."""
    1.43 +            size = self.s_lambda * (2 * self.d + 1) * number_of_multiplications
    1.44 +            inx = 0
    1.45 +            p_half = field.modulus // 2
    1.46 +            def coin_flip(v, ls, test_set):
    1.47 +                candidate = ls.pop(0)
    1.48 +                if p_half > v:
    1.49 +                    test_set.append(candidate)
    1.50 +                else:
    1.51 +                    ls.append(candidate)
    1.52 +                if size > len(test_set):
    1.53 +                    r = self.random_share(field)
    1.54 +                    r = self.output(r)
    1.55 +                    self.schedule_callback(r, coin_flip, ls, test_set)
    1.56 +                    r.addErrback(self.error_handler)
    1.57 +                    return r
    1.58 +                return ls, test_set
    1.59 +            r = self.random_share(field)
    1.60 +            r = self.output(r)
    1.61 +            self.schedule_callback(r, coin_flip, ls, [])
    1.62 +            r.addErrback(self.error_handler)
    1.63 +            return r            
    1.64 +
    1.65 +        def step45(lists):
    1.66 +            """For all i in test_set the parties reveal 
    1.67 +            the randomness used for TripleTest() and checks that
    1.68 +            the randomness is consistent with the actual values."""
    1.69 +            M_without_test_set = lists[0]
    1.70 +            T = lists[1]
    1.71 +
    1.72 +            def defer_share(xi, (rho1, rho2), commitment):
    1.73 +                d1 = Deferred()
    1.74 +                d2 = Deferred()
    1.75 +                d3 = Deferred()
    1.76 +                d4 = Deferred()
    1.77 +                d1.callback(xi)
    1.78 +                d2.callback(rho1)
    1.79 +                d3.callback(rho2)
    1.80 +                d4.callback(commitment)
    1.81 +                return gatherResults([d1, d2, d3, d4])
    1.82 +
    1.83 +            def get_share(x, ls):
    1.84 +                share = ls[x * 4]
    1.85 +                rho1 = ls[x * 4 + 1]
    1.86 +                rho2 = ls[x * 4 + 2]
    1.87 +                commitment = ls[x * 4 + 3]
    1.88 +                return (share, rho1, rho2, commitment)
    1.89 +
    1.90 +            def send_share(player_id, pc, a):
    1.91 +                self._send_orlandi_share(player_id, pc, a.share, a.rho, a.commitment) 
    1.92 +                
    1.93 +            def receive_shares(player_id):
    1.94 +                Cx = Deferred()
    1.95 +                xi = self._expect_share(player_id, field)
    1.96 +                rho1 = self._expect_share(player_id, field)
    1.97 +                rho2 = self._expect_share(player_id, field)
    1.98 +                self._expect_data(player_id, TEXT, Cx)
    1.99 +                Cx.addCallbacks(lambda Cx: commitment.deserialize(Cx), 
   1.100 +                                        self.error_handler)
   1.101 +                return gatherResults([xi, rho1, rho2, Cx])
   1.102 +
   1.103 +            def send_long(player_id, pc, l):
   1.104 +                self.protocols[player_id].sendData(pc, TEXT, str(l))
   1.105 +
   1.106 +            def receive_long(player_id):
   1.107 +                l = Deferred()
   1.108 +                self._expect_data(player_id, TEXT, l)
   1.109 +                l.addCallbacks(lambda x: long(x), self.error_handler)
   1.110 +                return l
   1.111 +
   1.112 +            def defer_value(l):
   1.113 +                d = Deferred()
   1.114 +                d.callback(l)
   1.115 +                return d
   1.116 +
   1.117 +            def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas):
   1.118 +                """So if B receives ai, bi, dij, ri, si, and the randomness used in the
   1.119 +                computation of alpha, he then checks that:
   1.120 +                1) the alpha_i he received is equals to the encryption of ai and the
   1.121 +                commitment he received, Ai, is equal to the commitment of ai and ri
   1.122 +                2) the commitment he received, Bj, is equal to the commitment of bj and sj
   1.123 +                3) the gammaij he received is equal to the gammaij he now computes based on
   1.124 +                the values he reveives
   1.125 +                4) a, b, c is a triple, a * b = c
   1.126 +                5) ai, bi < p and dij < p^3
   1.127 +                """
   1.128 +                a = 0
   1.129 +                a_rho1 = 0
   1.130 +                a_rho2 = 0
   1.131 +                b = 0
   1.132 +                b_rho1 = 0
   1.133 +                b_rho2 = 0
   1.134 +                c = 0
   1.135 +                c_rho1 = 0
   1.136 +                c_rho2 = 0
   1.137 +                
   1.138 +                for x in xrange(len(ais)):
   1.139 +                    (ai, a_rhoi1, a_rhoi2, A) = ais[x]
   1.140 +                    (bi, b_rhoi1, b_rhoi2, B) = bis[x]
   1.141 +                    (ci, c_rhoi1, c_rhoi2, C) = cis[x]
   1.142 +                    # 5) ai, bi < p...
   1.143 +                    if ai >= field.modulus:
   1.144 +                        raise OrlandiException("Inconsistent share ai, ai >= p: %i" % ai)
   1.145 +                    if bi >= field.modulus:
   1.146 +                        raise OrlandiException("Inconsistent share bi, bi >= p: %i" % bi)
   1.147 +                    a += ai
   1.148 +                    a_rho1 += a_rhoi1
   1.149 +                    a_rho2 += a_rhoi2
   1.150 +                    b += bi
   1.151 +                    b_rho1 += b_rhoi1
   1.152 +                    b_rho2 += b_rhoi2
   1.153 +                    c += ci
   1.154 +                    c_rho1 += c_rhoi1
   1.155 +                    c_rho2 += c_rhoi2
   1.156 +                    # 1) the alpha_i he received is equals to the encryption of ai...
   1.157 +                    alphai = encrypt_r(ai.value, alpha_randomness[x],
   1.158 +                                       self.players[x + 1].pubkey)
   1.159 +                    if not(alphas[x] == alphai):
   1.160 +                        raise OrlandiException("Inconsistent alpha from player %i, %i, %i" % (x + 1, alphas[x], alphai))
   1.161 +
   1.162 +                A1 = commitment.commit(a.value, a_rho1.value, a_rho2.value)
   1.163 +                B1 = commitment.commit(b.value, b_rho1.value, b_rho2.value)
   1.164 +                C1 = commitment.commit(c.value, c_rho1.value, c_rho2.value)
   1.165 +
   1.166 +                # 1) ... and the commitment he received, Ai, is equal
   1.167 +                # to the commitment of ai and ri.
   1.168 +                if A1 != A:
   1.169 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A))
   1.170 +                # 2) the commitment he received, Bj, is equal to the commitment of bj and sj.
   1.171 +                if B1 != B:
   1.172 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B))
   1.173 +                if C1 != C:
   1.174 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (c, C1, C))
   1.175 +                # 4) a, b, c is a triple, a * b = c
   1.176 +                if a * b != c:
   1.177 +                    raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c))
   1.178 +
   1.179 +
   1.180 +                # 3) the gammaij he received is equal to the gammaij he now computes based on
   1.181 +                # the values he reveives
   1.182 +                for j in xrange(len(ais)):
   1.183 +                    n = self.players[self.id].pubkey[0]
   1.184 +                    nsq = n * n
   1.185 +                    dij = dijs[j]
   1.186 +                    # 5) ... and dij < p^3.
   1.187 +                    if dij >= (field.modulus**3):
   1.188 +                        raise OrlandiException("Inconsistent random value dij %i from player %i" % (dij, j + 1))
   1.189 +                    # Enc_ek_i(1;1)^d_ij
   1.190 +                    enc = encrypt_r(1, 1, self.players[self.id].pubkey)
   1.191 +                    t1 = pow(enc, dij.value, nsq)
   1.192 +                    # alpha_i^b_j.
   1.193 +                    t2 = pow(alphas[self.id - 1], bis[j][0].value, nsq)
   1.194 +                    # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
   1.195 +                    gammaij = (t2) * (t1) % nsq
   1.196 +                    if gammaij != gammas[j]:
   1.197 +                        raise OrlandiException("Inconsistent gammaij, %i, %i" % (gammaij, gammas[j]))
   1.198 +
   1.199 +                return True
   1.200 +
   1.201 +            dls_all = []
   1.202 +            for (a, b, c, (alphas, alpha_randomness, gammas, dijs)) in T:
   1.203 +                ds_a = [None] * len(self.players)
   1.204 +                ds_b = [None] * len(self.players)
   1.205 +                ds_c = [None] * len(self.players)
   1.206 +                ds_alpha_randomness = [None] * len(self.players)
   1.207 +                ds_dijs = [None] * len(self.players)
   1.208 +                pc = tuple(self.program_counter)
   1.209 +
   1.210 +                for player_id in xrange(1, len(self.players.keys()) + 1):
   1.211 +                    if player_id == self.id:
   1.212 +                        ds_a[player_id - 1] = defer_share(a.share, a.rho, a.commitment)
   1.213 +                        ds_b[player_id - 1] = defer_share(b.share, b.rho, b.commitment)
   1.214 +                        ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment)
   1.215 +                        ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness)
   1.216 +                        ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1])
   1.217 +                    # Receive and recombine shares if this player is a receiver.
   1.218 +                    else:
   1.219 +                        send_share(player_id, pc, a)
   1.220 +                        send_share(player_id, pc, b)
   1.221 +                        send_share(player_id, pc, c)
   1.222 +                        send_long(player_id, pc, alpha_randomness)
   1.223 +                        self.protocols[player_id].sendShare(pc, dijs[player_id - 1])
   1.224 +
   1.225 +                        ds_a[player_id - 1] = receive_shares(player_id)
   1.226 +                        ds_b[player_id - 1] = receive_shares(player_id)
   1.227 +                        ds_c[player_id - 1] = receive_shares(player_id)
   1.228 +                        ds_alpha_randomness[player_id - 1] = receive_long(player_id)
   1.229 +                        ds_dijs[player_id - 1] = self._expect_share(player_id, field)
   1.230 +                dls_a = gatherResults(ds_a)
   1.231 +                dls_b = gatherResults(ds_b)
   1.232 +                dls_c = gatherResults(ds_c)
   1.233 +                dls_dijs = gatherResults(ds_dijs)
   1.234 +                dls_alpha_randomness = gatherResults(ds_alpha_randomness)
   1.235 +
   1.236 +            dls = gatherResults([dls_a, dls_b, dls_c, dls_alpha_randomness, dls_dijs])
   1.237 +            dls.addCallbacks(check, self.error_handler, callbackArgs=[alphas, gammas])
   1.238 +            dls_all.append(dls)
   1.239 +
   1.240 +            def result(x):
   1.241 +                ls = []
   1.242 +                for a, b, c, _ in M_without_test_set:
   1.243 +                    ls.append((a, b, c))
   1.244 +                return ls
   1.245 +
   1.246 +            dls_all = gatherResults(dls_all)
   1.247 +            dls_all.addCallbacks(result, self.error_handler)
   1.248 +            return dls_all
   1.249 +
   1.250 +        def step6(M_without_test_set):
   1.251 +            """Partition M without test_set in number_of_multiplications
   1.252 +            random subsets M_i of size (2d + 1).
   1.253 +            """
   1.254 +            subsets = []
   1.255 +            size = 2 * self.d + 1
   1.256 +            for x in xrange(number_of_multiplications):
   1.257 +                subsets.append([])
   1.258 +
   1.259 +            def put_in_set(v, M_without_test_set, subsets):
   1.260 +                if 0 == len(M_without_test_set):
   1.261 +                    return subsets
   1.262 +                v = v.value % number_of_multiplications
   1.263 +                if size > len(subsets[v]):
   1.264 +                    subsets[v].append(M_without_test_set.pop(0))
   1.265 +                r = self.random_share(field)
   1.266 +                r = self.output(r)
   1.267 +                self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
   1.268 +                r.addErrback(self.error_handler)
   1.269 +                return r
   1.270 +            r = self.random_share(field)
   1.271 +            r = self.output(r)
   1.272 +            self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
   1.273 +            r.addErrback(self.error_handler)
   1.274 +            return r
   1.275 +            
   1.276 +
   1.277 +        def step7(Msets):
   1.278 +            """For i = 1,...,M do:
   1.279 +            a) [a] <- Fpp(rand,...), [b] <- Fpp(rand,...)
   1.280 +            b) [r] <- Fpp(rand,...), 
   1.281 +            c) [c] <- LTMUL([a], [b], M_i)
   1.282 +            d) Open([c] + [r])
   1.283 +            """
   1.284 +            ds = []
   1.285 +            for Mi in Msets:
   1.286 +                a = self.random_share(field)
   1.287 +                b = self.random_share(field)
   1.288 +                r = self.random_share(field)
   1.289 +                c = self.leak_tolerant_mul(a, b, Mi)
   1.290 +                d = self.open(c + r)
   1.291 +                def return_abc(x, a, b, c):
   1.292 +                    return a, b, c
   1.293 +                d.addCallbacks(return_abc, self.error_handler, callbackArgs=(a, b, c))
   1.294 +                ds.append(d)
   1.295 +            result = gather_shares(ds)
   1.296 +            def triples(ls):
   1.297 +                return ls
   1.298 +            result.addCallbacks(triples, self.error_handler)
   1.299 +            return result
   1.300 +
   1.301 +        result = gatherResults(M)
   1.302 +        self.schedule_callback(result, step3)
   1.303 +        result.addErrback(self.error_handler)
   1.304 +        self.schedule_callback(result, step45)
   1.305 +        self.schedule_callback(result, step6)
   1.306 +        self.schedule_callback(result, step7)
   1.307 +
   1.308 +        # do actual communication
   1.309 +        self.activate_reactor()
   1.310 +
   1.311 +        return result
   1.312 +
   1.313 +
   1.314      def error_handler(self, ex):
   1.315          print "Error: ", ex
   1.316          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	Wed Oct 07 12:02:12 2009 +0200
     2.3 @@ -548,8 +548,8 @@
     2.4          x1 = 42
     2.5          y1 = 7
     2.6  
     2.7 -        d = 4
     2.8 -        
     2.9 +        runtime.d = 2
    2.10 +
    2.11          def check(v):
    2.12              self.assertEquals(v, x1 * y1)
    2.13   
    2.14 @@ -557,7 +557,7 @@
    2.15          y2 = runtime.shift([2], self.Zp, y1)
    2.16  
    2.17          M = []
    2.18 -        for j in xrange(1, 2*d + 2):
    2.19 +        for j in xrange(1, 2*runtime.d + 2):
    2.20              M.append(_get_triple(self, self.Zp))
    2.21          z2 = runtime.leak_tolerant_mul(x2, y2, M)
    2.22          d = runtime.open(z2)
    2.23 @@ -577,7 +577,7 @@
    2.24   
    2.25      runtime_class = OrlandiRuntime
    2.26   
    2.27 -    timeout = 240
    2.28 +    timeout = 1600
    2.29  
    2.30      @protocol
    2.31      def test_tripleGen(self, runtime):
    2.32 @@ -645,3 +645,34 @@
    2.33          d = runtime.triple_test(self.Zp)
    2.34          d.addCallbacks(open, runtime.error_handler)
    2.35          return d
    2.36 +
    2.37 +    @protocol
    2.38 +    def test_random_triple(self, runtime):
    2.39 +        """Test the triple_combiner command."""
    2.40 +
    2.41 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.42 +
    2.43 +        def check(ls):
    2.44 +            for x in xrange(len(ls) // 3):
    2.45 +                a = ls[x * 3]
    2.46 +                b = ls[x * 3 + 1]
    2.47 +                c = ls[x * 3 + 2]
    2.48 +                self.assertEquals(c, a * b)
    2.49 +
    2.50 +        def open(ls):
    2.51 +            ds = []
    2.52 +            for (a, b, c) in ls:
    2.53 +                d1 = runtime.open(a)
    2.54 +                d2 = runtime.open(b)
    2.55 +                d3 = runtime.open(c)
    2.56 +                ds.append(d1)
    2.57 +                ds.append(d2)
    2.58 +                ds.append(d3)
    2.59 +
    2.60 +            d = gatherResults(ds)
    2.61 +            d.addCallback(check)
    2.62 +            return d
    2.63 +        d = runtime.random_triple(self.Zp)
    2.64 +        d.addCallbacks(open, runtime.error_handler)
    2.65 +        return d
    2.66 +