viff

changeset 660:7209f53f0d73

Make double_share_random verify the sharings. If the verification goes well, then a Deferred is returned which will callback with the double shares. If it fails because the shares were inconsistent or because they recombine to different values, then the Deferred will trigger its errback instead with an AssertionError.
author Martin Geisler <mg@daimi.au.dk>
date Sun, 13 Apr 2008 15:02:16 +0200
parents dfdfd16a376a
children d66a147bbea6 2329d4321c4e
files viff/runtime.py
diffstat 1 files changed, 71 insertions(+), 7 deletions(-) [+]
line diff
     1.1 --- a/viff/runtime.py	Sat Apr 12 23:52:36 2008 +0200
     1.2 +++ b/viff/runtime.py	Sun Apr 13 15:02:16 2008 +0200
     1.3 @@ -44,7 +44,7 @@
     1.4  from viff.util import wrapper, rand
     1.5  
     1.6  from twisted.internet import reactor
     1.7 -from twisted.internet.defer import Deferred, DeferredList, succeed
     1.8 +from twisted.internet.defer import Deferred, DeferredList, gatherResults
     1.9  from twisted.internet.protocol import ClientFactory, ServerFactory
    1.10  from twisted.protocols.basic import Int16StringReceiver
    1.11  
    1.12 @@ -1045,14 +1045,78 @@
    1.13          svec2 = Matrix([d2_shares]).transpose()
    1.14  
    1.15          # Apply the hyper-invertible matrix to svec1 and svec2.
    1.16 -        rvec1 = (self._hyper * svec1).transpose()
    1.17 -        rvec2 = (self._hyper * svec2).transpose()
    1.18 +        rvec1 = (self._hyper * svec1)
    1.19 +        rvec2 = (self._hyper * svec2)
    1.20  
    1.21 -        # TODO: verify sharings
    1.22 +        # Get back to normal lists of shares.
    1.23 +        svec1 = svec1.transpose().rows[0]
    1.24 +        svec2 = svec2.transpose().rows[0]
    1.25 +        rvec1 = rvec1.transpose().rows[0]
    1.26 +        rvec2 = rvec2.transpose().rows[0]
    1.27  
    1.28 -        # Return the first T shares (the ones that was not opened in
    1.29 -        # the verifying step.
    1.30 -        return succeed((rvec1.rows[0][:T], rvec2.rows[0][:T]))
    1.31 +        def verify(shares):
    1.32 +            """Verify shares.
    1.33 +
    1.34 +            It is checked that they correspond to polynomial of the
    1.35 +            expected degrees and that they can be recombined to the
    1.36 +            same value.
    1.37 +
    1.38 +            If the verification succeeds, the T double shares are
    1.39 +            returned, otherwise the errback is called.
    1.40 +            """
    1.41 +            si_1, si_2 = shares
    1.42 +
    1.43 +            # TODO: This is necessary since shamir.recombine expects
    1.44 +            # to receive a list of *pairs* of field elements.
    1.45 +            si_1 = map(lambda (i, s): (field(i+1), s), enumerate(si_1))
    1.46 +            si_2 = map(lambda (i, s): (field(i+1), s), enumerate(si_2))
    1.47 +
    1.48 +            # Verify the sharings. If any of the assertions fail and
    1.49 +            # raise an exception, the errbacks will be called on the
    1.50 +            # double share returned by double_share_random.
    1.51 +            assert shamir.verify_sharing(si_1, d1), "Could not verify si_1"
    1.52 +            assert shamir.verify_sharing(si_2, d2), "Could not verify si_2"
    1.53 +            assert shamir.recombine(si_1[:d1+1]) == shamir.recombine(si_2[:d2+1]), \
    1.54 +                "Shares do not recombine to the same value"
    1.55 +
    1.56 +            # If we reach this point the n - T shares were verified
    1.57 +            # and we can safely return the first T shares.
    1.58 +            return (rvec1[:T], rvec2[:T])
    1.59 +
    1.60 +        def exchange(shares):
    1.61 +            """Exchange and (if possible) verify shares."""
    1.62 +            svec1, svec2 = shares
    1.63 +            pc = tuple(self.program_counter)
    1.64 +
    1.65 +            # We send our shares to the verifying players.
    1.66 +            for offset, (s1, s2) in enumerate(zip(svec1, svec2)):
    1.67 +                if T+1+offset != self.id:
    1.68 +                    self.protocols[T+1+offset].sendShare(pc, s1)
    1.69 +                    self.protocols[T+1+offset].sendShare(pc, s2)
    1.70 +
    1.71 +            if self.id > T:
    1.72 +                # The other players will send us their shares of si_1
    1.73 +                # and si_2 and we will verify it.
    1.74 +                si_1 = []
    1.75 +                si_2 = []
    1.76 +                for peer_id in inputters:
    1.77 +                    if self.id == peer_id:
    1.78 +                        si_1.append(Share(self, field, svec1[peer_id - T - 1]))
    1.79 +                        si_2.append(Share(self, field, svec2[peer_id - T - 1]))
    1.80 +                    else:
    1.81 +                        si_1.append(self._expect_share(peer_id, field))
    1.82 +                        si_2.append(self._expect_share(peer_id, field))
    1.83 +                result = gatherResults([gatherResults(si_1), gatherResults(si_2)])
    1.84 +                self.schedule_callback(result, verify)
    1.85 +                return result
    1.86 +            else:
    1.87 +                # We cannot verify anything, so we just return the
    1.88 +                # first T shares.
    1.89 +                return (rvec1[:T], rvec2[:T])
    1.90 +
    1.91 +        result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
    1.92 +        self.schedule_callback(result, exchange)
    1.93 +        return result
    1.94  
    1.95      @increment_pc
    1.96      def get_triple(self, field):