[viff-devel] [PATCH 02 of 12] Implemented secret sharing command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen <janus.nielsen at alexandra.dk>
# Date 1245394849 -7200
# Node ID f780a9ea514acb7de9d70022a8845938599696c8
# Parent  15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
Implemented secret sharing command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -67,3 +67,112 @@
         """Initialize runtime."""
         Runtime.__init__(self, player, threshold, options)
         self.threshold = self.num_players - 1
+
+    def _Com(self, x, rho):
+        return x + rho[0] + rho[1]
+
+    def output(self, share, receivers=None, threshold=None):
+        return self.open(share, receivers, threshold)
+
+    def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
+        """Send the share xim, rhoi, and the commitment Cx to party other_id."""
+        self.protocols[other_id].sendShare(pc, xi)
+        self.protocols[other_id].sendShare(pc, rhoi[0])
+        self.protocols[other_id].sendShare(pc, rhoi[1])
+        self.protocols[other_id].sendShare(pc, Cx)
+
+    def _expect_orlandi_share(self, peer_id, field):
+        """Waits for a number x, rho, and the commitment for x. """
+        xi = self._expect_share(peer_id, field)
+        rhoi1 = self._expect_share(peer_id, field)
+        rhoi2 = self._expect_share(peer_id, field)
+        Cx = self._expect_share(peer_id, field)
+        sls = ShareList([xi, rhoi1, rhoi2, Cx])
+        def combine(ls):
+            if len(ls) is not 4:
+                raise OrlandiException("Cannot share number, trying to create share," + \
+                                           " but there are too few or too many components.")
+            s1, xi = ls[0]
+            s2, rhoi1 = ls[1]
+            s3, rhoi2 = ls[2]
+            s4, Cx = ls[3]
+            if not (s1 and s2 and s3 and s4):
+                raise OrlandiException("Cannot share number, trying to create share," + \
+                                           " but a component did arrive properly.")
+            return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cx)
+        sls.addCallbacks(combine, self.error_handler)
+        return sls
+
+    @increment_pc
+    def secret_share(self, inputters, field, number=None, threshold=None):
+        """Share the value, number, among all the parties using additive shareing.
+
+        To share an element x in Z_{p}, choose random x_{1}, ..., x_{n-1} in Z_{p}, 
+        define x_{n} = x - SUM_{i=1}^{n-1} x_{i} mod p.
+        Choose random values rho_{x,1}, ..., rho_{x,n} in (Z_{p})^2, define 
+        rho_x = SUM_{i=1}^{n} rho_{x,i} and C_{x} = Com_{ck}(x, p_{x}).
+        
+        Send [x]_{i} = (x_{i}, rho_{x,i}, C_{x}) to party P_{i}.
+        """
+        assert number is None or self.id in inputters
+        self.threshold = self.num_players - 1
+
+        def additive_shares_with_rho(x):
+            """Returns a tuple of a list of tuples (player id, share, rho) and rho.
+
+            Chooses random elements x_{1}, ..., x_{n-1} in field and x_{n} st. 
+            x_{n} = x - Sum_{i=1}^{n-1} x_{i}.
+            Chooses random pair of elements rho_{1}, ..., rho_{n} in field_{2}
+            and define rho_{n} = Sum_{i=1}^{n} rho_{i}.
+            Returns a pair of ((player id, x_{i}, rho_{i}), rho).
+            """ 
+            shares = []
+            rhos = []
+            sum = field(0)
+            rho1 = field(0)
+            rho2 = field(0)
+            for i in xrange(1, self.num_players):
+                xi = field(rand.randint(0, field.modulus - 1))
+                rhoi1 = field(rand.randint(0, field.modulus - 1))
+                rhoi2 = field(rand.randint(0, field.modulus - 1))
+                sum += xi
+                rho1 += rhoi1
+                rho2 += rhoi2
+                shares.append((i, xi, (rhoi1, rhoi2)))    
+            xn = field(x) - sum
+            rhon1 = field(rand.randint(0, field.modulus - 1))
+            rhon2 = field(rand.randint(0, field.modulus - 1))
+            shares.append((self.num_players, xn, (rhon1, rhon2)))
+            rho1 += rhon1
+            rho2 += rhon2
+            return shares, (rho1, rho2)
+
+        # Send [x]_{i} = (x_{i}, rho_{x,i}, C_{x}) to party P_{i}.
+        results = []
+        for peer_id in inputters:
+            if peer_id == self.id:
+                pc = tuple(self.program_counter)
+                shares, rho = additive_shares_with_rho(number)
+                Cx = self._Com(number, rho)
+                # Distribute the shares
+                for other_id, xi, rhoi in shares:
+                    if other_id == self.id:
+                        results.append(OrlandiShare(self, field, xi, rhoi, Cx))
+                    else:
+                        # Send xi, rhoi, and commitment
+                        self._send_orlandi_share(other_id, pc, xi, rhoi, Cx)
+            else:
+                # Expect xi, rhoi, and commitment
+                results.append(self._expect_orlandi_share(peer_id, field))
+
+        # do actual communication
+        self.activate_reactor()
+
+        # Unpack a singleton list.
+        if len(results) == 1:
+            return results[0]
+        return results
+
+    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
@@ -31,3 +31,21 @@
     num_players = 3
 
     runtime_class = OrlandiRuntime
+
+    @protocol
+    def test_secret_share(self, runtime):
+        """Test sharing of random numbers."""
+
+        def check((xi, (rho1, rho2), Cr)):
+            # Check that we got the expected number of shares.
+            self.assert_type(xi, FieldElement)
+            self.assert_type(rho1, FieldElement)
+            self.assert_type(rho2, FieldElement)
+            self.assert_type(Cr, FieldElement)
+
+        if 1 == runtime.id:
+            share = runtime.secret_share([1], self.Zp, 42)
+        else:
+            share = runtime.secret_share([1], self.Zp)
+        share.addCallback(check)
+        return share