viff

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 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 @@ -15,8 +15,18 @@
     1.4  # You should have received a copy of the GNU Lesser General Public
     1.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     1.6  
     1.7 +from twisted.internet.defer import Deferred
     1.8 +
     1.9  from viff.runtime import Runtime, Share, ShareList, gather_shares
    1.10  from viff.util import rand
    1.11 +from viff.constants import TEXT
    1.12 +
    1.13 +import commitment
    1.14 +commitment.set_reference_string(23434347834783478783478L, 489237823478234783478020L)
    1.15 +
    1.16 +# import logging
    1.17 +# LOG_FILENAME = 'logging_example.out'
    1.18 +# logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,)
    1.19  
    1.20  class OrlandiException(Exception):
    1.21      pass
    1.22 @@ -67,3 +77,115 @@
    1.23          """Initialize runtime."""
    1.24          Runtime.__init__(self, player, threshold, options)
    1.25          self.threshold = self.num_players - 1
    1.26 +
    1.27 +    def output(self, share, receivers=None, threshold=None):
    1.28 +        return self.open(share, receivers, threshold)
    1.29 +
    1.30 +    def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
    1.31 +        """Send the share *xi*, *rhoi*, and the commitment *Cx* to party *other_id*."""
    1.32 +        self.protocols[other_id].sendShare(pc, xi)
    1.33 +        self.protocols[other_id].sendShare(pc, rhoi[0])
    1.34 +        self.protocols[other_id].sendShare(pc, rhoi[1])
    1.35 +        self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
    1.36 +
    1.37 +    def _expect_orlandi_share(self, peer_id, field):
    1.38 +        """Waits for a number ``x``, ``rho``, and the commitment for ``x``."""
    1.39 +        xi = self._expect_share(peer_id, field)
    1.40 +        Cx = Deferred()        
    1.41 +        rhoi1 = self._expect_share(peer_id, field)
    1.42 +        rhoi2 = self._expect_share(peer_id, field)
    1.43 +        self._expect_data(peer_id, TEXT, Cx)
    1.44 +        sls = ShareList([xi, rhoi1, rhoi2, Cx])
    1.45 +        def combine(ls):
    1.46 +            expected_num = 4;
    1.47 +            if len(ls) is not expected_num:
    1.48 +                raise OrlandiException("Cannot share number, trying to create a share,"
    1.49 +                                       " expected %s components got %s." % (expected_num, len(ls)))
    1.50 +            s1, xi = ls[0]
    1.51 +            s2, rhoi1 = ls[1]
    1.52 +            s3, rhoi2 = ls[2]
    1.53 +            s4, Cx = ls[3]
    1.54 +            Cxx = commitment.deserialize(Cx)
    1.55 +            if not (s1 and s2 and s3 and s4):
    1.56 +                raise OrlandiException("Cannot share number, trying to create share,"
    1.57 +                                       " but a component did arrive properly.")
    1.58 +            return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cxx)
    1.59 +        sls.addCallbacks(combine, self.error_handler)
    1.60 +        return sls
    1.61 +
    1.62 +    def secret_share(self, inputters, field, number=None, threshold=None):
    1.63 +        """Share the value, number, among all the parties using additive shareing.
    1.64 +
    1.65 +        To share an element ``x in Z_p``, choose random ``x_1, ..., x_n-1 in Z_p``, 
    1.66 +        define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
    1.67 +
    1.68 +        Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``, define 
    1.69 +        ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x, p_x)``.
    1.70 +        
    1.71 +        Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``.
    1.72 +        """
    1.73 +        assert number is None or self.id in inputters
    1.74 +        self.threshold = self.num_players - 1
    1.75 +
    1.76 +        self.program_counter[-1] += 1
    1.77 +
    1.78 +        def additive_shares_with_rho(x):
    1.79 +            """Returns a tuple of a list of tuples (player id, share, rho) and rho.
    1.80 +
    1.81 +            Chooses random elements ``x_1, ..., x_n-1`` in field and ``x_n`` st. 
    1.82 +            ``x_n = x - Sum_i=1^n-1 x_i``.
    1.83 +
    1.84 +            Chooses random pair of elements ``rho_1, ..., rho_n in Z_p^2``
    1.85 +            and define ``rho_n = Sum_i=1^n rho_i``.
    1.86 +
    1.87 +            Returns a pair of ``((player id, x_i, rho_i), rho)``.
    1.88 +            """ 
    1.89 +            shares = []
    1.90 +            rhos = []
    1.91 +            sum = 0
    1.92 +            rho1 = 0
    1.93 +            rho2 = 0
    1.94 +            for i in xrange(1, self.num_players):
    1.95 +                xi = field(rand.randint(0, field.modulus - 1))
    1.96 +                rhoi1 = field(rand.randint(0, field.modulus - 1))
    1.97 +                rhoi2 = field(rand.randint(0, field.modulus - 1))
    1.98 +                sum += xi
    1.99 +                rho1 += rhoi1
   1.100 +                rho2 += rhoi2
   1.101 +                shares.append((i, xi, (rhoi1, rhoi2)))    
   1.102 +            xn = field(x) - sum
   1.103 +            rhon1 = field(rand.randint(0, field.modulus - 1))
   1.104 +            rhon2 = field(rand.randint(0, field.modulus - 1))
   1.105 +            shares.append((self.num_players, xn, (rhon1, rhon2)))
   1.106 +            rho1 += rhon1
   1.107 +            rho2 += rhon2
   1.108 +            return shares, (rho1, rho2)
   1.109 +
   1.110 +        # Send ``[x]_i = (x_i, rho_x,i, C_x)`` to party ``P_i``.
   1.111 +        results = []
   1.112 +        for peer_id in inputters:
   1.113 +            if peer_id == self.id:
   1.114 +                pc = tuple(self.program_counter)
   1.115 +                shares, rho = additive_shares_with_rho(number)
   1.116 +                Cx = commitment.commit(number, rho[0].value, rho[1].value)
   1.117 +                # Distribute the shares
   1.118 +                the_others = []
   1.119 +                for other_id, xi, rhoi in shares:
   1.120 +                    if other_id == self.id:
   1.121 +                        results.append(OrlandiShare(self, field, xi, rhoi, Cx))
   1.122 +                    else:
   1.123 +                        # Send ``xi``, ``rhoi``, and commitment
   1.124 +                        self._send_orlandi_share(other_id, pc, xi, rhoi, Cx)
   1.125 +            else:
   1.126 +                # Expect ``xi``, ``rhoi``, and commitment
   1.127 +                results.append(self._expect_orlandi_share(peer_id, field))
   1.128 +        # do actual communication
   1.129 +        self.activate_reactor()
   1.130 +        # Unpack a singleton list.
   1.131 +        if len(results) == 1:
   1.132 +            return results[0]
   1.133 +        return results
   1.134 +
   1.135 +    def error_handler(self, ex):
   1.136 +        print "Error: ", ex
   1.137 +        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 @@ -21,9 +21,11 @@
     2.4  from viff.runtime import Share
     2.5  from viff.orlandi import OrlandiRuntime
     2.6  
     2.7 -from viff.field import FieldElement
     2.8 +from viff.field import FieldElement, GF
     2.9  from viff.passive import PassiveRuntime
    2.10  
    2.11 +import commitment
    2.12 +
    2.13  class OrlandiBasicCommandsTest(RuntimeTestCase):
    2.14      """Test for basic commands."""
    2.15  
    2.16 @@ -31,3 +33,23 @@
    2.17      num_players = 3
    2.18  
    2.19      runtime_class = OrlandiRuntime
    2.20 +
    2.21 +    @protocol
    2.22 +    def test_secret_share(self, runtime):
    2.23 +        """Test sharing of random numbers."""
    2.24 +
    2.25 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.26 +
    2.27 +        def check((xi, (rho1, rho2), Cr)):
    2.28 +            # Check that we got the expected number of shares.
    2.29 +            self.assert_type(xi, FieldElement)
    2.30 +            self.assert_type(rho1, FieldElement)
    2.31 +            self.assert_type(rho2, FieldElement)
    2.32 +            self.assert_type(Cr, commitment.Commitment)
    2.33 +
    2.34 +        if 1 == runtime.id:
    2.35 +            share = runtime.secret_share([1], self.Zp, 42)
    2.36 +        else:
    2.37 +            share = runtime.secret_share([1], self.Zp)
    2.38 +        share.addCallback(check)
    2.39 +        return share