changeset 1223:42d95e56edf6

Implemented secret sharing command.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Oct 2009 10:05:24 +0200
parents 7fe8f5835b61
children 7ed324dff36b
files viff/orlandi.py viff/test/test_orlandi_runtime.py
diffstat 2 files changed, 145 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
@@ -15,8 +15,18 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
 
+from twisted.internet.defer import Deferred
+
 from viff.runtime import Runtime, Share, ShareList, gather_shares
 from viff.util import rand
+from viff.constants import TEXT
+
+import commitment
+commitment.set_reference_string(23434347834783478783478L, 489237823478234783478020L)
+
+# import logging
+# LOG_FILENAME = 'logging_example.out'
+# logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,)
 
 class OrlandiException(Exception):
     pass
@@ -67,3 +77,115 @@
         """Initialize runtime."""
         Runtime.__init__(self, player, threshold, options)
         self.threshold = self.num_players - 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 *xi*, *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].sendData(pc, TEXT, repr(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)
+        Cx = Deferred()        
+        rhoi1 = self._expect_share(peer_id, field)
+        rhoi2 = self._expect_share(peer_id, field)
+        self._expect_data(peer_id, TEXT, Cx)
+        sls = ShareList([xi, rhoi1, rhoi2, Cx])
+        def combine(ls):
+            expected_num = 4;
+            if len(ls) is not expected_num:
+                raise OrlandiException("Cannot share number, trying to create a share,"
+                                       " expected %s components got %s." % (expected_num, len(ls)))
+            s1, xi = ls[0]
+            s2, rhoi1 = ls[1]
+            s3, rhoi2 = ls[2]
+            s4, Cx = ls[3]
+            Cxx = commitment.deserialize(Cx)
+            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), Cxx)
+        sls.addCallbacks(combine, self.error_handler)
+        return sls
+
+    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_x1, ..., rho_xn 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_xi, C_x)`` to party ``P_i``.
+        """
+        assert number is None or self.id in inputters
+        self.threshold = self.num_players - 1
+
+        self.program_counter[-1] += 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 Z_p^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 = 0
+            rho1 = 0
+            rho2 = 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 = commitment.commit(number, rho[0].value, rho[1].value)
+                # Distribute the shares
+                the_others = []
+                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
--- 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
@@ -21,9 +21,11 @@
 from viff.runtime import Share
 from viff.orlandi import OrlandiRuntime
 
-from viff.field import FieldElement
+from viff.field import FieldElement, GF
 from viff.passive import PassiveRuntime
 
+import commitment
+
 class OrlandiBasicCommandsTest(RuntimeTestCase):
     """Test for basic commands."""
 
@@ -31,3 +33,23 @@
     num_players = 3
 
     runtime_class = OrlandiRuntime
+
+    @protocol
+    def test_secret_share(self, runtime):
+        """Test sharing of random numbers."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        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, commitment.Commitment)
+
+        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