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 wrap: on
line diff
--- a/apps/aes.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/aes.py	Fri Mar 27 15:44:01 2009 +0100
@@ -20,7 +20,6 @@
 # This example shows how to use multi-party AES encryption.
 
 
-import sys
 import time
 from optparse import OptionParser
 
@@ -30,7 +29,7 @@
 from viff.runtime import Runtime, create_runtime, gather_shares
 from viff.config import load_config
 
-from viff.aes import bit_decompose,AES
+from viff.aes import AES
 
 
 parser = OptionParser(usage="Usage: %prog [options] config_file")
@@ -89,7 +88,6 @@
 
     for i in range(24):
         inputter = i % 3 + 1
-        
         if (inputter == id):
             key.append(rt.input([inputter], GF256, ord("b")))
         else:
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/apps/beginner.py	Fri Mar 27 15:44:01 2009 +0100
@@ -0,0 +1,114 @@
+#!/usr/bin/python
+
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+# This file contains a simpel example of a VIFF program, which illustrates
+# the basic features of VIFF. How to input values from the command line,
+# from individual players in the program, add, multiply, and output values
+# to all or some of the players.
+
+# Inorder to run the program follow the three steps:
+#
+# Generate player configurations in the viff/apps directory using:
+#   python generate-config-files.py localhost:4001 localhost:4002 localhost:4003
+#
+# Generate ssl certificates in the viff/apps directory using:
+#   python generate-certificates.py
+#
+# Run the program using three different shells using the command:
+#   python beginner.py player-x.ini 79
+# where x is replaced by the player number
+
+# Some useful imports.
+import sys
+
+from twisted.internet import reactor
+
+from viff.field import GF
+from viff.runtime import create_runtime
+from viff.config import load_config
+from viff.util import dprint, find_prime
+
+# Load the configuration from the player configuration files.
+id, players = load_config(sys.argv[1])
+
+# Initialize the field we do arithmetic over.
+Zp = GF(find_prime(2**64))
+
+# Read input from the commandline.
+input = int(sys.argv[2])
+
+print "I am player %d and will input %s" % (id, input)
+
+
+def protocol(runtime):
+    print "-" * 64
+    print "Program started"
+    print
+
+    # Each of the players [1, 2, 3] shares his input -- resulting in
+    # three shares. The a share is the input from P1, b is from P2,
+    # and c is from P3.
+    a, b, c = runtime.input([1, 2, 3], Zp, input)
+
+    # It is possible to make the players do different things by
+    # branching on the players ID. In this case only P1 inputs a
+    # number. The other two players must still participate in order to
+    # get the hold of their share.
+    if runtime.id == 1:
+        s1 = runtime.input([1], Zp, 42)
+    else:
+        s1 = runtime.input([1], Zp, None)
+
+    # Secure arithmetic works like normal.
+    a = b + c
+    b = c * s1
+
+    # Outputting shares convert them from secret shared form into
+    # cleartext. By default every player receives the cleartext.
+    a = runtime.output(a)
+    b = runtime.output(b)
+    c = runtime.output(c)
+    # Output s1 to player 2. The other players will receive None.
+    s1 = runtime.output(s1, [2])
+
+    dprint("### Output a to all: %s ###", a)
+    dprint("### Output b to all: %s ###", b)
+    dprint("### Output c to all: %s ###", c)
+
+    # We only print the value of s1 for player 2, 
+    # since only player 2 has the value of s1.
+    if runtime.id == 2:
+        dprint("### opened s1: %s ###", s1)
+    
+    # We wait for the evaluation of deferred a, b, c.
+    runtime.wait_for(a, b, c)
+
+def errorHandler(failure):
+    print "Error: %s" % failure
+
+
+# Create a runtime
+pre_runtime = create_runtime(id, players, 1)
+pre_runtime.addCallback(protocol)
+# This error handler will enable debugging by capturing
+# any exceptions and print them on Standard Out.
+pre_runtime.addErrback(errorHandler)
+
+print "#### Starting reactor ###"
+reactor.run()
--- a/apps/benchmark.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/benchmark.py	Fri Mar 27 15:44:01 2009 +0100
@@ -140,9 +140,11 @@
 
 if options.fake:
     print "Using fake field elements"
-    GF = FakeGF
+    Field = FakeGF
+else:
+    Field = GF
 
-Zp = GF(find_prime(options.modulus))
+Zp = Field(find_prime(options.modulus))
 print "Using field elements (%d bit modulus)" % log(Zp.modulus, 2)
 
 count = options.count
--- a/apps/generate-config-files.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/generate-config-files.py	Fri Mar 27 15:44:01 2009 +0100
@@ -65,12 +65,15 @@
                   help="be quiet")
 parser.add_option("-n", "--players", dest="n", type="int",
                   help="number of players")
+parser.add_option("-k", "--keysize", type="int",
+                  help="Specify the key-size")
 parser.add_option("-t", "--threshold", dest="t", type="int",
                   help="threshold (it must hold that t < n/2)")
 parser.add_option("--skip-prss", action="store_true",
                   help="do not generate PRSS keys")
 
-parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False)
+parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False,
+                    keysize=1024)
 
 (options, args) = parser.parse_args()
 
@@ -78,8 +81,8 @@
     parser.error("must supply a hostname:port argument for each player")
 
 addresses = [arg.split(':', 1) for arg in args]
-configs = generate_configs(options.n, options.t, addresses, options.prefix,
-                           options.skip_prss)
+configs = generate_configs(options.n, options.t, options.keysize, addresses,
+                           options.prefix, options.skip_prss)
 
 for config in configs.itervalues():
     config.write()
--- a/apps/multiply.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/multiply.py	Fri Mar 27 15:44:01 2009 +0100
@@ -1,6 +1,6 @@
 #!/usr/bin/python
 
-# Copyright 2008 VIFF Development Team.
+# Copyright 2008, 2009 VIFF Development Team.
 #
 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
 #
@@ -24,10 +24,13 @@
 from viff.runtime import create_runtime, Runtime
 from viff.config import load_config
 
-parser = OptionParser()
+parser = OptionParser("%prog config input")
 Runtime.add_options(parser)
 (options, args) = parser.parse_args()
 
+if len(args) != 2:
+    parser.error("please supply a config file and an integer")
+
 Zp = GF(1031)
 
 id, players = load_config(args[0])
--- a/doc/authors.txt	Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/authors.txt	Fri Mar 27 15:44:01 2009 +0100
@@ -13,6 +13,8 @@
 * Jakob Illeborg Pagter
 * Sigurd Meldgaard
 * Marcel Keller <mkeller@cs.au.dk>
+* Tord Reistad
+* Ivan Damgård
 
 If you have been forgotten, then please checkout `the repository`_,
 add yourself to the list and `send us a patch`_!
--- a/doc/bibliography.txt	Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/bibliography.txt	Fri Mar 27 15:44:01 2009 +0100
@@ -74,7 +74,7 @@
 .. [Toft05] Tomas Toft, *Secure Integer Computation with Applications
    in Economics*, PhD Progress Report, July 2005, PDF__.
 
-   .. __: http://www.daimi.au.dk/~tomas/publications/progress.pdf
+   .. __: http://www.daimi.au.dk/~ttoft/publications/progress.pdf
 
 .. [Yao82] Andrew Chi-Chih Yao, *Protocols for Secure Computations*,
    FOCS 1982, 160-164.
--- a/doc/index.txt	Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/index.txt	Fri Mar 27 15:44:01 2009 +0100
@@ -32,6 +32,7 @@
    install
    implementation
    background
+   todo
    coding-style
    development
    unit-testing
--- a/doc/install.txt	Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/install.txt	Fri Mar 27 15:44:01 2009 +0100
@@ -73,27 +73,39 @@
    Python-installation which comes with Mac OS X is not entirely
    up-to-date).
 
-2) Download and Install Twisted_ from source. Notice again that Mac OS
-   X comes with a pre-installed version of Twisted, but this is not
-   the full Twisted installation. After installation change your
-   ``PYTHONPATH`` (in your ``~/.bash_profile``) to::
+2) Download and Install Twisted_ from source. There is an installer
+   for Mac OS X 10.5 which can be used if you use Mac OS X
+   10.5. Notice again that Mac OS X comes with a pre-installed version
+   of Twisted, but this is not the full Twisted installation. After
+   installation change your ``PYTHONPATH`` (in your
+   ``~/.bash_profile``) to::
 
-      PATH="/Library/Python/2.5/site-packages:${PATH}"
+      export PYTHONPATH="/Library/Python/2.5/site-packages:${PYTHONPATH}"
+      export PYTHONPATH=$PYTHONPATH:$HOME/opt/lib/python
 
 3) Optionally: download PyOpenSSL_ and tell us if it works!
 
-4) Download and install GMPY_ following the instructions in
+4) Download and install GMP_. You can preferably use the Macports or
+   Fink package utilities. If you download the other dependencies from
+   either Macports or Fink, they might depend on Python 2.4 which is
+   not preferable, you should use Python 2.5, unless you have good
+   reasons not to.
+
+5) Download and install GMPY_ following the instructions in
    ``gmpy-1.02.macosx.README.txt`` (under Downloads).
 
-5) Install VIFF from source (see below). If you prefer you can just
-   install it in site-packages, it makes no difference. For
-   developers, it is perhaps a better solution in to create a symbolic
-   link from the site-packages directory to the VIFF Python files
-   (``viff/viff/``), as otherwise you need to re-install VIFF each time
-   the project is modified.
+6) Install VIFF from source (see below). If you prefer you can just
+   install it in site-packages, it makes no difference.
 
-6) Proceed to `testing`_.
+   For developers, either add VIFF to the PYTHONPATH::
 
+      export PYTHONPATH=$PYTHONPATH:$HOME/path-to-viff/viff
+
+   or create a symbolic link from the site-packages directory to the
+   VIFF Python files (``viff/viff/``), as otherwise you need to
+   re-install VIFF each time the project is modified.
+
+7) Proceed to `testing`_.
 
 GNU/Linux
 ---------
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/todo.txt	Fri Mar 27 15:44:01 2009 +0100
@@ -0,0 +1,50 @@
+
+Planned Work on VIFF
+====================
+
+This document collects the bigger pieces of work we plan to do on
+VIFF --- pieces too big for the bug tracker.
+
+
+Active Security
+---------------
+
+The protocol implemented in :mod:`viff.active` is (believed to be)
+secure against active adversaries, but only as long as they don't
+actually try to cheat! In other words, the players will crash in bad
+ways if malformed data is received or too few shares are received.
+
+The following points should be addressed:
+
+* Error correction. The honest players must tolerate being sent wrong
+  shares or no shares at all from the corrupt players.
+
+  This is related to Issue4_, Issue29_, and Issue70_.
+
+  .. _Issue4: http://tracker.viff.dk/issue4
+  .. _Issue29: http://tracker.viff.dk/issue29
+  .. _Issue70: http://tracker.viff.dk/issue70
+
+* Byzantine agreement. After the preprocessing phase a Byzantime
+  agreement protocol should be run in order to determine if all honest
+  players are ready to continue.
+
+  At the moment an honest players simply aborts the protocol if it
+  detects any form of cheating --- the "idea" being that this will
+  make the other honest players crash too, thereby effectively halting
+  the protocol.
+
+Self Trust
+----------
+
+Implement an (actively) secure protocol with threshold ``t = n-1``
+based on the "triples approach" of Claudio Orlandi and Jesper Buus
+Nielsen. There will soon be a paper describing the protocol.
+
+Covert Adversaries
+------------------
+
+Implement an actively secure protocol for a covert adversary and
+threshold ``t < n/2``. The goal is to have almost the same complexity
+as for the passive case. Martin Geisler is working on a paper
+describing a solution.
--- a/setup.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/setup.py	Fri Mar 27 15:44:01 2009 +0100
@@ -4,7 +4,7 @@
 # For a local install into ~/opt, use:  python setup.py --home=~/opt
 # For more options, use:                python setup.py --help
 
-# Copyright 2007, 2008 VIFF Development Team.
+# Copyright 2007, 2008, 2009 VIFF Development Team.
 #
 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
 #
@@ -33,22 +33,22 @@
 class hg_sdist(sdist):
     def get_file_list(self):
         try:
-            # Attempt the import here so that users can run the other
-            # Distutils commands without needing Mercurial.
-            from mercurial import hg
-        except ImportError:
             from distutils.errors import DistutilsModuleError
-            raise DistutilsModuleError("could not import mercurial")
+            import subprocess
+            p = subprocess.Popen(['hg', 'manifest'], stdout=subprocess.PIPE)
+            exitcode = p.wait()
+            if exitcode != 0:
+                raise DistutilsModuleError("Mercurial exited with non-zero "
+                                           "exit code: %d" % exitcode)
+            files = p.stdout.read().strip().split('\n')
 
-        repo = hg.repository(None)
-        changeset = repo.changectx(None)
-        files = changeset.manifest().keys()
-
-        # Add the files *before* the normal manifest magic is done.
-        # That allows the manifest template to exclude some files
-        # tracked by hg and to include others.
-        self.filelist.extend(files)
-        sdist.get_file_list(self)
+            # Add the files *before* the normal manifest magic is
+            # done. That allows the manifest template to exclude some
+            # files tracked by hg and to include others.
+            self.filelist.extend(files)
+            sdist.get_file_list(self)
+        except OSError, e:
+            raise DistutilsModuleError("could not execute Mercurial: %s" % e)
 
 setup(name='viff',
       version=viff.__version__,
--- a/viff/aes.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/aes.py	Fri Mar 27 15:44:01 2009 +0100
@@ -58,14 +58,17 @@
 
 
 class AES:
-    """AES instantiation:
+    """AES instantiation.
 
-    >>> aes = AES(runtime, 192)
-    >>> cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
-    >>> key = [runtime.prss_share_random(GF256) for i in range(192/8)]
-    >>> ciphertext = aes.encrypt("abcdefghijklmnop", key)
-    >>> ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
-    >>> ciphertext = aes.encrypt(cleartext, key)
+    This class is used together with a :class:`viff.runtime.Runtime`
+    object::
+
+        aes = AES(runtime, 192)
+        cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
+        key = [runtime.prss_share_random(GF256) for i in range(192/8)]
+        ciphertext = aes.encrypt("abcdefghijklmnop", key)
+        ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
+        ciphertext = aes.encrypt(cleartext, key)
 
     In every case *ciphertext* will be a list of shares over GF256.
     """
--- a/viff/config.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/config.py	Fri Mar 27 15:44:01 2009 +0100
@@ -158,7 +158,7 @@
     return owner_id, players
 
 
-def generate_configs(n, t, addresses=None, prefix=None, skip_prss=False):
+def generate_configs(n, t, keysize=1024, addresses=None, prefix=None, skip_prss=False):
     """Generate player configurations.
 
     Generates *n* configuration objects with a threshold of *t*. The
@@ -194,8 +194,7 @@
         """Convert a dealer ID to a string."""
         return "Dealer " + str(dealer)
 
-    # TODO: remove hard-coded key size.
-    key_pairs = dict([(p, paillier.generate_keys(1024)) for p in players])
+    key_pairs = dict([(p, paillier.generate_keys(keysize)) for p in players])
 
     configs = {}
     for p in players:
--- a/viff/field.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/field.py	Fri Mar 27 15:44:01 2009 +0100
@@ -32,6 +32,7 @@
 
 >>> x = Zp(10)
 >>> y = Zp(15)
+>>> z = Zp(1)
 
 Addition and subtraction (with modulo reduction):
 
@@ -40,6 +41,15 @@
 >>> x - y
 {14}
 
+Bitwise xor for field elements:
+
+>>> z ^ z
+{0}
+>>> z ^ 0
+{1}
+>>> 1 ^ z
+{0}
+
 Exponentiation:
 
 >>> x**3
@@ -69,6 +79,7 @@
 
 
 from gmpy import mpz
+from math import log, ceil
 
 
 class FieldElement(object):
@@ -84,6 +95,25 @@
 
     __long__ = __int__
 
+    def split(self):
+        """Splits self into bit array LSB first.
+
+        >>> Zp = GF(29)
+        >>> Zp(3).split()
+        [{1}, {1}, {0}, {0}, {0}]
+        >>> Zp(28).split()
+        [{0}, {0}, {1}, {1}, {1}]
+        >>> GF256(8).split()
+        [[0], [0], [0], [1], [0], [0], [0], [0]]
+        """
+        length = int(ceil(log(self.modulus,2)))
+        result = [0] * length
+        temp = self.value
+        for i in range(length):
+            result[i] = self.field(temp % 2)
+            temp = temp // 2
+        return result
+
 #: Inversion table.
 #:
 #: Maps a value *x* to *x^-1*. See `_generate_tables`.
@@ -377,6 +407,20 @@
             """Subtraction (reflected argument version)."""
             return GFElement(other - self.value)
 
+        def __xor__(self, other):
+            """Xor for bitvalues."""
+            if not isinstance(other, (GFElement, int, long)):
+                return NotImplemented
+            try:
+                assert self.field is other.field, "Fields must be identical"
+                return GFElement(self.value ^ other.value)
+            except AttributeError:
+                return GFElement(self.value ^ other)
+
+        def __rxor__(self, other):
+            """Xor for bitvalues (reflected argument version)."""
+            return GFElement(other ^ self.value)
+
         def __mul__(self, other):
             """Multiplication."""
             if not isinstance(other, (GFElement, int, long)):
--- a/viff/passive.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/passive.py	Fri Mar 27 15:44:01 2009 +0100
@@ -214,7 +214,7 @@
     def pow(self, share, exponent):
         """Exponentation of a share to an integer by square-and-multiply."""
 
-        assert isinstance(exponent, int), "Exponent must be an integer"
+        assert isinstance(exponent, (int, long)), "Exponent must be an integer"
         assert exponent >= 0, "Exponent must be non-negative"
 
         if exponent == 0:
@@ -464,6 +464,32 @@
         unless there is only one inputter in which case the
         share is returned directly.
 
+        In code it is used like this::
+
+            a, b, c = runtime.shamir_share([1, 2, 3], Zp, x)
+
+        where ``Zp`` is a field and ``x`` is a Python integer holding
+        the input of each player (three inputs in total).
+
+        If only a subset of the players provide input it looks like
+        this::
+
+            if runtime.id == 1:
+                a = runtime.shamir_share([1], Zp, x)
+            else:
+                a = runtime.shamir_share([1], Zp)
+
+        Instead of branching when calling :meth:`shamir_share`, one
+        can give ``None`` as input::
+
+            if runtime.id == 1:
+                x = int(raw_input("Input x: "))
+            else:
+                x = None
+            a = runtime.shamir_share([1], Zp, x)
+
+        which might be practical in some cases.
+
         Communication cost: n elements transmitted.
         """
         assert number is None or self.id in inputters
--- a/viff/runtime.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/runtime.py	Fri Mar 27 15:44:01 2009 +0100
@@ -514,11 +514,11 @@
         All connections are closed and the runtime cannot be used
         again after this has been called.
         """
-        print "Synchronizing shutdown... ",
+        print "Synchronizing shutdown...",
 
         def close_connections(_):
             print "done."
-            print "Closing connections... ",
+            print "Closing connections...",
             results = [maybeDeferred(self.port.stopListening)]
             for protocol in self.protocols.itervalues():
                 results.append(protocol.lost_connection)
@@ -527,7 +527,7 @@
 
         def stop_reactor(_):
             print "done."
-            print "Stopping reactor... ",
+            print "Stopping reactor...",
             reactor.stop()
             print "done."
 
--- a/viff/test/rijndael.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/test/rijndael.py	Fri Mar 27 15:44:01 2009 +0100
@@ -36,109 +36,6 @@
 # [keysize][block_size]
 num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32: {16: 14, 24: 14, 32: 14}}
 
-A = [[1, 1, 1, 1, 1, 0, 0, 0],
-     [0, 1, 1, 1, 1, 1, 0, 0],
-     [0, 0, 1, 1, 1, 1, 1, 0],
-     [0, 0, 0, 1, 1, 1, 1, 1],
-     [1, 0, 0, 0, 1, 1, 1, 1],
-     [1, 1, 0, 0, 0, 1, 1, 1],
-     [1, 1, 1, 0, 0, 0, 1, 1],
-     [1, 1, 1, 1, 0, 0, 0, 1]]
-
-# produce log and alog tables, needed for multiplying in the
-# field GF(2^m) (generator = 3)
-alog = [1]
-for i in xrange(255):
-    j = (alog[-1] << 1) ^ alog[-1]
-    if j & 0x100 != 0:
-        j ^= 0x11B
-    alog.append(j)
-
-log = [0] * 256
-for i in xrange(1, 255):
-    log[alog[i]] = i
-
-# multiply two elements of GF(2^m)
-def mul(a, b):
-    if a == 0 or b == 0:
-        return 0
-    return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]
-
-# substitution box based on F^{-1}(x)
-box = [[0] * 8 for i in xrange(256)]
-box[1][7] = 1
-for i in xrange(2, 256):
-    j = alog[255 - log[i]]
-    for t in xrange(8):
-        box[i][t] = (j >> (7 - t)) & 0x01
-
-B = [0, 1, 1, 0, 0, 0, 1, 1]
-
-# affine transform:  box[i] <- B + A*box[i]
-cox = [[0] * 8 for i in xrange(256)]
-for i in xrange(256):
-    for t in xrange(8):
-        cox[i][t] = B[t]
-        for j in xrange(8):
-            cox[i][t] ^= A[t][j] * box[i][j]
-
-# S-boxes and inverse S-boxes
-S =  [0] * 256
-Si = [0] * 256
-for i in xrange(256):
-    S[i] = cox[i][0] << 7
-    for t in xrange(1, 8):
-        S[i] ^= cox[i][t] << (7-t)
-    Si[S[i] & 0xFF] = i
-
-# T-boxes
-G = [[2, 1, 1, 3],
-    [3, 2, 1, 1],
-    [1, 3, 2, 1],
-    [1, 1, 3, 2]]
-
-AA = [[0] * 8 for i in xrange(4)]
-
-for i in xrange(4):
-    for j in xrange(4):
-        AA[i][j] = G[i][j]
-        AA[i][i+4] = 1
-
-for i in xrange(4):
-    pivot = AA[i][i]
-    if pivot == 0:
-        t = i + 1
-        while AA[t][i] == 0 and t < 4:
-            t += 1
-            assert t != 4, 'G matrix must be invertible'
-            for j in xrange(8):
-                AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
-            pivot = AA[i][i]
-    for j in xrange(8):
-        if AA[i][j] != 0:
-            AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255]
-    for t in xrange(4):
-        if i != t:
-            for j in xrange(i+1, 8):
-                AA[t][j] ^= mul(AA[i][j], AA[t][i])
-            AA[t][i] = 0
-
-iG = [[0] * 4 for i in xrange(4)]
-
-for i in xrange(4):
-    for j in xrange(4):
-        iG[i][j] = AA[i][j + 4]
-
-def mul4(a, bs):
-    if a == 0:
-        return 0
-    r = 0
-    for b in bs:
-        r <<= 8
-        if b != 0:
-            r = r | mul(a, b)
-    return r
-
 T1 = []
 T2 = []
 T3 = []
@@ -152,48 +49,141 @@
 U3 = []
 U4 = []
 
-for t in xrange(256):
-    s = S[t]
-    T1.append(mul4(s, G[0]))
-    T2.append(mul4(s, G[1]))
-    T3.append(mul4(s, G[2]))
-    T4.append(mul4(s, G[3]))
+S =  [0] * 256
+Si = [0] * 256
 
-    s = Si[t]
-    T5.append(mul4(s, iG[0]))
-    T6.append(mul4(s, iG[1]))
-    T7.append(mul4(s, iG[2]))
-    T8.append(mul4(s, iG[3]))
+rcon = [1]
 
-    U1.append(mul4(t, iG[0]))
-    U2.append(mul4(t, iG[1]))
-    U3.append(mul4(t, iG[2]))
-    U4.append(mul4(t, iG[3]))
+def initialize():
+    """Called once at module import to initialize constants defined above."""
 
-# round constants
-rcon = [1]
-r = 1
-for t in xrange(1, 30):
-    r = mul(2, r)
-    rcon.append(r)
+    A = [[1, 1, 1, 1, 1, 0, 0, 0],
+         [0, 1, 1, 1, 1, 1, 0, 0],
+         [0, 0, 1, 1, 1, 1, 1, 0],
+         [0, 0, 0, 1, 1, 1, 1, 1],
+         [1, 0, 0, 0, 1, 1, 1, 1],
+         [1, 1, 0, 0, 0, 1, 1, 1],
+         [1, 1, 1, 0, 0, 0, 1, 1],
+         [1, 1, 1, 1, 0, 0, 0, 1]]
 
-del A
-del AA
-del pivot
-del B
-del G
-del box
-del log
-del alog
-del i
-del j
-del r
-del s
-del t
-del mul
-del mul4
-del cox
-del iG
+    # produce log and alog tables, needed for multiplying in the
+    # field GF(2^m) (generator = 3)
+    alog = [1]
+    for i in xrange(255):
+        j = (alog[-1] << 1) ^ alog[-1]
+        if j & 0x100 != 0:
+            j ^= 0x11B
+        alog.append(j)
+
+    log = [0] * 256
+    for i in xrange(1, 255):
+        log[alog[i]] = i
+
+    # multiply two elements of GF(2^m)
+    def mul(a, b):
+        if a == 0 or b == 0:
+            return 0
+        return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]
+
+    # substitution box based on F^{-1}(x)
+    box = [[0] * 8 for i in xrange(256)]
+    box[1][7] = 1
+    for i in xrange(2, 256):
+        j = alog[255 - log[i]]
+        for t in xrange(8):
+            box[i][t] = (j >> (7 - t)) & 0x01
+
+    B = [0, 1, 1, 0, 0, 0, 1, 1]
+
+    # affine transform:  box[i] <- B + A*box[i]
+    cox = [[0] * 8 for i in xrange(256)]
+    for i in xrange(256):
+        for t in xrange(8):
+            cox[i][t] = B[t]
+            for j in xrange(8):
+                cox[i][t] ^= A[t][j] * box[i][j]
+
+    # S-boxes and inverse S-boxes
+    for i in xrange(256):
+        S[i] = cox[i][0] << 7
+        for t in xrange(1, 8):
+            S[i] ^= cox[i][t] << (7-t)
+        Si[S[i] & 0xFF] = i
+
+    # T-boxes
+    G = [[2, 1, 1, 3],
+        [3, 2, 1, 1],
+        [1, 3, 2, 1],
+        [1, 1, 3, 2]]
+
+    AA = [[0] * 8 for i in xrange(4)]
+
+    for i in xrange(4):
+        for j in xrange(4):
+            AA[i][j] = G[i][j]
+            AA[i][i+4] = 1
+
+    for i in xrange(4):
+        pivot = AA[i][i]
+        if pivot == 0:
+            t = i + 1
+            while AA[t][i] == 0 and t < 4:
+                t += 1
+                assert t != 4, 'G matrix must be invertible'
+                for j in xrange(8):
+                    AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
+                pivot = AA[i][i]
+        for j in xrange(8):
+            if AA[i][j] != 0:
+                AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255]
+        for t in xrange(4):
+            if i != t:
+                for j in xrange(i+1, 8):
+                    AA[t][j] ^= mul(AA[i][j], AA[t][i])
+                AA[t][i] = 0
+
+    iG = [[0] * 4 for i in xrange(4)]
+
+    for i in xrange(4):
+        for j in xrange(4):
+            iG[i][j] = AA[i][j + 4]
+
+    def mul4(a, bs):
+        if a == 0:
+            return 0
+        r = 0
+        for b in bs:
+            r <<= 8
+            if b != 0:
+                r = r | mul(a, b)
+        return r
+
+    for t in xrange(256):
+        s = S[t]
+        T1.append(mul4(s, G[0]))
+        T2.append(mul4(s, G[1]))
+        T3.append(mul4(s, G[2]))
+        T4.append(mul4(s, G[3]))
+
+        s = Si[t]
+        T5.append(mul4(s, iG[0]))
+        T6.append(mul4(s, iG[1]))
+        T7.append(mul4(s, iG[2]))
+        T8.append(mul4(s, iG[3]))
+
+        U1.append(mul4(t, iG[0]))
+        U2.append(mul4(t, iG[1]))
+        U3.append(mul4(t, iG[2]))
+        U4.append(mul4(t, iG[3]))
+
+    # round constants
+    r = 1
+    for t in xrange(1, 30):
+        r = mul(2, r)
+        rcon.append(r)
+
+# initialize constants
+initialize()
 
 class rijndael:
     def __init__(self, key, block_size = 16):
--- a/viff/test/test_util.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/test/test_util.py	Fri Mar 27 15:44:01 2009 +0100
@@ -21,8 +21,7 @@
 
 from viff.util import deep_wait
 from viff.field import GF, GF256
-import viff.shamir
-import viff.prss
+from viff import shamir, prss
 
 from twisted.trial.unittest import TestCase
 from twisted.internet.defer import Deferred
@@ -36,7 +35,7 @@
 
     # Modules which will be reloaded with and without VIFF_FAKE set in
     # the environment.
-    _modules = [viff.shamir, viff.prss]
+    _modules = [shamir, prss]
 
     def setUp(self):
         self.field = GF(1031)
@@ -51,29 +50,27 @@
             reload(module)
 
     def test_shamir_share(self):
-        from viff.shamir import share
         secret = self.field(17)
-        shares = share(secret, 1, 3)
+        shares = shamir.share(secret, 1, 3)
         self.assertEquals(shares[0][1], secret)
         self.assertEquals(shares[1][1], secret)
         self.assertEquals(shares[2][1], secret)
 
     def test_shamir_recombine(self):
-        from viff.shamir import recombine
         shares = [(1, 1), None, None]
-        self.assertEquals(recombine(shares), 1)
+        self.assertEquals(shamir.recombine(shares), 1)
 
     def test_prss(self):
-        share = viff.prss.prss(None, None, self.field, None, None)
+        share = prss.prss(None, None, self.field, None, None)
         self.assertEquals(share, self.field(7))
 
     def test_prss_lsb(self):
-        (share, bit) = viff.prss.prss_lsb(None, None, self.field, None, None)
+        (share, bit) = prss.prss_lsb(None, None, self.field, None, None)
         self.assertEquals(share, self.field(7))
         self.assertEquals(bit, GF256(1))
 
     def test_prss_zero(self):
-        share = viff.prss.prss_zero(None, None, None, self.field, None, None)
+        share = prss.prss_zero(None, None, None, self.field, None, None)
         self.assertEquals(share, self.field(0))
 
 
--- a/viff/util.py	Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/util.py	Fri Mar 27 15:44:01 2009 +0100
@@ -388,6 +388,16 @@
                          for key, value in usage.iteritems()])
         _last_memory_usage = usage
 
+def if_then(cond, a, b):
+    """If then else operator works both for integers and for shares.
+
+    >>> if_then(0, 3, 6)
+    6
+    >>> if_then(1, 3, 6)
+    3
+    """
+    return b + cond * (a - b)
+
 if __name__ == "__main__":
     import doctest    #pragma NO COVER
     doctest.testmod() #pragma NO COVER