viff

changeset 1154:950815ab873f

Merged.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 27 Mar 2009 15:44:01 +0100
parents 99a8a7c9cce5 d9b3bceab2f5
children 4d7291de8f8a
files apps/aes.py apps/benchmark.py viff/aes.py viff/config.py viff/passive.py viff/runtime.py
diffstat 19 files changed, 458 insertions(+), 204 deletions(-) [+]
line diff
     1.1 --- a/apps/aes.py	Fri Mar 27 15:33:52 2009 +0100
     1.2 +++ b/apps/aes.py	Fri Mar 27 15:44:01 2009 +0100
     1.3 @@ -20,7 +20,6 @@
     1.4  # This example shows how to use multi-party AES encryption.
     1.5  
     1.6  
     1.7 -import sys
     1.8  import time
     1.9  from optparse import OptionParser
    1.10  
    1.11 @@ -30,7 +29,7 @@
    1.12  from viff.runtime import Runtime, create_runtime, gather_shares
    1.13  from viff.config import load_config
    1.14  
    1.15 -from viff.aes import bit_decompose,AES
    1.16 +from viff.aes import AES
    1.17  
    1.18  
    1.19  parser = OptionParser(usage="Usage: %prog [options] config_file")
    1.20 @@ -89,7 +88,6 @@
    1.21  
    1.22      for i in range(24):
    1.23          inputter = i % 3 + 1
    1.24 -        
    1.25          if (inputter == id):
    1.26              key.append(rt.input([inputter], GF256, ord("b")))
    1.27          else:
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/apps/beginner.py	Fri Mar 27 15:44:01 2009 +0100
     2.3 @@ -0,0 +1,114 @@
     2.4 +#!/usr/bin/python
     2.5 +
     2.6 +# Copyright 2009 VIFF Development Team.
     2.7 +#
     2.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     2.9 +#
    2.10 +# VIFF is free software: you can redistribute it and/or modify it
    2.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    2.12 +# published by the Free Software Foundation, either version 3 of the
    2.13 +# License, or (at your option) any later version.
    2.14 +#
    2.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    2.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    2.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    2.18 +# Public License for more details.
    2.19 +#
    2.20 +# You should have received a copy of the GNU Lesser General Public
    2.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    2.22 +
    2.23 +# This file contains a simpel example of a VIFF program, which illustrates
    2.24 +# the basic features of VIFF. How to input values from the command line,
    2.25 +# from individual players in the program, add, multiply, and output values
    2.26 +# to all or some of the players.
    2.27 +
    2.28 +# Inorder to run the program follow the three steps:
    2.29 +#
    2.30 +# Generate player configurations in the viff/apps directory using:
    2.31 +#   python generate-config-files.py localhost:4001 localhost:4002 localhost:4003
    2.32 +#
    2.33 +# Generate ssl certificates in the viff/apps directory using:
    2.34 +#   python generate-certificates.py
    2.35 +#
    2.36 +# Run the program using three different shells using the command:
    2.37 +#   python beginner.py player-x.ini 79
    2.38 +# where x is replaced by the player number
    2.39 +
    2.40 +# Some useful imports.
    2.41 +import sys
    2.42 +
    2.43 +from twisted.internet import reactor
    2.44 +
    2.45 +from viff.field import GF
    2.46 +from viff.runtime import create_runtime
    2.47 +from viff.config import load_config
    2.48 +from viff.util import dprint, find_prime
    2.49 +
    2.50 +# Load the configuration from the player configuration files.
    2.51 +id, players = load_config(sys.argv[1])
    2.52 +
    2.53 +# Initialize the field we do arithmetic over.
    2.54 +Zp = GF(find_prime(2**64))
    2.55 +
    2.56 +# Read input from the commandline.
    2.57 +input = int(sys.argv[2])
    2.58 +
    2.59 +print "I am player %d and will input %s" % (id, input)
    2.60 +
    2.61 +
    2.62 +def protocol(runtime):
    2.63 +    print "-" * 64
    2.64 +    print "Program started"
    2.65 +    print
    2.66 +
    2.67 +    # Each of the players [1, 2, 3] shares his input -- resulting in
    2.68 +    # three shares. The a share is the input from P1, b is from P2,
    2.69 +    # and c is from P3.
    2.70 +    a, b, c = runtime.input([1, 2, 3], Zp, input)
    2.71 +
    2.72 +    # It is possible to make the players do different things by
    2.73 +    # branching on the players ID. In this case only P1 inputs a
    2.74 +    # number. The other two players must still participate in order to
    2.75 +    # get the hold of their share.
    2.76 +    if runtime.id == 1:
    2.77 +        s1 = runtime.input([1], Zp, 42)
    2.78 +    else:
    2.79 +        s1 = runtime.input([1], Zp, None)
    2.80 +
    2.81 +    # Secure arithmetic works like normal.
    2.82 +    a = b + c
    2.83 +    b = c * s1
    2.84 +
    2.85 +    # Outputting shares convert them from secret shared form into
    2.86 +    # cleartext. By default every player receives the cleartext.
    2.87 +    a = runtime.output(a)
    2.88 +    b = runtime.output(b)
    2.89 +    c = runtime.output(c)
    2.90 +    # Output s1 to player 2. The other players will receive None.
    2.91 +    s1 = runtime.output(s1, [2])
    2.92 +
    2.93 +    dprint("### Output a to all: %s ###", a)
    2.94 +    dprint("### Output b to all: %s ###", b)
    2.95 +    dprint("### Output c to all: %s ###", c)
    2.96 +
    2.97 +    # We only print the value of s1 for player 2, 
    2.98 +    # since only player 2 has the value of s1.
    2.99 +    if runtime.id == 2:
   2.100 +        dprint("### opened s1: %s ###", s1)
   2.101 +    
   2.102 +    # We wait for the evaluation of deferred a, b, c.
   2.103 +    runtime.wait_for(a, b, c)
   2.104 +
   2.105 +def errorHandler(failure):
   2.106 +    print "Error: %s" % failure
   2.107 +
   2.108 +
   2.109 +# Create a runtime
   2.110 +pre_runtime = create_runtime(id, players, 1)
   2.111 +pre_runtime.addCallback(protocol)
   2.112 +# This error handler will enable debugging by capturing
   2.113 +# any exceptions and print them on Standard Out.
   2.114 +pre_runtime.addErrback(errorHandler)
   2.115 +
   2.116 +print "#### Starting reactor ###"
   2.117 +reactor.run()
     3.1 --- a/apps/benchmark.py	Fri Mar 27 15:33:52 2009 +0100
     3.2 +++ b/apps/benchmark.py	Fri Mar 27 15:44:01 2009 +0100
     3.3 @@ -140,9 +140,11 @@
     3.4  
     3.5  if options.fake:
     3.6      print "Using fake field elements"
     3.7 -    GF = FakeGF
     3.8 +    Field = FakeGF
     3.9 +else:
    3.10 +    Field = GF
    3.11  
    3.12 -Zp = GF(find_prime(options.modulus))
    3.13 +Zp = Field(find_prime(options.modulus))
    3.14  print "Using field elements (%d bit modulus)" % log(Zp.modulus, 2)
    3.15  
    3.16  count = options.count
     4.1 --- a/apps/generate-config-files.py	Fri Mar 27 15:33:52 2009 +0100
     4.2 +++ b/apps/generate-config-files.py	Fri Mar 27 15:44:01 2009 +0100
     4.3 @@ -65,12 +65,15 @@
     4.4                    help="be quiet")
     4.5  parser.add_option("-n", "--players", dest="n", type="int",
     4.6                    help="number of players")
     4.7 +parser.add_option("-k", "--keysize", type="int",
     4.8 +                  help="Specify the key-size")
     4.9  parser.add_option("-t", "--threshold", dest="t", type="int",
    4.10                    help="threshold (it must hold that t < n/2)")
    4.11  parser.add_option("--skip-prss", action="store_true",
    4.12                    help="do not generate PRSS keys")
    4.13  
    4.14 -parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False)
    4.15 +parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False,
    4.16 +                    keysize=1024)
    4.17  
    4.18  (options, args) = parser.parse_args()
    4.19  
    4.20 @@ -78,8 +81,8 @@
    4.21      parser.error("must supply a hostname:port argument for each player")
    4.22  
    4.23  addresses = [arg.split(':', 1) for arg in args]
    4.24 -configs = generate_configs(options.n, options.t, addresses, options.prefix,
    4.25 -                           options.skip_prss)
    4.26 +configs = generate_configs(options.n, options.t, options.keysize, addresses,
    4.27 +                           options.prefix, options.skip_prss)
    4.28  
    4.29  for config in configs.itervalues():
    4.30      config.write()
     5.1 --- a/apps/multiply.py	Fri Mar 27 15:33:52 2009 +0100
     5.2 +++ b/apps/multiply.py	Fri Mar 27 15:44:01 2009 +0100
     5.3 @@ -1,6 +1,6 @@
     5.4  #!/usr/bin/python
     5.5  
     5.6 -# Copyright 2008 VIFF Development Team.
     5.7 +# Copyright 2008, 2009 VIFF Development Team.
     5.8  #
     5.9  # This file is part of VIFF, the Virtual Ideal Functionality Framework.
    5.10  #
    5.11 @@ -24,10 +24,13 @@
    5.12  from viff.runtime import create_runtime, Runtime
    5.13  from viff.config import load_config
    5.14  
    5.15 -parser = OptionParser()
    5.16 +parser = OptionParser("%prog config input")
    5.17  Runtime.add_options(parser)
    5.18  (options, args) = parser.parse_args()
    5.19  
    5.20 +if len(args) != 2:
    5.21 +    parser.error("please supply a config file and an integer")
    5.22 +
    5.23  Zp = GF(1031)
    5.24  
    5.25  id, players = load_config(args[0])
     6.1 --- a/doc/authors.txt	Fri Mar 27 15:33:52 2009 +0100
     6.2 +++ b/doc/authors.txt	Fri Mar 27 15:44:01 2009 +0100
     6.3 @@ -13,6 +13,8 @@
     6.4  * Jakob Illeborg Pagter
     6.5  * Sigurd Meldgaard
     6.6  * Marcel Keller <mkeller@cs.au.dk>
     6.7 +* Tord Reistad
     6.8 +* Ivan Damgård
     6.9  
    6.10  If you have been forgotten, then please checkout `the repository`_,
    6.11  add yourself to the list and `send us a patch`_!
     7.1 --- a/doc/bibliography.txt	Fri Mar 27 15:33:52 2009 +0100
     7.2 +++ b/doc/bibliography.txt	Fri Mar 27 15:44:01 2009 +0100
     7.3 @@ -74,7 +74,7 @@
     7.4  .. [Toft05] Tomas Toft, *Secure Integer Computation with Applications
     7.5     in Economics*, PhD Progress Report, July 2005, PDF__.
     7.6  
     7.7 -   .. __: http://www.daimi.au.dk/~tomas/publications/progress.pdf
     7.8 +   .. __: http://www.daimi.au.dk/~ttoft/publications/progress.pdf
     7.9  
    7.10  .. [Yao82] Andrew Chi-Chih Yao, *Protocols for Secure Computations*,
    7.11     FOCS 1982, 160-164.
     8.1 --- a/doc/index.txt	Fri Mar 27 15:33:52 2009 +0100
     8.2 +++ b/doc/index.txt	Fri Mar 27 15:44:01 2009 +0100
     8.3 @@ -32,6 +32,7 @@
     8.4     install
     8.5     implementation
     8.6     background
     8.7 +   todo
     8.8     coding-style
     8.9     development
    8.10     unit-testing
     9.1 --- a/doc/install.txt	Fri Mar 27 15:33:52 2009 +0100
     9.2 +++ b/doc/install.txt	Fri Mar 27 15:44:01 2009 +0100
     9.3 @@ -73,27 +73,39 @@
     9.4     Python-installation which comes with Mac OS X is not entirely
     9.5     up-to-date).
     9.6  
     9.7 -2) Download and Install Twisted_ from source. Notice again that Mac OS
     9.8 -   X comes with a pre-installed version of Twisted, but this is not
     9.9 -   the full Twisted installation. After installation change your
    9.10 -   ``PYTHONPATH`` (in your ``~/.bash_profile``) to::
    9.11 +2) Download and Install Twisted_ from source. There is an installer
    9.12 +   for Mac OS X 10.5 which can be used if you use Mac OS X
    9.13 +   10.5. Notice again that Mac OS X comes with a pre-installed version
    9.14 +   of Twisted, but this is not the full Twisted installation. After
    9.15 +   installation change your ``PYTHONPATH`` (in your
    9.16 +   ``~/.bash_profile``) to::
    9.17  
    9.18 -      PATH="/Library/Python/2.5/site-packages:${PATH}"
    9.19 +      export PYTHONPATH="/Library/Python/2.5/site-packages:${PYTHONPATH}"
    9.20 +      export PYTHONPATH=$PYTHONPATH:$HOME/opt/lib/python
    9.21  
    9.22  3) Optionally: download PyOpenSSL_ and tell us if it works!
    9.23  
    9.24 -4) Download and install GMPY_ following the instructions in
    9.25 +4) Download and install GMP_. You can preferably use the Macports or
    9.26 +   Fink package utilities. If you download the other dependencies from
    9.27 +   either Macports or Fink, they might depend on Python 2.4 which is
    9.28 +   not preferable, you should use Python 2.5, unless you have good
    9.29 +   reasons not to.
    9.30 +
    9.31 +5) Download and install GMPY_ following the instructions in
    9.32     ``gmpy-1.02.macosx.README.txt`` (under Downloads).
    9.33  
    9.34 -5) Install VIFF from source (see below). If you prefer you can just
    9.35 -   install it in site-packages, it makes no difference. For
    9.36 -   developers, it is perhaps a better solution in to create a symbolic
    9.37 -   link from the site-packages directory to the VIFF Python files
    9.38 -   (``viff/viff/``), as otherwise you need to re-install VIFF each time
    9.39 -   the project is modified.
    9.40 +6) Install VIFF from source (see below). If you prefer you can just
    9.41 +   install it in site-packages, it makes no difference.
    9.42  
    9.43 -6) Proceed to `testing`_.
    9.44 +   For developers, either add VIFF to the PYTHONPATH::
    9.45  
    9.46 +      export PYTHONPATH=$PYTHONPATH:$HOME/path-to-viff/viff
    9.47 +
    9.48 +   or create a symbolic link from the site-packages directory to the
    9.49 +   VIFF Python files (``viff/viff/``), as otherwise you need to
    9.50 +   re-install VIFF each time the project is modified.
    9.51 +
    9.52 +7) Proceed to `testing`_.
    9.53  
    9.54  GNU/Linux
    9.55  ---------
    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/doc/todo.txt	Fri Mar 27 15:44:01 2009 +0100
    10.3 @@ -0,0 +1,50 @@
    10.4 +
    10.5 +Planned Work on VIFF
    10.6 +====================
    10.7 +
    10.8 +This document collects the bigger pieces of work we plan to do on
    10.9 +VIFF --- pieces too big for the bug tracker.
   10.10 +
   10.11 +
   10.12 +Active Security
   10.13 +---------------
   10.14 +
   10.15 +The protocol implemented in :mod:`viff.active` is (believed to be)
   10.16 +secure against active adversaries, but only as long as they don't
   10.17 +actually try to cheat! In other words, the players will crash in bad
   10.18 +ways if malformed data is received or too few shares are received.
   10.19 +
   10.20 +The following points should be addressed:
   10.21 +
   10.22 +* Error correction. The honest players must tolerate being sent wrong
   10.23 +  shares or no shares at all from the corrupt players.
   10.24 +
   10.25 +  This is related to Issue4_, Issue29_, and Issue70_.
   10.26 +
   10.27 +  .. _Issue4: http://tracker.viff.dk/issue4
   10.28 +  .. _Issue29: http://tracker.viff.dk/issue29
   10.29 +  .. _Issue70: http://tracker.viff.dk/issue70
   10.30 +
   10.31 +* Byzantine agreement. After the preprocessing phase a Byzantime
   10.32 +  agreement protocol should be run in order to determine if all honest
   10.33 +  players are ready to continue.
   10.34 +
   10.35 +  At the moment an honest players simply aborts the protocol if it
   10.36 +  detects any form of cheating --- the "idea" being that this will
   10.37 +  make the other honest players crash too, thereby effectively halting
   10.38 +  the protocol.
   10.39 +
   10.40 +Self Trust
   10.41 +----------
   10.42 +
   10.43 +Implement an (actively) secure protocol with threshold ``t = n-1``
   10.44 +based on the "triples approach" of Claudio Orlandi and Jesper Buus
   10.45 +Nielsen. There will soon be a paper describing the protocol.
   10.46 +
   10.47 +Covert Adversaries
   10.48 +------------------
   10.49 +
   10.50 +Implement an actively secure protocol for a covert adversary and
   10.51 +threshold ``t < n/2``. The goal is to have almost the same complexity
   10.52 +as for the passive case. Martin Geisler is working on a paper
   10.53 +describing a solution.
    11.1 --- a/setup.py	Fri Mar 27 15:33:52 2009 +0100
    11.2 +++ b/setup.py	Fri Mar 27 15:44:01 2009 +0100
    11.3 @@ -4,7 +4,7 @@
    11.4  # For a local install into ~/opt, use:  python setup.py --home=~/opt
    11.5  # For more options, use:                python setup.py --help
    11.6  
    11.7 -# Copyright 2007, 2008 VIFF Development Team.
    11.8 +# Copyright 2007, 2008, 2009 VIFF Development Team.
    11.9  #
   11.10  # This file is part of VIFF, the Virtual Ideal Functionality Framework.
   11.11  #
   11.12 @@ -33,22 +33,22 @@
   11.13  class hg_sdist(sdist):
   11.14      def get_file_list(self):
   11.15          try:
   11.16 -            # Attempt the import here so that users can run the other
   11.17 -            # Distutils commands without needing Mercurial.
   11.18 -            from mercurial import hg
   11.19 -        except ImportError:
   11.20              from distutils.errors import DistutilsModuleError
   11.21 -            raise DistutilsModuleError("could not import mercurial")
   11.22 +            import subprocess
   11.23 +            p = subprocess.Popen(['hg', 'manifest'], stdout=subprocess.PIPE)
   11.24 +            exitcode = p.wait()
   11.25 +            if exitcode != 0:
   11.26 +                raise DistutilsModuleError("Mercurial exited with non-zero "
   11.27 +                                           "exit code: %d" % exitcode)
   11.28 +            files = p.stdout.read().strip().split('\n')
   11.29  
   11.30 -        repo = hg.repository(None)
   11.31 -        changeset = repo.changectx(None)
   11.32 -        files = changeset.manifest().keys()
   11.33 -
   11.34 -        # Add the files *before* the normal manifest magic is done.
   11.35 -        # That allows the manifest template to exclude some files
   11.36 -        # tracked by hg and to include others.
   11.37 -        self.filelist.extend(files)
   11.38 -        sdist.get_file_list(self)
   11.39 +            # Add the files *before* the normal manifest magic is
   11.40 +            # done. That allows the manifest template to exclude some
   11.41 +            # files tracked by hg and to include others.
   11.42 +            self.filelist.extend(files)
   11.43 +            sdist.get_file_list(self)
   11.44 +        except OSError, e:
   11.45 +            raise DistutilsModuleError("could not execute Mercurial: %s" % e)
   11.46  
   11.47  setup(name='viff',
   11.48        version=viff.__version__,
    12.1 --- a/viff/aes.py	Fri Mar 27 15:33:52 2009 +0100
    12.2 +++ b/viff/aes.py	Fri Mar 27 15:44:01 2009 +0100
    12.3 @@ -58,14 +58,17 @@
    12.4  
    12.5  
    12.6  class AES:
    12.7 -    """AES instantiation:
    12.8 +    """AES instantiation.
    12.9  
   12.10 -    >>> aes = AES(runtime, 192)
   12.11 -    >>> cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
   12.12 -    >>> key = [runtime.prss_share_random(GF256) for i in range(192/8)]
   12.13 -    >>> ciphertext = aes.encrypt("abcdefghijklmnop", key)
   12.14 -    >>> ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
   12.15 -    >>> ciphertext = aes.encrypt(cleartext, key)
   12.16 +    This class is used together with a :class:`viff.runtime.Runtime`
   12.17 +    object::
   12.18 +
   12.19 +        aes = AES(runtime, 192)
   12.20 +        cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
   12.21 +        key = [runtime.prss_share_random(GF256) for i in range(192/8)]
   12.22 +        ciphertext = aes.encrypt("abcdefghijklmnop", key)
   12.23 +        ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
   12.24 +        ciphertext = aes.encrypt(cleartext, key)
   12.25  
   12.26      In every case *ciphertext* will be a list of shares over GF256.
   12.27      """
    13.1 --- a/viff/config.py	Fri Mar 27 15:33:52 2009 +0100
    13.2 +++ b/viff/config.py	Fri Mar 27 15:44:01 2009 +0100
    13.3 @@ -158,7 +158,7 @@
    13.4      return owner_id, players
    13.5  
    13.6  
    13.7 -def generate_configs(n, t, addresses=None, prefix=None, skip_prss=False):
    13.8 +def generate_configs(n, t, keysize=1024, addresses=None, prefix=None, skip_prss=False):
    13.9      """Generate player configurations.
   13.10  
   13.11      Generates *n* configuration objects with a threshold of *t*. The
   13.12 @@ -194,8 +194,7 @@
   13.13          """Convert a dealer ID to a string."""
   13.14          return "Dealer " + str(dealer)
   13.15  
   13.16 -    # TODO: remove hard-coded key size.
   13.17 -    key_pairs = dict([(p, paillier.generate_keys(1024)) for p in players])
   13.18 +    key_pairs = dict([(p, paillier.generate_keys(keysize)) for p in players])
   13.19  
   13.20      configs = {}
   13.21      for p in players:
    14.1 --- a/viff/field.py	Fri Mar 27 15:33:52 2009 +0100
    14.2 +++ b/viff/field.py	Fri Mar 27 15:44:01 2009 +0100
    14.3 @@ -32,6 +32,7 @@
    14.4  
    14.5  >>> x = Zp(10)
    14.6  >>> y = Zp(15)
    14.7 +>>> z = Zp(1)
    14.8  
    14.9  Addition and subtraction (with modulo reduction):
   14.10  
   14.11 @@ -40,6 +41,15 @@
   14.12  >>> x - y
   14.13  {14}
   14.14  
   14.15 +Bitwise xor for field elements:
   14.16 +
   14.17 +>>> z ^ z
   14.18 +{0}
   14.19 +>>> z ^ 0
   14.20 +{1}
   14.21 +>>> 1 ^ z
   14.22 +{0}
   14.23 +
   14.24  Exponentiation:
   14.25  
   14.26  >>> x**3
   14.27 @@ -69,6 +79,7 @@
   14.28  
   14.29  
   14.30  from gmpy import mpz
   14.31 +from math import log, ceil
   14.32  
   14.33  
   14.34  class FieldElement(object):
   14.35 @@ -84,6 +95,25 @@
   14.36  
   14.37      __long__ = __int__
   14.38  
   14.39 +    def split(self):
   14.40 +        """Splits self into bit array LSB first.
   14.41 +
   14.42 +        >>> Zp = GF(29)
   14.43 +        >>> Zp(3).split()
   14.44 +        [{1}, {1}, {0}, {0}, {0}]
   14.45 +        >>> Zp(28).split()
   14.46 +        [{0}, {0}, {1}, {1}, {1}]
   14.47 +        >>> GF256(8).split()
   14.48 +        [[0], [0], [0], [1], [0], [0], [0], [0]]
   14.49 +        """
   14.50 +        length = int(ceil(log(self.modulus,2)))
   14.51 +        result = [0] * length
   14.52 +        temp = self.value
   14.53 +        for i in range(length):
   14.54 +            result[i] = self.field(temp % 2)
   14.55 +            temp = temp // 2
   14.56 +        return result
   14.57 +
   14.58  #: Inversion table.
   14.59  #:
   14.60  #: Maps a value *x* to *x^-1*. See `_generate_tables`.
   14.61 @@ -377,6 +407,20 @@
   14.62              """Subtraction (reflected argument version)."""
   14.63              return GFElement(other - self.value)
   14.64  
   14.65 +        def __xor__(self, other):
   14.66 +            """Xor for bitvalues."""
   14.67 +            if not isinstance(other, (GFElement, int, long)):
   14.68 +                return NotImplemented
   14.69 +            try:
   14.70 +                assert self.field is other.field, "Fields must be identical"
   14.71 +                return GFElement(self.value ^ other.value)
   14.72 +            except AttributeError:
   14.73 +                return GFElement(self.value ^ other)
   14.74 +
   14.75 +        def __rxor__(self, other):
   14.76 +            """Xor for bitvalues (reflected argument version)."""
   14.77 +            return GFElement(other ^ self.value)
   14.78 +
   14.79          def __mul__(self, other):
   14.80              """Multiplication."""
   14.81              if not isinstance(other, (GFElement, int, long)):
    15.1 --- a/viff/passive.py	Fri Mar 27 15:33:52 2009 +0100
    15.2 +++ b/viff/passive.py	Fri Mar 27 15:44:01 2009 +0100
    15.3 @@ -214,7 +214,7 @@
    15.4      def pow(self, share, exponent):
    15.5          """Exponentation of a share to an integer by square-and-multiply."""
    15.6  
    15.7 -        assert isinstance(exponent, int), "Exponent must be an integer"
    15.8 +        assert isinstance(exponent, (int, long)), "Exponent must be an integer"
    15.9          assert exponent >= 0, "Exponent must be non-negative"
   15.10  
   15.11          if exponent == 0:
   15.12 @@ -464,6 +464,32 @@
   15.13          unless there is only one inputter in which case the
   15.14          share is returned directly.
   15.15  
   15.16 +        In code it is used like this::
   15.17 +
   15.18 +            a, b, c = runtime.shamir_share([1, 2, 3], Zp, x)
   15.19 +
   15.20 +        where ``Zp`` is a field and ``x`` is a Python integer holding
   15.21 +        the input of each player (three inputs in total).
   15.22 +
   15.23 +        If only a subset of the players provide input it looks like
   15.24 +        this::
   15.25 +
   15.26 +            if runtime.id == 1:
   15.27 +                a = runtime.shamir_share([1], Zp, x)
   15.28 +            else:
   15.29 +                a = runtime.shamir_share([1], Zp)
   15.30 +
   15.31 +        Instead of branching when calling :meth:`shamir_share`, one
   15.32 +        can give ``None`` as input::
   15.33 +
   15.34 +            if runtime.id == 1:
   15.35 +                x = int(raw_input("Input x: "))
   15.36 +            else:
   15.37 +                x = None
   15.38 +            a = runtime.shamir_share([1], Zp, x)
   15.39 +
   15.40 +        which might be practical in some cases.
   15.41 +
   15.42          Communication cost: n elements transmitted.
   15.43          """
   15.44          assert number is None or self.id in inputters
    16.1 --- a/viff/runtime.py	Fri Mar 27 15:33:52 2009 +0100
    16.2 +++ b/viff/runtime.py	Fri Mar 27 15:44:01 2009 +0100
    16.3 @@ -514,11 +514,11 @@
    16.4          All connections are closed and the runtime cannot be used
    16.5          again after this has been called.
    16.6          """
    16.7 -        print "Synchronizing shutdown... ",
    16.8 +        print "Synchronizing shutdown...",
    16.9  
   16.10          def close_connections(_):
   16.11              print "done."
   16.12 -            print "Closing connections... ",
   16.13 +            print "Closing connections...",
   16.14              results = [maybeDeferred(self.port.stopListening)]
   16.15              for protocol in self.protocols.itervalues():
   16.16                  results.append(protocol.lost_connection)
   16.17 @@ -527,7 +527,7 @@
   16.18  
   16.19          def stop_reactor(_):
   16.20              print "done."
   16.21 -            print "Stopping reactor... ",
   16.22 +            print "Stopping reactor...",
   16.23              reactor.stop()
   16.24              print "done."
   16.25  
    17.1 --- a/viff/test/rijndael.py	Fri Mar 27 15:33:52 2009 +0100
    17.2 +++ b/viff/test/rijndael.py	Fri Mar 27 15:44:01 2009 +0100
    17.3 @@ -36,109 +36,6 @@
    17.4  # [keysize][block_size]
    17.5  num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32: {16: 14, 24: 14, 32: 14}}
    17.6  
    17.7 -A = [[1, 1, 1, 1, 1, 0, 0, 0],
    17.8 -     [0, 1, 1, 1, 1, 1, 0, 0],
    17.9 -     [0, 0, 1, 1, 1, 1, 1, 0],
   17.10 -     [0, 0, 0, 1, 1, 1, 1, 1],
   17.11 -     [1, 0, 0, 0, 1, 1, 1, 1],
   17.12 -     [1, 1, 0, 0, 0, 1, 1, 1],
   17.13 -     [1, 1, 1, 0, 0, 0, 1, 1],
   17.14 -     [1, 1, 1, 1, 0, 0, 0, 1]]
   17.15 -
   17.16 -# produce log and alog tables, needed for multiplying in the
   17.17 -# field GF(2^m) (generator = 3)
   17.18 -alog = [1]
   17.19 -for i in xrange(255):
   17.20 -    j = (alog[-1] << 1) ^ alog[-1]
   17.21 -    if j & 0x100 != 0:
   17.22 -        j ^= 0x11B
   17.23 -    alog.append(j)
   17.24 -
   17.25 -log = [0] * 256
   17.26 -for i in xrange(1, 255):
   17.27 -    log[alog[i]] = i
   17.28 -
   17.29 -# multiply two elements of GF(2^m)
   17.30 -def mul(a, b):
   17.31 -    if a == 0 or b == 0:
   17.32 -        return 0
   17.33 -    return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]
   17.34 -
   17.35 -# substitution box based on F^{-1}(x)
   17.36 -box = [[0] * 8 for i in xrange(256)]
   17.37 -box[1][7] = 1
   17.38 -for i in xrange(2, 256):
   17.39 -    j = alog[255 - log[i]]
   17.40 -    for t in xrange(8):
   17.41 -        box[i][t] = (j >> (7 - t)) & 0x01
   17.42 -
   17.43 -B = [0, 1, 1, 0, 0, 0, 1, 1]
   17.44 -
   17.45 -# affine transform:  box[i] <- B + A*box[i]
   17.46 -cox = [[0] * 8 for i in xrange(256)]
   17.47 -for i in xrange(256):
   17.48 -    for t in xrange(8):
   17.49 -        cox[i][t] = B[t]
   17.50 -        for j in xrange(8):
   17.51 -            cox[i][t] ^= A[t][j] * box[i][j]
   17.52 -
   17.53 -# S-boxes and inverse S-boxes
   17.54 -S =  [0] * 256
   17.55 -Si = [0] * 256
   17.56 -for i in xrange(256):
   17.57 -    S[i] = cox[i][0] << 7
   17.58 -    for t in xrange(1, 8):
   17.59 -        S[i] ^= cox[i][t] << (7-t)
   17.60 -    Si[S[i] & 0xFF] = i
   17.61 -
   17.62 -# T-boxes
   17.63 -G = [[2, 1, 1, 3],
   17.64 -    [3, 2, 1, 1],
   17.65 -    [1, 3, 2, 1],
   17.66 -    [1, 1, 3, 2]]
   17.67 -
   17.68 -AA = [[0] * 8 for i in xrange(4)]
   17.69 -
   17.70 -for i in xrange(4):
   17.71 -    for j in xrange(4):
   17.72 -        AA[i][j] = G[i][j]
   17.73 -        AA[i][i+4] = 1
   17.74 -
   17.75 -for i in xrange(4):
   17.76 -    pivot = AA[i][i]
   17.77 -    if pivot == 0:
   17.78 -        t = i + 1
   17.79 -        while AA[t][i] == 0 and t < 4:
   17.80 -            t += 1
   17.81 -            assert t != 4, 'G matrix must be invertible'
   17.82 -            for j in xrange(8):
   17.83 -                AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
   17.84 -            pivot = AA[i][i]
   17.85 -    for j in xrange(8):
   17.86 -        if AA[i][j] != 0:
   17.87 -            AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255]
   17.88 -    for t in xrange(4):
   17.89 -        if i != t:
   17.90 -            for j in xrange(i+1, 8):
   17.91 -                AA[t][j] ^= mul(AA[i][j], AA[t][i])
   17.92 -            AA[t][i] = 0
   17.93 -
   17.94 -iG = [[0] * 4 for i in xrange(4)]
   17.95 -
   17.96 -for i in xrange(4):
   17.97 -    for j in xrange(4):
   17.98 -        iG[i][j] = AA[i][j + 4]
   17.99 -
  17.100 -def mul4(a, bs):
  17.101 -    if a == 0:
  17.102 -        return 0
  17.103 -    r = 0
  17.104 -    for b in bs:
  17.105 -        r <<= 8
  17.106 -        if b != 0:
  17.107 -            r = r | mul(a, b)
  17.108 -    return r
  17.109 -
  17.110  T1 = []
  17.111  T2 = []
  17.112  T3 = []
  17.113 @@ -152,48 +49,141 @@
  17.114  U3 = []
  17.115  U4 = []
  17.116  
  17.117 -for t in xrange(256):
  17.118 -    s = S[t]
  17.119 -    T1.append(mul4(s, G[0]))
  17.120 -    T2.append(mul4(s, G[1]))
  17.121 -    T3.append(mul4(s, G[2]))
  17.122 -    T4.append(mul4(s, G[3]))
  17.123 +S =  [0] * 256
  17.124 +Si = [0] * 256
  17.125  
  17.126 -    s = Si[t]
  17.127 -    T5.append(mul4(s, iG[0]))
  17.128 -    T6.append(mul4(s, iG[1]))
  17.129 -    T7.append(mul4(s, iG[2]))
  17.130 -    T8.append(mul4(s, iG[3]))
  17.131 +rcon = [1]
  17.132  
  17.133 -    U1.append(mul4(t, iG[0]))
  17.134 -    U2.append(mul4(t, iG[1]))
  17.135 -    U3.append(mul4(t, iG[2]))
  17.136 -    U4.append(mul4(t, iG[3]))
  17.137 +def initialize():
  17.138 +    """Called once at module import to initialize constants defined above."""
  17.139  
  17.140 -# round constants
  17.141 -rcon = [1]
  17.142 -r = 1
  17.143 -for t in xrange(1, 30):
  17.144 -    r = mul(2, r)
  17.145 -    rcon.append(r)
  17.146 +    A = [[1, 1, 1, 1, 1, 0, 0, 0],
  17.147 +         [0, 1, 1, 1, 1, 1, 0, 0],
  17.148 +         [0, 0, 1, 1, 1, 1, 1, 0],
  17.149 +         [0, 0, 0, 1, 1, 1, 1, 1],
  17.150 +         [1, 0, 0, 0, 1, 1, 1, 1],
  17.151 +         [1, 1, 0, 0, 0, 1, 1, 1],
  17.152 +         [1, 1, 1, 0, 0, 0, 1, 1],
  17.153 +         [1, 1, 1, 1, 0, 0, 0, 1]]
  17.154  
  17.155 -del A
  17.156 -del AA
  17.157 -del pivot
  17.158 -del B
  17.159 -del G
  17.160 -del box
  17.161 -del log
  17.162 -del alog
  17.163 -del i
  17.164 -del j
  17.165 -del r
  17.166 -del s
  17.167 -del t
  17.168 -del mul
  17.169 -del mul4
  17.170 -del cox
  17.171 -del iG
  17.172 +    # produce log and alog tables, needed for multiplying in the
  17.173 +    # field GF(2^m) (generator = 3)
  17.174 +    alog = [1]
  17.175 +    for i in xrange(255):
  17.176 +        j = (alog[-1] << 1) ^ alog[-1]
  17.177 +        if j & 0x100 != 0:
  17.178 +            j ^= 0x11B
  17.179 +        alog.append(j)
  17.180 +
  17.181 +    log = [0] * 256
  17.182 +    for i in xrange(1, 255):
  17.183 +        log[alog[i]] = i
  17.184 +
  17.185 +    # multiply two elements of GF(2^m)
  17.186 +    def mul(a, b):
  17.187 +        if a == 0 or b == 0:
  17.188 +            return 0
  17.189 +        return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]
  17.190 +
  17.191 +    # substitution box based on F^{-1}(x)
  17.192 +    box = [[0] * 8 for i in xrange(256)]
  17.193 +    box[1][7] = 1
  17.194 +    for i in xrange(2, 256):
  17.195 +        j = alog[255 - log[i]]
  17.196 +        for t in xrange(8):
  17.197 +            box[i][t] = (j >> (7 - t)) & 0x01
  17.198 +
  17.199 +    B = [0, 1, 1, 0, 0, 0, 1, 1]
  17.200 +
  17.201 +    # affine transform:  box[i] <- B + A*box[i]
  17.202 +    cox = [[0] * 8 for i in xrange(256)]
  17.203 +    for i in xrange(256):
  17.204 +        for t in xrange(8):
  17.205 +            cox[i][t] = B[t]
  17.206 +            for j in xrange(8):
  17.207 +                cox[i][t] ^= A[t][j] * box[i][j]
  17.208 +
  17.209 +    # S-boxes and inverse S-boxes
  17.210 +    for i in xrange(256):
  17.211 +        S[i] = cox[i][0] << 7
  17.212 +        for t in xrange(1, 8):
  17.213 +            S[i] ^= cox[i][t] << (7-t)
  17.214 +        Si[S[i] & 0xFF] = i
  17.215 +
  17.216 +    # T-boxes
  17.217 +    G = [[2, 1, 1, 3],
  17.218 +        [3, 2, 1, 1],
  17.219 +        [1, 3, 2, 1],
  17.220 +        [1, 1, 3, 2]]
  17.221 +
  17.222 +    AA = [[0] * 8 for i in xrange(4)]
  17.223 +
  17.224 +    for i in xrange(4):
  17.225 +        for j in xrange(4):
  17.226 +            AA[i][j] = G[i][j]
  17.227 +            AA[i][i+4] = 1
  17.228 +
  17.229 +    for i in xrange(4):
  17.230 +        pivot = AA[i][i]
  17.231 +        if pivot == 0:
  17.232 +            t = i + 1
  17.233 +            while AA[t][i] == 0 and t < 4:
  17.234 +                t += 1
  17.235 +                assert t != 4, 'G matrix must be invertible'
  17.236 +                for j in xrange(8):
  17.237 +                    AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
  17.238 +                pivot = AA[i][i]
  17.239 +        for j in xrange(8):
  17.240 +            if AA[i][j] != 0:
  17.241 +                AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255]
  17.242 +        for t in xrange(4):
  17.243 +            if i != t:
  17.244 +                for j in xrange(i+1, 8):
  17.245 +                    AA[t][j] ^= mul(AA[i][j], AA[t][i])
  17.246 +                AA[t][i] = 0
  17.247 +
  17.248 +    iG = [[0] * 4 for i in xrange(4)]
  17.249 +
  17.250 +    for i in xrange(4):
  17.251 +        for j in xrange(4):
  17.252 +            iG[i][j] = AA[i][j + 4]
  17.253 +
  17.254 +    def mul4(a, bs):
  17.255 +        if a == 0:
  17.256 +            return 0
  17.257 +        r = 0
  17.258 +        for b in bs:
  17.259 +            r <<= 8
  17.260 +            if b != 0:
  17.261 +                r = r | mul(a, b)
  17.262 +        return r
  17.263 +
  17.264 +    for t in xrange(256):
  17.265 +        s = S[t]
  17.266 +        T1.append(mul4(s, G[0]))
  17.267 +        T2.append(mul4(s, G[1]))
  17.268 +        T3.append(mul4(s, G[2]))
  17.269 +        T4.append(mul4(s, G[3]))
  17.270 +
  17.271 +        s = Si[t]
  17.272 +        T5.append(mul4(s, iG[0]))
  17.273 +        T6.append(mul4(s, iG[1]))
  17.274 +        T7.append(mul4(s, iG[2]))
  17.275 +        T8.append(mul4(s, iG[3]))
  17.276 +
  17.277 +        U1.append(mul4(t, iG[0]))
  17.278 +        U2.append(mul4(t, iG[1]))
  17.279 +        U3.append(mul4(t, iG[2]))
  17.280 +        U4.append(mul4(t, iG[3]))
  17.281 +
  17.282 +    # round constants
  17.283 +    r = 1
  17.284 +    for t in xrange(1, 30):
  17.285 +        r = mul(2, r)
  17.286 +        rcon.append(r)
  17.287 +
  17.288 +# initialize constants
  17.289 +initialize()
  17.290  
  17.291  class rijndael:
  17.292      def __init__(self, key, block_size = 16):
    18.1 --- a/viff/test/test_util.py	Fri Mar 27 15:33:52 2009 +0100
    18.2 +++ b/viff/test/test_util.py	Fri Mar 27 15:44:01 2009 +0100
    18.3 @@ -21,8 +21,7 @@
    18.4  
    18.5  from viff.util import deep_wait
    18.6  from viff.field import GF, GF256
    18.7 -import viff.shamir
    18.8 -import viff.prss
    18.9 +from viff import shamir, prss
   18.10  
   18.11  from twisted.trial.unittest import TestCase
   18.12  from twisted.internet.defer import Deferred
   18.13 @@ -36,7 +35,7 @@
   18.14  
   18.15      # Modules which will be reloaded with and without VIFF_FAKE set in
   18.16      # the environment.
   18.17 -    _modules = [viff.shamir, viff.prss]
   18.18 +    _modules = [shamir, prss]
   18.19  
   18.20      def setUp(self):
   18.21          self.field = GF(1031)
   18.22 @@ -51,29 +50,27 @@
   18.23              reload(module)
   18.24  
   18.25      def test_shamir_share(self):
   18.26 -        from viff.shamir import share
   18.27          secret = self.field(17)
   18.28 -        shares = share(secret, 1, 3)
   18.29 +        shares = shamir.share(secret, 1, 3)
   18.30          self.assertEquals(shares[0][1], secret)
   18.31          self.assertEquals(shares[1][1], secret)
   18.32          self.assertEquals(shares[2][1], secret)
   18.33  
   18.34      def test_shamir_recombine(self):
   18.35 -        from viff.shamir import recombine
   18.36          shares = [(1, 1), None, None]
   18.37 -        self.assertEquals(recombine(shares), 1)
   18.38 +        self.assertEquals(shamir.recombine(shares), 1)
   18.39  
   18.40      def test_prss(self):
   18.41 -        share = viff.prss.prss(None, None, self.field, None, None)
   18.42 +        share = prss.prss(None, None, self.field, None, None)
   18.43          self.assertEquals(share, self.field(7))
   18.44  
   18.45      def test_prss_lsb(self):
   18.46 -        (share, bit) = viff.prss.prss_lsb(None, None, self.field, None, None)
   18.47 +        (share, bit) = prss.prss_lsb(None, None, self.field, None, None)
   18.48          self.assertEquals(share, self.field(7))
   18.49          self.assertEquals(bit, GF256(1))
   18.50  
   18.51      def test_prss_zero(self):
   18.52 -        share = viff.prss.prss_zero(None, None, None, self.field, None, None)
   18.53 +        share = prss.prss_zero(None, None, None, self.field, None, None)
   18.54          self.assertEquals(share, self.field(0))
   18.55  
   18.56  
    19.1 --- a/viff/util.py	Fri Mar 27 15:33:52 2009 +0100
    19.2 +++ b/viff/util.py	Fri Mar 27 15:44:01 2009 +0100
    19.3 @@ -388,6 +388,16 @@
    19.4                           for key, value in usage.iteritems()])
    19.5          _last_memory_usage = usage
    19.6  
    19.7 +def if_then(cond, a, b):
    19.8 +    """If then else operator works both for integers and for shares.
    19.9 +
   19.10 +    >>> if_then(0, 3, 6)
   19.11 +    6
   19.12 +    >>> if_then(1, 3, 6)
   19.13 +    3
   19.14 +    """
   19.15 +    return b + cond * (a - b)
   19.16 +
   19.17  if __name__ == "__main__":
   19.18      import doctest    #pragma NO COVER
   19.19      doctest.testmod() #pragma NO COVER