# HG changeset patch # User Janus Dam Nielsen <[email protected]> # Date 1254816324 -7200 # Node ID 42d95e56edf626b2a2c8535e5bfbe856a1e82a3b # Parent 7fe8f5835b61c495be6eb807cae043f6aa1fd908 Implemented secret sharing command.
diff --git a/viff/orlandi.py b/viff/orlandi.py --- a/viff/orlandi.py +++ b/viff/orlandi.py @@ -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 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 @@ -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 _______________________________________________ viff-patches mailing list [email protected] http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
