viff

changeset 666:876f98730e4c

Merged bugfix.
author Martin Geisler <mg@daimi.au.dk>
date Sun, 13 Apr 2008 22:16:28 +0200
parents 2329d4321c4e 77ad363d79ae
children e41ce22ed035
files viff/runtime.py
diffstat 2 files changed, 121 insertions(+), 14 deletions(-) [+]
line diff
     1.1 --- a/viff/runtime.py	Sun Apr 13 22:03:51 2008 +0200
     1.2 +++ b/viff/runtime.py	Sun Apr 13 22:16:28 2008 +0200
     1.3 @@ -993,7 +993,7 @@
     1.4              d = self.open(share_x - a)
     1.5              e = self.open(share_y - b)
     1.6  
     1.7 -            # TODO: We ought to be able to simple do
     1.8 +            # TODO: We ought to be able to simply do
     1.9              #
    1.10              #   return d*e + d*y + e*x + c
    1.11              #
    1.12 @@ -1016,6 +1016,93 @@
    1.13          return result
    1.14  
    1.15      @increment_pc
    1.16 +    def single_share_random(self, T, degree, field):
    1.17 +        """Share a random secret.
    1.18 +
    1.19 +        The guarantee is that a number of shares are made and out of
    1.20 +        those, the T that are returned by this method will be correct
    1.21 +        sharings of a random number using C{degree} as the polynomial
    1.22 +        degree.
    1.23 +
    1.24 +        @param T: The number of shares output.
    1.25 +        @param degree: The degree of the polynomial.
    1.26 +        @param field: The field over which to share the secret.
    1.27 +        """
    1.28 +        # TODO: Move common code between single_share and
    1.29 +        # double_share_random out to their own methods.
    1.30 +        inputters = range(1, self.num_players + 1)
    1.31 +        if self._hyper is None:
    1.32 +            self._hyper = hyper(self.num_players, field)
    1.33 +
    1.34 +        # Generate a random element.
    1.35 +        si = rand.randint(0, field.modulus - 1)
    1.36 +
    1.37 +        # Every player shares the random value with two thresholds.
    1.38 +        shares = self.shamir_share(inputters, field, si, degree)
    1.39 +
    1.40 +        # Turn the shares into a column vector.
    1.41 +        svec = Matrix([shares]).transpose()
    1.42 +
    1.43 +        # Apply the hyper-invertible matrix to svec1 and svec2.
    1.44 +        rvec = (self._hyper * svec)
    1.45 +
    1.46 +        # Get back to normal lists of shares.
    1.47 +        svec = svec.transpose().rows[0]
    1.48 +        rvec = rvec.transpose().rows[0]
    1.49 +
    1.50 +        def verify(shares):
    1.51 +            """Verify shares.
    1.52 +
    1.53 +            It is checked that they correspond to polynomial of the
    1.54 +            expected degree.
    1.55 +
    1.56 +            If the verification succeeds, the T shares are returned,
    1.57 +            otherwise the errback is called.
    1.58 +            """
    1.59 +            # TODO: This is necessary since shamir.recombine expects
    1.60 +            # to receive a list of *pairs* of field elements.
    1.61 +            shares = map(lambda (i, s): (field(i+1), s), enumerate(shares))
    1.62 +
    1.63 +            # Verify the sharings. If any of the assertions fail and
    1.64 +            # raise an exception, the errbacks will be called on the
    1.65 +            # share returned by single_share_random.
    1.66 +            assert shamir.verify_sharing(shares, degree), "Could not verify"
    1.67 +
    1.68 +            # If we reach this point the n - T shares were verified
    1.69 +            # and we can safely return the first T shares.
    1.70 +            return rvec[:T]
    1.71 +
    1.72 +        def exchange(svec):
    1.73 +            """Exchange and (if possible) verify shares."""
    1.74 +            pc = tuple(self.program_counter)
    1.75 +
    1.76 +            # We send our shares to the verifying players.
    1.77 +            for offset, share in enumerate(svec):
    1.78 +                if T+1+offset != self.id:
    1.79 +                    self.protocols[T+1+offset].sendShare(pc, share)
    1.80 +
    1.81 +            if self.id > T:
    1.82 +                # The other players will send us their shares of si_1
    1.83 +                # and si_2 and we will verify it.
    1.84 +                si = []
    1.85 +                for peer_id in inputters:
    1.86 +                    if self.id == peer_id:
    1.87 +                        si.append(Share(self, field, svec[peer_id - T - 1]))
    1.88 +                    else:
    1.89 +                        si.append(self._expect_share(peer_id, field))
    1.90 +                result = gatherResults(si)
    1.91 +                self.schedule_callback(result, verify)
    1.92 +                return result
    1.93 +            else:
    1.94 +                # We cannot verify anything, so we just return the
    1.95 +                # first T shares.
    1.96 +                return rvec[:T]
    1.97 +
    1.98 +        result = gather_shares(svec[T:])
    1.99 +        self.schedule_callback(result, exchange)
   1.100 +        return result
   1.101 +
   1.102 +    @increment_pc
   1.103      def double_share_random(self, T, d1, d2, field):
   1.104          """Double-share a random secret using two polynomials.
   1.105  
   1.106 @@ -1142,25 +1229,28 @@
   1.107          t = self.threshold
   1.108          T = n - 2*t
   1.109  
   1.110 -        # Generate normal random sharings.
   1.111 -        a_t = [self.prss_share_random(field) for _ in range(T)]
   1.112 -        b_t = [self.prss_share_random(field) for _ in range(T)]
   1.113 -        c_2t = []
   1.114 -        for i in range(T):
   1.115 -            # Multiply a[i] and b[i] without resharing.
   1.116 -            ci = gather_shares([a_t[i], b_t[i]])
   1.117 -            ci.addCallback(lambda (ai, bi): ai * bi)
   1.118 -            c_2t.append(ci)
   1.119 +        def make_triple(shares):
   1.120 +            a_t, b_t, (r_t, r_2t) = shares
   1.121  
   1.122 -        def make_triple((r_t, r_2t)):
   1.123 +            c_2t = []
   1.124 +            for i in range(T):
   1.125 +                # Multiply a[i] and b[i] without resharing.
   1.126 +                ci = gather_shares([a_t[i], b_t[i]])
   1.127 +                ci.addCallback(lambda (ai, bi): ai * bi)
   1.128 +                c_2t.append(ci)
   1.129 +
   1.130              d_2t = [c_2t[i] - r_2t[i] for i in range(T)]
   1.131              d = [self.open(d_2t[i], threshold=2*t) for i in range(T)]
   1.132              c_t = [r_t[i] + d[i] for i in range(T)]
   1.133              return zip(a_t, b_t, c_t)
   1.134  
   1.135 -        double = self.double_share_random(T, t, 2*t, field)
   1.136 -        self.schedule_callback(double, make_triple)
   1.137 -        return double
   1.138 +        single_a = self.single_share_random(T, t, field)
   1.139 +        single_b = self.single_share_random(T, t, field)
   1.140 +        double_c = self.double_share_random(T, t, 2*t, field)
   1.141 +
   1.142 +        result = gatherResults([single_a, single_b, double_c])
   1.143 +        self.schedule_callback(result, make_triple)
   1.144 +        return result
   1.145  
   1.146      @increment_pc
   1.147      def _broadcast(self, sender, message=None):
     2.1 --- a/viff/test/test_active_runtime.py	Sun Apr 13 22:03:51 2008 +0200
     2.2 +++ b/viff/test/test_active_runtime.py	Sun Apr 13 22:16:28 2008 +0200
     2.3 @@ -62,6 +62,23 @@
     2.4          return gatherResults([x, y, z])
     2.5  
     2.6      @protocol
     2.7 +    def test_single_share_random(self, runtime):
     2.8 +        """Test sharing of random numbers."""
     2.9 +        T = runtime.num_players - 2 * runtime.threshold
    2.10 +
    2.11 +        def check(shares):
    2.12 +            # Check that we got the expected number of shares.
    2.13 +            self.assertEquals(len(shares), T)
    2.14 +
    2.15 +            results = []
    2.16 +            for share in shares:
    2.17 +                self.assert_type(share, Share)
    2.18 +
    2.19 +        shares = runtime.single_share_random(T, runtime.threshold, self.Zp)
    2.20 +        shares.addCallback(check)
    2.21 +        return shares
    2.22 +
    2.23 +    @protocol
    2.24      def test_double_share_random(self, runtime):
    2.25          """Test double-share random numbers."""
    2.26          T = runtime.num_players - 2 * runtime.threshold