## viff

### changeset 1233:a3d5284eea19

Generate a list of random triples based on the security parameter s.
author Janus Dam Nielsen Wed, 07 Oct 2009 12:02:12 +0200 f5b89b88b8c8 82e3597871ae viff/orlandi.py viff/test/test_orlandi_runtime.py 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.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.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.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.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.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.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.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.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.299 +            return result
1.300 +
1.301 +        result = gatherResults(M)
1.302 +        self.schedule_callback(result, step3)
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.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)