viff

changeset 643:84d720a9ed4b

Added double_share_random method to Runtime. This method uses a hyper-invertible matrix to efficiently generate shares of a number of random values unknown to all parties. The values are shared using two different degrees.
author Martin Geisler <mg@daimi.au.dk>
date Sat, 05 Apr 2008 00:00:24 +0200
parents 885828ebed92
children cc58a62d507c
files viff/runtime.py
diffstat 1 files changed, 52 insertions(+), 1 deletions(-) [+]
line diff
     1.1 --- a/viff/runtime.py	Sat Apr 05 00:00:24 2008 +0200
     1.2 +++ b/viff/runtime.py	Sat Apr 05 00:00:24 2008 +0200
     1.3 @@ -40,7 +40,8 @@
     1.4  from viff import shamir
     1.5  from viff.prss import prss
     1.6  from viff.field import GF256, FieldElement
     1.7 -from viff.util import wrapper
     1.8 +from viff.matrix import Matrix, hyper
     1.9 +from viff.util import wrapper, rand
    1.10  
    1.11  from twisted.internet import reactor
    1.12  from twisted.internet.defer import Deferred, DeferredList
    1.13 @@ -952,6 +953,56 @@
    1.14      normal L{Runtime} class and is thus I{not} yet secure.
    1.15      """
    1.16  
    1.17 +    def __init__(self, player, threshold, options=None):
    1.18 +        """Initialize runtime."""
    1.19 +
    1.20 +        #: A hyper-invertible matrix.
    1.21 +        #:
    1.22 +        #: It should be suitable for L{self.num_players} players, but
    1.23 +        #: since we don't know the total number of players yet, we set
    1.24 +        #: it to C{None} here and update it as necessary.
    1.25 +        self._hyper = None
    1.26 +        Runtime.__init__(self, player, threshold, options)
    1.27 +
    1.28 +    @increment_pc
    1.29 +    def double_share_random(self, T, d1, d2, field):
    1.30 +        """Double-shares a randoms secret by using two polynomials.
    1.31 +
    1.32 +        The guarantee is that a number of shares are made and out of
    1.33 +        those, the T that are returned by this method will be correct
    1.34 +        double-sharings of a random number using d1 and d2 as the
    1.35 +        polynomial degrees.
    1.36 +
    1.37 +        @param T: The number of double-shares output.
    1.38 +        @param d1: The degree of the first polynomial.
    1.39 +        @param d2: The degree of the second polynomial.
    1.40 +        @param field: The field over which to share the secret.
    1.41 +        """
    1.42 +        inputters = range(1, self.num_players + 1)
    1.43 +        if self._hyper is None:
    1.44 +            self._hyper = hyper(self.num_players, field)
    1.45 +
    1.46 +        # Generate a random element.
    1.47 +        si = rand.randint(0, field.modulus - 1)
    1.48 +
    1.49 +        # Every player shares the random value with two thresholds.
    1.50 +        d1_shares = self.shamir_share(inputters, field, si, d1)
    1.51 +        d2_shares = self.shamir_share(inputters, field, si, d2)
    1.52 +
    1.53 +        # Turn the shares into a column vector.
    1.54 +        svec1 = Matrix([d1_shares]).transpose()
    1.55 +        svec2 = Matrix([d2_shares]).transpose()
    1.56 +
    1.57 +        # Apply the hyper-invertible matrix to svec1 and svec2.
    1.58 +        rvec1 = (self._hyper * svec1).transpose()
    1.59 +        rvec2 = (self._hyper * svec2).transpose()
    1.60 +
    1.61 +        # TODO: verify sharings
    1.62 +
    1.63 +        # Return the first T shares (the ones that was not opened in
    1.64 +        # the verifying step.
    1.65 +        return rvec1.rows[0][:T], rvec2.rows[0][:T]
    1.66 +
    1.67      @increment_pc
    1.68      def _broadcast(self, sender, message=None):
    1.69          """Perform a Bracha broadcast.