viff

changeset 684:95a26f4d2a9e

Merged bugfix back in.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 25 Apr 2008 11:27:02 +0200
parents c1ad22124f89 74f54302aeb0
children 19b875e0d65d
files apps/benchmark.py viff/runtime.py
diffstat 11 files changed, 446 insertions(+), 97 deletions(-) [+]
line diff
     1.1 --- a/.hgignore	Fri Apr 25 11:26:05 2008 +0200
     1.2 +++ b/.hgignore	Fri Apr 25 11:27:02 2008 +0200
     1.3 @@ -13,7 +13,7 @@
     1.4  
     1.5  
     1.6  # Keys and certificates.
     1.7 -*-[1-9].{ini,cert,key}
     1.8 +*-[1-9]*.{ini,cert,key}
     1.9  ca.{cert,key}
    1.10  
    1.11  # Trial output directory.
     2.1 --- a/.hgsigs	Fri Apr 25 11:26:05 2008 +0200
     2.2 +++ b/.hgsigs	Fri Apr 25 11:27:02 2008 +0200
     2.3 @@ -1,2 +1,3 @@
     2.4  7e47fd0abed9673230a456e2f1b12794f6cf9d23 0 iD8DBQBHc/jr6nfwy35F3TgRAgxWAKDSuNK9UQtG01GqzmLZ5wwVKKlaygCfeA4xgSigRCOi3OOzXMdv4wmEcps=
     2.5  081094c8a3fb6ea46eb4e698e5038f1315b0ec69 0 iD8DBQBH2DMz6nfwy35F3TgRAnJ0AJ0fK1NE1J79kDOGW16Mae4d30AFUgCgzcuVGQn05U42FC+CZ+pmJUSkt9A=
     2.6 +46636debbbe310bd6428fc4e6f3e0d412d991a29 0 iD8DBQBIDtlM6nfwy35F3TgRAv2FAJ9jNfLhwU1yhQ3yVAwa3jEmIkb85ACgmldTcT4VE1x1JuTONGQx0V8Dk2o=
     3.1 --- a/.hgtags	Fri Apr 25 11:26:05 2008 +0200
     3.2 +++ b/.hgtags	Fri Apr 25 11:27:02 2008 +0200
     3.3 @@ -3,3 +3,4 @@
     3.4  63b4a2939abe4ec196a44919ba6306f247550ec0 0.2
     3.5  7e47fd0abed9673230a456e2f1b12794f6cf9d23 0.3
     3.6  081094c8a3fb6ea46eb4e698e5038f1315b0ec69 0.4
     3.7 +46636debbbe310bd6428fc4e6f3e0d412d991a29 0.5rc1
     4.1 --- a/NEWS	Fri Apr 25 11:26:05 2008 +0200
     4.2 +++ b/NEWS	Fri Apr 25 11:27:02 2008 +0200
     4.3 @@ -13,9 +13,18 @@
     4.4    http://tracker.viff.dk/
     4.5  
     4.6  
     4.7 -Version ?, not yet released
     4.8 ----------------------------
     4.9 +Version 0.5, not yet released
    4.10 +-----------------------------
    4.11  
    4.12 +The installation guide was updated for Windows Vista. Fixed minor
    4.13 +typos in documentation.
    4.14 +
    4.15 +
    4.16 +Version 0.5rc1, released on 2008-04-23
    4.17 +--------------------------------------
    4.18 +
    4.19 +Added preliminary support for preprocessing and an efficient
    4.20 +multiplication protocol which is secure against active adversaries.
    4.21  The Runtime class has been split into several parts and two new mixin
    4.22  classes provide different comparison protocols. Several coercion
    4.23  problems were fixed. The Runtime.callback method was renamed to
    4.24 @@ -31,6 +40,9 @@
    4.25    viff.comparison. If you used greater_than_equalII, then use the
    4.26    Toft07Runtime from the same module.
    4.27  
    4.28 +* Issue 3: Preprocessing. The runtime will now log the use of certain
    4.29 +  methods and this log can be used to preprocess the needed data.
    4.30 +
    4.31  * Issue 7: New system for unit tests. The tests now better simulate an
    4.32    asynchronous network by randomly delaying the communication between
    4.33    the players.
    4.34 @@ -41,6 +53,10 @@
    4.35  
    4.36  * The coercion done by the xor method was also fixed.
    4.37  
    4.38 +* Issue 30: Local multiplication if one operand is a constant. The
    4.39 +  runtime will now avoid an expensive resharing step when multiplying
    4.40 +  shares with constants.
    4.41 +
    4.42  * Issue 22: Allow sending data several times in one method. Previously
    4.43    one could only send once to a given players in a given method since
    4.44    all communication used the same program counter. The data is now
     5.1 --- a/README	Fri Apr 25 11:26:05 2008 +0200
     5.2 +++ b/README	Fri Apr 25 11:27:02 2008 +0200
     5.3 @@ -26,7 +26,7 @@
     5.4    sharing (PRSS).
     5.5  
     5.6  * arithmetic with shares from Zp or GF(2^8): addition, multiplication,
     5.7 -  exclusive-or.
     5.8 +  exclusive-or. Some support for actively secure multiplication.
     5.9  
    5.10  * two comparison protocols which compare secret shared Zp inputs, with
    5.11    secret GF(2^8) or Zp output.
     6.1 --- a/apps/benchmark.py	Fri Apr 25 11:26:05 2008 +0200
     6.2 +++ b/apps/benchmark.py	Fri Apr 25 11:27:02 2008 +0200
     6.3 @@ -57,6 +57,7 @@
     6.4  import time
     6.5  from optparse import OptionParser
     6.6  import operator
     6.7 +from pprint import pprint
     6.8  
     6.9  from twisted.internet import reactor
    6.10  
    6.11 @@ -70,18 +71,18 @@
    6.12  start = 0
    6.13  
    6.14  
    6.15 -def record_start():
    6.16 +def record_start(what):
    6.17      global start
    6.18      start = time.time()
    6.19      print "*" * 64
    6.20 -    print "Started"
    6.21 +    print "Started", what
    6.22  
    6.23  
    6.24 -def record_stop(_):
    6.25 +def record_stop(_, what):
    6.26      stop = time.time()
    6.27      print
    6.28      print "Total time used: %.3f sec" % (stop-start)
    6.29 -    print "Time per operation: %.3f ms" % (1000*float(stop-start) / count)
    6.30 +    print "Time per %s operation: %.3f ms" % (what, 1000*float(stop-start) / count)
    6.31      print "*" * 6
    6.32  
    6.33  
    6.34 @@ -122,9 +123,26 @@
    6.35  class Benchmark:
    6.36  
    6.37      def __init__(self, rt, operation):
    6.38 -        print "Runtime ready, starting protocol"
    6.39          self.rt = rt
    6.40          self.operation = operation
    6.41 +
    6.42 +        if isinstance(self.rt, ActiveRuntime) and self.operation == operator.mul:
    6.43 +            # TODO: Make this optional and extend it to other operations.
    6.44 +            print "Starting preprocessing"
    6.45 +            program_desc = {
    6.46 +                ("generate_triples", (Zp,)):
    6.47 +                    [(i, 1, 0) for i in range(3 + 2*count, 3 + 3*count)]
    6.48 +                }
    6.49 +            record_start("preprocessing")
    6.50 +            preproc = rt.preprocess(program_desc)
    6.51 +            preproc.addCallback(record_stop, "preprocessing")
    6.52 +            preproc.addCallback(self.begin)
    6.53 +        else:
    6.54 +            print "Need no preprocessing"
    6.55 +            self.begin(None)
    6.56 +
    6.57 +    def begin(self, _):
    6.58 +        print "Runtime ready, starting protocol"
    6.59          self.a_shares = [self.rt.prss_share_random(Zp) for _ in range(count)]
    6.60          self.b_shares = [self.rt.prss_share_random(Zp) for _ in range(count)]
    6.61          shares_ready = gather_shares(self.a_shares + self.b_shares)
    6.62 @@ -151,8 +169,14 @@
    6.63  
    6.64      def finished(self, _):
    6.65          print "Finished, synchronizing shutdown."
    6.66 +        sys.stdout.flush()
    6.67 +
    6.68 +        if self.rt._needed_data:
    6.69 +            print "Missing pre-processed data:"
    6.70 +            pprint(self.rt._needed_data)
    6.71 +
    6.72          sync = self.rt.synchronize()
    6.73 -        sync.addCallback(self.shutdown)
    6.74 +        sync.addCallback(lambda _: reactor.callLater(5, self.shutdown, None))
    6.75  
    6.76      def shutdown(self, _):
    6.77          print "Shutdown."
    6.78 @@ -164,24 +188,22 @@
    6.79  class ParallelBenchmark(Benchmark):
    6.80  
    6.81      def run_test(self, _):
    6.82 -        print "Starting parallel test."
    6.83          c_shares = []
    6.84 -        record_start()
    6.85 +        record_start("parallel test")
    6.86          while self.a_shares and self.b_shares:
    6.87              a = self.a_shares.pop()
    6.88              b = self.b_shares.pop()
    6.89              c_shares.append(self.operation(a, b))
    6.90  
    6.91          done = gather_shares(c_shares)
    6.92 -        done.addCallback(record_stop)
    6.93 +        done.addCallback(record_stop, "parallel test")
    6.94          done.addCallback(self.finished)
    6.95  
    6.96  # A benchmark where the operations are executed one after each other.
    6.97  class SequentialBenchmark(Benchmark):
    6.98  
    6.99      def run_test(self, _):
   6.100 -        print "Starting sequential test."
   6.101 -        record_start()
   6.102 +        record_start("sequential test")
   6.103          self.single_operation(None)
   6.104  
   6.105      def single_operation(self, _):
   6.106 @@ -191,7 +213,7 @@
   6.107              c = self.operation(a, b)
   6.108              c.addCallback(self.single_operation)
   6.109          else:
   6.110 -            record_stop(None)
   6.111 +            record_stop(None, "sequential test")
   6.112              self.finished(None)
   6.113  
   6.114  if options.operation == "mul":
     7.1 --- a/setup.py	Fri Apr 25 11:26:05 2008 +0200
     7.2 +++ b/setup.py	Fri Apr 25 11:27:02 2008 +0200
     7.3 @@ -21,6 +21,10 @@
     7.4  # You should have received a copy of the GNU Lesser General Public
     7.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     7.6  
     7.7 +import sys
     7.8 +if not hasattr(sys, 'version_info') or sys.version_info < (2, 4, 0, 'final'):
     7.9 +    raise SystemExit, "VIFF requires Python version 2.4 or later."
    7.10 +
    7.11  from distutils.command.sdist import sdist
    7.12  from distutils.core import setup
    7.13  
    7.14 @@ -104,6 +108,7 @@
    7.15  # * viff-devel@viff.dk
    7.16  # * http://freshmeat.net/projects/viff/
    7.17  # * http://pypi.python.org/pypi/viff/
    7.18 +# * http://directory.fsf.org/project/viff/
    7.19  # * http://www.icewalkers.com/Linux/Software/532160/VIFF.html
    7.20  # * http://www.hotscripts.com/Detailed/74748.html
    7.21  # * http://sourcewell.berlios.de/appbyid.php?id=3572
     8.1 --- a/viff/__init__.py	Fri Apr 25 11:26:05 2008 +0200
     8.2 +++ b/viff/__init__.py	Fri Apr 25 11:27:02 2008 +0200
     8.3 @@ -124,5 +124,5 @@
     8.4  @see: U{http://viff.dk/}
     8.5  """
     8.6  
     8.7 -__version__ = '0.4'
     8.8 +__version__ = '0.5rc1'
     8.9  __license__ = 'GNU GPL'
     9.1 --- a/viff/runtime.py	Fri Apr 25 11:26:05 2008 +0200
     9.2 +++ b/viff/runtime.py	Fri Apr 25 11:27:02 2008 +0200
     9.3 @@ -44,7 +44,7 @@
     9.4  from viff.util import wrapper, rand
     9.5  
     9.6  from twisted.internet import reactor
     9.7 -from twisted.internet.defer import Deferred, DeferredList
     9.8 +from twisted.internet.defer import Deferred, DeferredList, gatherResults, succeed
     9.9  from twisted.internet.protocol import ClientFactory, ServerFactory
    9.10  from twisted.protocols.basic import Int16StringReceiver
    9.11  
    9.12 @@ -173,7 +173,7 @@
    9.13  
    9.14      If a threshold less than the full number of shares is used, some
    9.15      of the pairs may be missing and C{None} is used instead. In the
    9.16 -    example above the C{c} Share arrived later than C{a} and C{b}, and
    9.17 +    example above the C{b} Share arrived later than C{a} and C{c}, and
    9.18      so the list contains a C{None} on its place.
    9.19      """
    9.20  
    9.21 @@ -370,6 +370,38 @@
    9.22      return inc_pc_wrapper
    9.23  
    9.24  
    9.25 +def preprocess(generator):
    9.26 +    """Track calls to this method.
    9.27 +
    9.28 +    The decorated method will be replaced with a proxy method which
    9.29 +    first tries to get the data needed from C{self._pool}, and if that
    9.30 +    fails it falls back to the original method.
    9.31 +
    9.32 +    The C{generator} method is only used to record where the data
    9.33 +    should be generated from, the method is not actually called.
    9.34 +
    9.35 +    @param generator: Use this method as the generator for
    9.36 +    pre-processed data.
    9.37 +    @type generator: C{str}
    9.38 +    """
    9.39 +
    9.40 +    def preprocess_decorator(method):
    9.41 +
    9.42 +        @wrapper(method)
    9.43 +        def preprocess_wrapper(self, *args, **kwargs):
    9.44 +            pc = tuple(self.program_counter)
    9.45 +            try:
    9.46 +                return self._pool[pc]
    9.47 +            except KeyError:
    9.48 +                key = (generator, args)
    9.49 +                pcs = self._needed_data.setdefault(key, [])
    9.50 +                pcs.append(pc)
    9.51 +                return method(self, *args, **kwargs)
    9.52 +
    9.53 +        return preprocess_wrapper
    9.54 +    return preprocess_decorator
    9.55 +
    9.56 +
    9.57  class BasicRuntime:
    9.58      """Basic VIFF runtime with no crypto.
    9.59  
    9.60 @@ -396,9 +428,15 @@
    9.61          group.add_option("--deferred-debug", action="store_true",
    9.62                           help="Enable extra debug output for deferreds.")
    9.63  
    9.64 +        try:
    9.65 +            import gnutls
    9.66 +            have_gnutls = True
    9.67 +        except ImportError:
    9.68 +            have_gnutls = False
    9.69 +
    9.70          parser.set_defaults(bit_length=32,
    9.71                              security_parameter=30,
    9.72 -                            tls=True,
    9.73 +                            tls=have_gnutls,
    9.74                              deferred_debug=False)
    9.75  
    9.76      def __init__(self, player, threshold, options=None):
    9.77 @@ -427,6 +465,11 @@
    9.78              from twisted.internet import defer
    9.79              defer.setDebugging(True)
    9.80  
    9.81 +        #: Pool of preprocessed data.
    9.82 +        self._pool = {}
    9.83 +        #: Description of needed preprocessed data.
    9.84 +        self._needed_data = {}
    9.85 +
    9.86          #: Current program counter.
    9.87          #:
    9.88          #: Whenever a share is sent over the network, it must be
    9.89 @@ -608,6 +651,72 @@
    9.90          self._expect_data(peer_id, "share", share)
    9.91          return share
    9.92  
    9.93 +    @increment_pc
    9.94 +    def preprocess(self, program):
    9.95 +        """Generate preprocess material.
    9.96 +
    9.97 +        The C{program} specifies which methods to call and with which
    9.98 +        arguments. The generator methods called must adhere to the
    9.99 +        following interface:
   9.100 +
   9.101 +          - They must return a C{(int, Deferred)} tuple where the
   9.102 +            C{int} tells us how many items of pre-processed data the
   9.103 +            Deferred will yield.
   9.104 +
   9.105 +          - The Deferred must yield a C{list} of the promissed length.
   9.106 +
   9.107 +          - The C{list} contains the actual data. This data can be
   9.108 +            either a Deferred or a C{tuple} of Deferreds.
   9.109 +
   9.110 +        The L{ActiveRuntime.generate_triples} method is an example of
   9.111 +        a method fulfilling this interface.
   9.112 +
   9.113 +        @param program: A description of the needed data.
   9.114 +        @type program: C{dict} mapping C{(str, args)} tuples to
   9.115 +        program counters
   9.116 +        """
   9.117 +
   9.118 +        def update(results, program_counters):
   9.119 +            # We concatenate the sub-lists in results.
   9.120 +            results = sum(results, [])
   9.121 +
   9.122 +            wait_list = []
   9.123 +            for result in results:
   9.124 +                # We allow pre-processing methods to return tuples of
   9.125 +                # shares or individual shares as their result. Here we
   9.126 +                # deconstruct result (if possible) and wait on its
   9.127 +                # individual parts.
   9.128 +                if isinstance(result, tuple):
   9.129 +                    wait_list.extend(result)
   9.130 +                else:
   9.131 +                    wait_list.append(result)
   9.132 +
   9.133 +            # The pool must map program counters to Deferreds to
   9.134 +            # present a uniform interface for the functions we
   9.135 +            # pre-process.
   9.136 +            results = map(succeed, results)
   9.137 +
   9.138 +            # Update the pool with pairs of program counter and data.
   9.139 +            self._pool.update(zip(program_counters, results))
   9.140 +            # Return a Deferred that waits on the individual results.
   9.141 +            # This is important to make it possible for the players to
   9.142 +            # avoid starting before the pre-processing is complete.
   9.143 +            return gatherResults(wait_list)
   9.144 +
   9.145 +        wait_list = []
   9.146 +        for ((generator, args), program_counters) in program.iteritems():
   9.147 +            print "Preprocessing %s (%d items)" % (generator, len(program_counters))
   9.148 +            func = getattr(self, generator)
   9.149 +            results = []
   9.150 +            items = 0
   9.151 +            while items < len(program_counters):
   9.152 +                item_count, result = func(*args)
   9.153 +                items += item_count
   9.154 +                results.append(result)
   9.155 +            ready = gatherResults(results)
   9.156 +            ready.addCallback(update, program_counters)
   9.157 +            wait_list.append(ready)
   9.158 +        return DeferredList(wait_list)
   9.159  
   9.160  class Runtime(BasicRuntime):
   9.161      """The VIFF runtime.
   9.162 @@ -989,26 +1098,123 @@
   9.163  
   9.164          # At this point both share_x and share_y must be Share
   9.165          # objects. We multiply them via a multiplication triple.
   9.166 -        a, b, c = self.get_triple(share_x.field)
   9.167 -        d = self.open(share_x - a)
   9.168 -        e = self.open(share_y - b)
   9.169 +        def finish_mul(triple):
   9.170 +            a, b, c = triple
   9.171 +            d = self.open(share_x - a)
   9.172 +            e = self.open(share_y - b)
   9.173  
   9.174 -        # TODO: We ought to be able to simple do
   9.175 -        #
   9.176 -        #   return d*e + d*y + e*x + c
   9.177 -        #
   9.178 -        # but that leads to infinite recursion since d and e are
   9.179 -        # Shares, not FieldElements. So we have to do a bit more
   9.180 -        # work... The following callback also leads to recursion, but
   9.181 -        # only one level since d and e are FieldElements now, which
   9.182 -        # means that we return in the above if statements.
   9.183 -        result = gather_shares([d, e])
   9.184 -        result.addCallback(lambda (d,e): d*e + d*b + e*a + c)
   9.185 +            # TODO: We ought to be able to simply do
   9.186 +            #
   9.187 +            #   return d*e + d*y + e*x + c
   9.188 +            #
   9.189 +            # but that leads to infinite recursion since d and e are
   9.190 +            # Shares, not FieldElements. So we have to do a bit more
   9.191 +            # work... The following callback also leads to recursion, but
   9.192 +            # only one level since d and e are FieldElements now, which
   9.193 +            # means that we return in the above if statements.
   9.194 +            result = gather_shares([d, e])
   9.195 +            result.addCallback(lambda (d,e): d*e + d*b + e*a + c)
   9.196 +            return result
   9.197 +
   9.198 +        # This will be the result, a Share object.
   9.199 +        result = Share(self, share_x.field)
   9.200 +        # This is the Deferred we will do processing on.
   9.201 +        triple = self.get_triple(share_x.field)
   9.202 +        self.schedule_callback(triple, finish_mul)
   9.203 +        # We add the result to the chains in triple.
   9.204 +        triple.chainDeferred(result)
   9.205 +        return result
   9.206 +
   9.207 +    @increment_pc
   9.208 +    def single_share_random(self, T, degree, field):
   9.209 +        """Share a random secret.
   9.210 +
   9.211 +        The guarantee is that a number of shares are made and out of
   9.212 +        those, the T that are returned by this method will be correct
   9.213 +        sharings of a random number using C{degree} as the polynomial
   9.214 +        degree.
   9.215 +
   9.216 +        @param T: The number of shares output.
   9.217 +        @param degree: The degree of the polynomial.
   9.218 +        @param field: The field over which to share the secret.
   9.219 +        """
   9.220 +        # TODO: Move common code between single_share and
   9.221 +        # double_share_random out to their own methods.
   9.222 +        inputters = range(1, self.num_players + 1)
   9.223 +        if self._hyper is None:
   9.224 +            self._hyper = hyper(self.num_players, field)
   9.225 +
   9.226 +        # Generate a random element.
   9.227 +        si = rand.randint(0, field.modulus - 1)
   9.228 +
   9.229 +        # Every player shares the random value with two thresholds.
   9.230 +        shares = self.shamir_share(inputters, field, si, degree)
   9.231 +
   9.232 +        # Turn the shares into a column vector.
   9.233 +        svec = Matrix([shares]).transpose()
   9.234 +
   9.235 +        # Apply the hyper-invertible matrix to svec1 and svec2.
   9.236 +        rvec = (self._hyper * svec)
   9.237 +
   9.238 +        # Get back to normal lists of shares.
   9.239 +        svec = svec.transpose().rows[0]
   9.240 +        rvec = rvec.transpose().rows[0]
   9.241 +
   9.242 +        def verify(shares):
   9.243 +            """Verify shares.
   9.244 +
   9.245 +            It is checked that they correspond to polynomial of the
   9.246 +            expected degree.
   9.247 +
   9.248 +            If the verification succeeds, the T shares are returned,
   9.249 +            otherwise the errback is called.
   9.250 +            """
   9.251 +            # TODO: This is necessary since shamir.recombine expects
   9.252 +            # to receive a list of *pairs* of field elements.
   9.253 +            shares = map(lambda (i, s): (field(i+1), s), enumerate(shares))
   9.254 +
   9.255 +            # Verify the sharings. If any of the assertions fail and
   9.256 +            # raise an exception, the errbacks will be called on the
   9.257 +            # share returned by single_share_random.
   9.258 +            assert shamir.verify_sharing(shares, degree), "Could not verify"
   9.259 +
   9.260 +            # If we reach this point the n - T shares were verified
   9.261 +            # and we can safely return the first T shares.
   9.262 +            return rvec[:T]
   9.263 +
   9.264 +        def exchange(svec):
   9.265 +            """Exchange and (if possible) verify shares."""
   9.266 +            pc = tuple(self.program_counter)
   9.267 +
   9.268 +            # We send our shares to the verifying players.
   9.269 +            for offset, share in enumerate(svec):
   9.270 +                if T+1+offset != self.id:
   9.271 +                    self.protocols[T+1+offset].sendShare(pc, share)
   9.272 +
   9.273 +            if self.id > T:
   9.274 +                # The other players will send us their shares of si_1
   9.275 +                # and si_2 and we will verify it.
   9.276 +                si = []
   9.277 +                for peer_id in inputters:
   9.278 +                    if self.id == peer_id:
   9.279 +                        si.append(Share(self, field, svec[peer_id - T - 1]))
   9.280 +                    else:
   9.281 +                        si.append(self._expect_share(peer_id, field))
   9.282 +                result = gatherResults(si)
   9.283 +                self.schedule_callback(result, verify)
   9.284 +                return result
   9.285 +            else:
   9.286 +                # We cannot verify anything, so we just return the
   9.287 +                # first T shares.
   9.288 +                return rvec[:T]
   9.289 +
   9.290 +        result = gather_shares(svec[T:])
   9.291 +        self.schedule_callback(result, exchange)
   9.292          return result
   9.293  
   9.294      @increment_pc
   9.295      def double_share_random(self, T, d1, d2, field):
   9.296 -        """Double-shares a randoms secret by using two polynomials.
   9.297 +        """Double-share a random secret using two polynomials.
   9.298  
   9.299          The guarantee is that a number of shares are made and out of
   9.300          those, the T that are returned by this method will be correct
   9.301 @@ -1036,53 +1242,126 @@
   9.302          svec2 = Matrix([d2_shares]).transpose()
   9.303  
   9.304          # Apply the hyper-invertible matrix to svec1 and svec2.
   9.305 -        rvec1 = (self._hyper * svec1).transpose()
   9.306 -        rvec2 = (self._hyper * svec2).transpose()
   9.307 +        rvec1 = (self._hyper * svec1)
   9.308 +        rvec2 = (self._hyper * svec2)
   9.309  
   9.310 -        # TODO: verify sharings
   9.311 +        # Get back to normal lists of shares.
   9.312 +        svec1 = svec1.transpose().rows[0]
   9.313 +        svec2 = svec2.transpose().rows[0]
   9.314 +        rvec1 = rvec1.transpose().rows[0]
   9.315 +        rvec2 = rvec2.transpose().rows[0]
   9.316  
   9.317 -        # Return the first T shares (the ones that was not opened in
   9.318 -        # the verifying step.
   9.319 -        return rvec1.rows[0][:T], rvec2.rows[0][:T]
   9.320 +        def verify(shares):
   9.321 +            """Verify shares.
   9.322 +
   9.323 +            It is checked that they correspond to polynomial of the
   9.324 +            expected degrees and that they can be recombined to the
   9.325 +            same value.
   9.326 +
   9.327 +            If the verification succeeds, the T double shares are
   9.328 +            returned, otherwise the errback is called.
   9.329 +            """
   9.330 +            si_1, si_2 = shares
   9.331 +
   9.332 +            # TODO: This is necessary since shamir.recombine expects
   9.333 +            # to receive a list of *pairs* of field elements.
   9.334 +            si_1 = map(lambda (i, s): (field(i+1), s), enumerate(si_1))
   9.335 +            si_2 = map(lambda (i, s): (field(i+1), s), enumerate(si_2))
   9.336 +
   9.337 +            # Verify the sharings. If any of the assertions fail and
   9.338 +            # raise an exception, the errbacks will be called on the
   9.339 +            # double share returned by double_share_random.
   9.340 +            assert shamir.verify_sharing(si_1, d1), "Could not verify si_1"
   9.341 +            assert shamir.verify_sharing(si_2, d2), "Could not verify si_2"
   9.342 +            assert shamir.recombine(si_1[:d1+1]) == shamir.recombine(si_2[:d2+1]), \
   9.343 +                "Shares do not recombine to the same value"
   9.344 +
   9.345 +            # If we reach this point the n - T shares were verified
   9.346 +            # and we can safely return the first T shares.
   9.347 +            return (rvec1[:T], rvec2[:T])
   9.348 +
   9.349 +        def exchange(shares):
   9.350 +            """Exchange and (if possible) verify shares."""
   9.351 +            svec1, svec2 = shares
   9.352 +            pc = tuple(self.program_counter)
   9.353 +
   9.354 +            # We send our shares to the verifying players.
   9.355 +            for offset, (s1, s2) in enumerate(zip(svec1, svec2)):
   9.356 +                if T+1+offset != self.id:
   9.357 +                    self.protocols[T+1+offset].sendShare(pc, s1)
   9.358 +                    self.protocols[T+1+offset].sendShare(pc, s2)
   9.359 +
   9.360 +            if self.id > T:
   9.361 +                # The other players will send us their shares of si_1
   9.362 +                # and si_2 and we will verify it.
   9.363 +                si_1 = []
   9.364 +                si_2 = []
   9.365 +                for peer_id in inputters:
   9.366 +                    if self.id == peer_id:
   9.367 +                        si_1.append(Share(self, field, svec1[peer_id - T - 1]))
   9.368 +                        si_2.append(Share(self, field, svec2[peer_id - T - 1]))
   9.369 +                    else:
   9.370 +                        si_1.append(self._expect_share(peer_id, field))
   9.371 +                        si_2.append(self._expect_share(peer_id, field))
   9.372 +                result = gatherResults([gatherResults(si_1), gatherResults(si_2)])
   9.373 +                self.schedule_callback(result, verify)
   9.374 +                return result
   9.375 +            else:
   9.376 +                # We cannot verify anything, so we just return the
   9.377 +                # first T shares.
   9.378 +                return (rvec1[:T], rvec2[:T])
   9.379 +
   9.380 +        result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
   9.381 +        self.schedule_callback(result, exchange)
   9.382 +        return result
   9.383  
   9.384      @increment_pc
   9.385 +    @preprocess("generate_triples")
   9.386      def get_triple(self, field):
   9.387 -        # TODO: This is of course insecure... We should move
   9.388 -        # generate_triples to a preprocessing step and draw the
   9.389 -        # triples from a pool instead. Also, using only the first
   9.390 -        # triple is quite wasteful...
   9.391 -        return self.generate_triples(field)[0]
   9.392 +        # This is a waste, but this function is only called if there
   9.393 +        # are no pre-processed triples left.
   9.394 +        count, result = self.generate_triples(field)
   9.395 +        result.addCallback(lambda triples: triples[0])
   9.396 +        return result
   9.397  
   9.398      @increment_pc
   9.399      def generate_triples(self, field):
   9.400          """Generate multiplication triples.
   9.401  
   9.402          These are random numbers M{a}, M{b}, and M{c} such that M{c =
   9.403 -        ab}.
   9.404 +        ab}. This function can be used in pre-processing.
   9.405  
   9.406 -        @return: C{list} of 3-tuples.
   9.407 -        @returntype: C{list} of C{(Share, Share, Share)}
   9.408 +        @return: Number of triples returned and a Deferred which will
   9.409 +        yield a C{list} of 3-tuples.
   9.410 +        @returntype: (C{int}, C{list} of Deferred C{(Share, Share,
   9.411 +        Share)})
   9.412          """
   9.413          n = self.num_players
   9.414          t = self.threshold
   9.415          T = n - 2*t
   9.416  
   9.417 -        # Generate normal random sharings.
   9.418 -        a_t = [self.prss_share_random(field) for _ in range(T)]
   9.419 -        b_t = [self.prss_share_random(field) for _ in range(T)]
   9.420 -        c_2t = []
   9.421 -        for i in range(T):
   9.422 -            # Multiply a[i] and b[i] without resharing.
   9.423 -            ci = gather_shares([a_t[i], b_t[i]])
   9.424 -            ci.addCallback(lambda (ai, bi): ai * bi)
   9.425 -            c_2t.append(ci)
   9.426 +        def make_triple(shares):
   9.427 +            a_t, b_t, (r_t, r_2t) = shares
   9.428  
   9.429 -        r_t, r_2t = self.double_share_random(T, t, 2*t, field)
   9.430 -        d_2t = [c_2t[i] - r_2t[i] for i in range(T)]
   9.431 -        d = [self.open(d_2t[i], threshold=2*t) for i in range(T)]
   9.432 -        c_t = [r_t[i] + d[i] for i in range(T)]
   9.433 +            c_2t = []
   9.434 +            for i in range(T):
   9.435 +                # Multiply a[i] and b[i] without resharing.
   9.436 +                ci = gather_shares([a_t[i], b_t[i]])
   9.437 +                ci.addCallback(lambda (ai, bi): ai * bi)
   9.438 +                c_2t.append(ci)
   9.439  
   9.440 -        return zip(a_t, b_t, c_t)
   9.441 +            d_2t = [c_2t[i] - r_2t[i] for i in range(T)]
   9.442 +            d = [self.open(d_2t[i], threshold=2*t) for i in range(T)]
   9.443 +            c_t = [r_t[i] + d[i] for i in range(T)]
   9.444 +            return zip(a_t, b_t, c_t)
   9.445 +
   9.446 +        single_a = self.single_share_random(T, t, field)
   9.447 +        single_b = self.single_share_random(T, t, field)
   9.448 +        double_c = self.double_share_random(T, t, 2*t, field)
   9.449 +
   9.450 +        result = gatherResults([single_a, single_b, double_c])
   9.451 +        self.schedule_callback(result, make_triple)
   9.452 +        return T, result
   9.453  
   9.454      @increment_pc
   9.455      def _broadcast(self, sender, message=None):
    10.1 --- a/viff/test/test_active_runtime.py	Fri Apr 25 11:26:05 2008 +0200
    10.2 +++ b/viff/test/test_active_runtime.py	Fri Apr 25 11:27:02 2008 +0200
    10.3 @@ -62,54 +62,78 @@
    10.4          return gatherResults([x, y, z])
    10.5  
    10.6      @protocol
    10.7 +    def test_single_share_random(self, runtime):
    10.8 +        """Test sharing of random numbers."""
    10.9 +        T = runtime.num_players - 2 * runtime.threshold
   10.10 +
   10.11 +        def check(shares):
   10.12 +            # Check that we got the expected number of shares.
   10.13 +            self.assertEquals(len(shares), T)
   10.14 +
   10.15 +            results = []
   10.16 +            for share in shares:
   10.17 +                self.assert_type(share, Share)
   10.18 +
   10.19 +        shares = runtime.single_share_random(T, runtime.threshold, self.Zp)
   10.20 +        shares.addCallback(check)
   10.21 +        return shares
   10.22 +
   10.23 +    @protocol
   10.24      def test_double_share_random(self, runtime):
   10.25          """Test double-share random numbers."""
   10.26          T = runtime.num_players - 2 * runtime.threshold
   10.27 -        from viff.field import GF
   10.28 -        self.Zp = GF(11)
   10.29 -
   10.30 -        r_t, r_2t = runtime.double_share_random(T,
   10.31 -                                                runtime.threshold,
   10.32 -                                                2*runtime.threshold,
   10.33 -                                                self.Zp)
   10.34 -
   10.35 -        # Check that we got the expected number of shares.
   10.36 -        self.assertEquals(len(r_t), T)
   10.37 -        self.assertEquals(len(r_2t), T)
   10.38  
   10.39          def verify(shares):
   10.40              """Verify that the list contains two equal shares."""
   10.41              self.assertEquals(shares[0], shares[1])
   10.42  
   10.43 -        results = []
   10.44 -        for a, b in zip(r_t, r_2t):
   10.45 -            self.assert_type(a, Share)
   10.46 -            self.assert_type(b, Share)
   10.47 -            open_a = runtime.open(a)
   10.48 -            open_b = runtime.open(b, threshold=2*runtime.threshold)
   10.49 -            result = gatherResults([open_a, open_b])
   10.50 -            result.addCallback(verify)
   10.51 -            results.append(result)
   10.52 -        return gatherResults(results)
   10.53 +        def check(double):
   10.54 +            r_t, r_2t = double
   10.55 +
   10.56 +            # Check that we got the expected number of shares.
   10.57 +            self.assertEquals(len(r_t), T)
   10.58 +            self.assertEquals(len(r_2t), T)
   10.59 +
   10.60 +            results = []
   10.61 +            for a, b in zip(r_t, r_2t):
   10.62 +                self.assert_type(a, Share)
   10.63 +                self.assert_type(b, Share)
   10.64 +                open_a = runtime.open(a)
   10.65 +                open_b = runtime.open(b, threshold=2*runtime.threshold)
   10.66 +                result = gatherResults([open_a, open_b])
   10.67 +                result.addCallback(verify)
   10.68 +                results.append(result)
   10.69 +            return gatherResults(results)
   10.70 +
   10.71 +        double = runtime.double_share_random(T, runtime.threshold,
   10.72 +                                             2*runtime.threshold, self.Zp)
   10.73 +        double.addCallback(check)
   10.74 +        return double
   10.75  
   10.76      @protocol
   10.77      def test_generate_triples(self, runtime):
   10.78          """Test generation of multiplication triples."""
   10.79 -        triples = runtime.generate_triples(self.Zp)
   10.80  
   10.81          def verify(triple):
   10.82              """Verify a multiplication triple."""
   10.83              self.assertEquals(triple[0] * triple[1], triple[2])
   10.84  
   10.85 -        results = []
   10.86 -        for a, b, c in triples:
   10.87 -            self.assert_type(a, Share)
   10.88 -            self.assert_type(b, Share)
   10.89 -            self.assert_type(c, Share)
   10.90 -            open_a = runtime.open(a)
   10.91 -            open_b = runtime.open(b)
   10.92 -            open_c = runtime.open(c)
   10.93 -            result = gatherResults([open_a, open_b, open_c])
   10.94 -            result.addCallback(verify)
   10.95 -            results.append(result)
   10.96 -        return gatherResults(results)
   10.97 +        def check(triples):
   10.98 +            results = []
   10.99 +            for a, b, c in triples:
  10.100 +                self.assert_type(a, Share)
  10.101 +                self.assert_type(b, Share)
  10.102 +                self.assert_type(c, Share)
  10.103 +                open_a = runtime.open(a)
  10.104 +                open_b = runtime.open(b)
  10.105 +                open_c = runtime.open(c)
  10.106 +                result = gatherResults([open_a, open_b, open_c])
  10.107 +                result.addCallback(verify)
  10.108 +                results.append(result)
  10.109 +            return gatherResults(results)
  10.110 +
  10.111 +        count, triples = runtime.generate_triples(self.Zp)
  10.112 +        self.assertEquals(count, runtime.num_players - 2*runtime.threshold)
  10.113 +
  10.114 +        triples.addCallback(check)
  10.115 +        return triples
    11.1 --- a/viff/util.py	Fri Apr 25 11:26:05 2008 +0200
    11.2 +++ b/viff/util.py	Fri Apr 25 11:27:02 2008 +0200
    11.3 @@ -201,7 +201,7 @@
    11.4      If a prime is given as the lower bound, then this prime is
    11.5      returned:
    11.6  
    11.7 -    >> find_prime(37)
    11.8 +    >>> find_prime(37)
    11.9      37L
   11.10  
   11.11      The bound can be a Python expression as a string. This makes it