changeset 1006:68b96c32e06e

Renamed Runtime to PassiveRuntime. I also moved it from viff.runtime to a new viff.passive module.
author Martin Geisler <mg@daimi.au.dk>
date Wed, 29 Oct 2008 15:54:15 +0100
parents 8b46d76bdc75
children 00e057006d2a
files apps/benchmark.py apps/millionaires.py viff/active.py viff/comparison.py viff/passive.py viff/runtime.py viff/test/test_runtime_equal.py viff/test/util.py
diffstat 8 files changed, 447 insertions(+), 406 deletions(-) [+]
line wrap: on
line diff
--- a/apps/benchmark.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/apps/benchmark.py	Wed Oct 29 15:54:15 2008 +0100
@@ -62,8 +62,9 @@
 from twisted.internet import reactor
 
 from viff.field import GF, GF256
-from viff.runtime import Runtime, create_runtime, gather_shares, \
+from viff.runtime import BasicRuntime, create_runtime, gather_shares, \
     make_runtime_class
+from viff.passive import PassiveRuntime
 from viff.active import BasicActiveRuntime, \
     TriplesHyperinvertibleMatricesMixin, TriplesPRSSMixin
 from viff.comparison import ComparisonToft05Mixin, ComparisonToft07Mixin
@@ -122,7 +123,7 @@
                     operation=operations[0], parallel=True)
 
 # Add standard VIFF options.
-Runtime.add_options(parser)
+BasicRuntime.add_options(parser)
 
 (options, args) = parser.parse_args()
 
@@ -277,7 +278,7 @@
         else:
             mixins.append(TriplesHyperinvertibleMatricesMixin)
     else:
-        base_runtime_class = Runtime
+        base_runtime_class = PassiveRuntime
 
     if options.operation == "mul":
         operation = operator.mul
--- a/apps/millionaires.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/apps/millionaires.py	Wed Oct 29 15:54:15 2008 +0100
@@ -35,7 +35,7 @@
 from twisted.internet import reactor
 
 from viff.field import GF
-from viff.runtime import Runtime, create_runtime, gather_shares
+from viff.runtime import create_runtime, gather_shares
 from viff.comparison import Toft05Runtime
 from viff.config import load_config
 from viff.util import rand, find_prime
@@ -138,7 +138,7 @@
 
 # Parse command line arguments.
 parser = OptionParser()
-Runtime.add_options(parser)
+Toft05Runtime.add_options(parser)
 options, args = parser.parse_args()
 
 if len(args) == 0:
--- a/viff/active.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/viff/active.py	Wed Oct 29 15:54:15 2008 +0100
@@ -26,7 +26,8 @@
 from viff import shamir
 from viff.util import rand
 from viff.matrix import Matrix, hyper
-from viff.runtime import Runtime, Share, increment_pc, preprocess, gather_shares
+from viff.passive import PassiveRuntime
+from viff.runtime import Share, increment_pc, preprocess, gather_shares
 
 
 class BrachaBroadcastMixin:
@@ -443,7 +444,7 @@
         return 1, succeed([(a_t, b_t, c_t)])
 
 
-class BasicActiveRuntime(Runtime):
+class BasicActiveRuntime(PassiveRuntime):
     """Basic runtime secure against active adversaries.
 
     This class depends on either
--- a/viff/comparison.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/viff/comparison.py	Wed Oct 29 15:54:15 2008 +0100
@@ -25,7 +25,8 @@
 import math
 
 from viff.util import rand, profile
-from viff.runtime import Runtime, Share, gather_shares, increment_pc
+from viff.runtime import Share, gather_shares, increment_pc
+from viff.passive import PassiveRuntime
 from viff.active import ActiveRuntime
 from viff.field import GF256, FieldElement
 
@@ -141,7 +142,7 @@
         return (top, bot)
 
 
-class Toft05Runtime(ComparisonToft05Mixin, Runtime):
+class Toft05Runtime(ComparisonToft05Mixin, PassiveRuntime):
     """Default mix of :class:`ComparisonToft05Mixin` and
     :class:`Runtime <viff.runtime.Runtime>`."""
     pass
@@ -338,7 +339,7 @@
                                               field)
 
 
-class Toft07Runtime(ComparisonToft07Mixin, Runtime):
+class Toft07Runtime(ComparisonToft07Mixin, PassiveRuntime):
     """Default mix of :class:`ComparisonToft07Mixin` and
     :class:`Runtime <viff.runtime.Runtime>`.
     """
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/passive.py	Wed Oct 29 15:54:15 2008 +0100
@@ -0,0 +1,413 @@
+# Copyright 2008 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/>.
+
+"""Passively secure VIFF runtime."""
+
+from viff import shamir
+from viff.runtime import BasicRuntime, increment_pc, Share, ShareList, gather_shares
+from viff.prss import prss, prss_lsb, prss_zero
+from viff.field import GF256, FieldElement
+from viff.util import rand, profile
+
+
+class PassiveRuntime(BasicRuntime):
+    """The VIFF runtime.
+
+    The runtime is used for sharing values (:meth:`shamir_share` or
+    :meth:`prss_share`) into :class:`Share` object and opening such
+    shares (:meth:`open`) again. Calculations on shares is normally
+    done through overloaded arithmetic operations, but it is also
+    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
+    prefers.
+
+    Each player in the protocol uses a :class:`Runtime` object. To
+    create an instance and connect it correctly with the other
+    players, please use the :func:`create_runtime` function instead of
+    instantiating a Runtime directly. The :func:`create_runtime`
+    function will take care of setting up network connections and
+    return a :class:`Deferred` which triggers with the
+    :class:`Runtime` object when it is ready.
+    """
+
+    def __init__(self, player, threshold, options=None):
+        """Initialize runtime."""
+        BasicRuntime.__init__(self, player, threshold, options)
+
+    @increment_pc
+    def open(self, share, receivers=None, threshold=None):
+        """Open a secret sharing.
+
+        The *receivers* are the players that will eventually obtain
+        the opened result. The default is to let everybody know the
+        result. By default the :attr:`threshold` + 1 shares are
+        reconstructed, but *threshold* can be used to override this.
+
+        Communication cost: every player sends one share to each
+        receiving player.
+        """
+        assert isinstance(share, Share)
+        # all players receive result by default
+        if receivers is None:
+            receivers = self.players.keys()
+        if threshold is None:
+            threshold = self.threshold
+
+        def filter_good_shares(results):
+            # Filter results, which is a list of (success, share)
+            # pairs.
+            return [result[1] for result in results
+                    if result is not None and result[0]][:threshold+1]
+
+        def recombine(shares):
+            assert len(shares) > threshold
+            result = ShareList(shares, threshold+1)
+            result.addCallback(filter_good_shares)
+            result.addCallback(shamir.recombine)
+            return result
+
+        def exchange(share):
+            # Send share to all receivers.
+            for peer_id in receivers:
+                if peer_id != self.id:
+                    pc = tuple(self.program_counter)
+                    self.protocols[peer_id].sendShare(pc, share)
+            # Receive and recombine shares if this player is a receiver.
+            if self.id in receivers:
+                deferreds = []
+                for peer_id in self.players:
+                    if peer_id == self.id:
+                        d = Share(self, share.field, (share.field(peer_id), share))
+                    else:
+                        d = self._expect_share(peer_id, share.field)
+                        self.schedule_callback(d, lambda s, peer_id: (s.field(peer_id), s), peer_id)
+                    deferreds.append(d)
+                return recombine(deferreds)
+
+        result = share.clone()
+        self.schedule_callback(result, exchange)
+        if self.id in receivers:
+            return result
+
+    @profile
+    def add(self, share_a, share_b):
+        """Addition of shares.
+
+        Communication cost: none.
+        """
+        field = getattr(share_a, "field", getattr(share_b, "field", None))
+        if not isinstance(share_a, Share):
+            share_a = Share(self, field, share_a)
+        if not isinstance(share_b, Share):
+            share_b = Share(self, field, share_b)
+
+        result = gather_shares([share_a, share_b])
+        result.addCallback(lambda (a, b): a + b)
+        return result
+
+    def sub(self, share_a, share_b):
+        """Subtraction of shares.
+
+        Communication cost: none.
+        """
+        field = getattr(share_a, "field", getattr(share_b, "field", None))
+        if not isinstance(share_a, Share):
+            share_a = Share(self, field, share_a)
+        if not isinstance(share_b, Share):
+            share_b = Share(self, field, share_b)
+
+        result = gather_shares([share_a, share_b])
+        result.addCallback(lambda (a, b): a - b)
+        return result
+
+    @profile
+    @increment_pc
+    def mul(self, share_a, share_b):
+        """Multiplication of shares.
+
+        Communication cost: 1 Shamir sharing.
+        """
+        assert isinstance(share_a, Share) or isinstance(share_b, Share), \
+            "At least one of share_a and share_b must be a Share."
+
+        if not isinstance(share_a, Share):
+            # Then share_b must be a Share => local multiplication. We
+            # clone first to avoid changing share_b.
+            result = share_b.clone()
+            result.addCallback(lambda b: share_a * b)
+            return result
+        if not isinstance(share_b, Share):
+            # Likewise when share_b is a constant.
+            result = share_a.clone()
+            result.addCallback(lambda a: a * share_b)
+            return result
+
+        # At this point both share_a and share_b must be Share
+        # objects. So we wait on them, multiply and reshare.
+
+        def share_recombine(number):
+            shares = shamir.share(number, self.threshold, self.num_players)
+
+            exchanged_shares = []
+            for peer_id, share in shares:
+                d = self._exchange_shares(peer_id.value, share)
+                d.addCallback(lambda share, peer_id: (peer_id, share), peer_id)
+                exchanged_shares.append(d)
+
+            # Recombine the first 2t+1 shares.
+            result = gather_shares(exchanged_shares[:2*self.threshold+1])
+            result.addCallback(shamir.recombine)
+            return result
+
+        result = gather_shares([share_a, share_b])
+        result.addCallback(lambda (a, b): a * b)
+        self.schedule_callback(result, share_recombine)
+        return result
+
+    @increment_pc
+    def xor(self, share_a, share_b):
+        field = getattr(share_a, "field", getattr(share_b, "field", None))
+        if not isinstance(share_a, Share):
+            if not isinstance(share_a, FieldElement):
+                share_a = field(share_a)
+            share_a = Share(self, field, share_a)
+        if not isinstance(share_b, Share):
+            if not isinstance(share_b, FieldElement):
+                share_b = field(share_b)
+            share_b = Share(self, field, share_b)
+
+        if field is GF256:
+            return share_a + share_b
+        else:
+            return share_a + share_b - 2 * share_a * share_b
+
+    @increment_pc
+    def prss_share(self, inputters, field, element=None):
+        """Creates pseudo-random secret sharings.
+
+        This protocol creates a secret sharing for each player in the
+        subset of players specified in *inputters*. Each inputter
+        provides an integer. The result is a list of shares, one for
+        each inputter.
+
+        The protocol uses the pseudo-random secret sharing technique
+        described in the paper "Share Conversion, Pseudorandom
+        Secret-Sharing and Applications to Secure Computation" by
+        Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC
+        2005, LNCS 3378. `Download
+        <http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps>`__
+
+        Communication cost: Each inputter does one broadcast.
+        """
+        # Verifying parameters.
+        if element is None:
+            assert self.id not in inputters, "No element given."
+        else:
+            assert self.id in inputters, \
+                "Element given, but we are not sharing?"
+
+        n = self.num_players
+
+        # Key used for PRSS.
+        key = tuple(self.program_counter)
+
+        # The shares for which we have all the keys.
+        all_shares = []
+
+        # Shares we calculate from doing PRSS with the other players.
+        tmp_shares = {}
+
+        prfs = self.players[self.id].dealer_prfs(field.modulus)
+
+        # Compute and broadcast correction value.
+        if self.id in inputters:
+            for player in self.players:
+                share = prss(n, player, field, prfs[self.id], key)
+                all_shares.append((field(player), share))
+            shared = shamir.recombine(all_shares[:self.threshold+1])
+            correction = element - shared
+            # if this player is inputter then broadcast correction value
+            # TODO: more efficient broadcast?
+            pc = tuple(self.program_counter)
+            for peer_id in self.players:
+                if self.id != peer_id:
+                    self.protocols[peer_id].sendShare(pc, correction)
+
+        # Receive correction value from inputters and compute share.
+        result = []
+        for player in inputters:
+            tmp_shares[player] = prss(n, self.id, field, prfs[player], key)
+            if player == self.id:
+                d = Share(self, field, correction)
+            else:
+                d = self._expect_share(player, field)
+            d.addCallback(lambda c, s: s + c, tmp_shares[player])
+            result.append(d)
+
+        # Unpack a singleton list.
+        if len(result) == 1:
+            return result[0]
+        else:
+            return result
+
+    @increment_pc
+    def prss_share_random(self, field, binary=False):
+        """Generate shares of a uniformly random element from the field given.
+
+        If binary is True, a 0/1 element is generated. No player
+        learns the value of the element.
+
+        Communication cost: none if binary=False, 1 open otherwise.
+        """
+        if field is GF256 and binary:
+            modulus = 2
+        else:
+            modulus = field.modulus
+
+        # Key used for PRSS.
+        prss_key = tuple(self.program_counter)
+        prfs = self.players[self.id].prfs(modulus)
+        share = prss(self.num_players, self.id, field, prfs, prss_key)
+
+        if field is GF256 or not binary:
+            return Share(self, field, share)
+
+        # Open the square and compute a square-root
+        result = self.open(Share(self, field, share*share),
+                           threshold=2*self.threshold)
+
+        def finish(square, share, binary):
+            if square == 0:
+                # We were unlucky, try again...
+                return self.prss_share_random(field, binary)
+            else:
+                # We can finish the calculation
+                root = square.sqrt()
+                # When the root is computed, we divide the share and
+                # convert the resulting -1/1 share into a 0/1 share.
+                return Share(self, field, (share/root + 1) / 2)
+
+        self.schedule_callback(result, finish, share, binary)
+        return result
+
+    @increment_pc
+    def prss_share_zero(self, field):
+        """Generate shares of the zero element from the field given.
+
+        Communication cost: none.
+        """
+        # Key used for PRSS.
+        prss_key = tuple(self.program_counter)
+        prfs = self.players[self.id].prfs(field.modulus)
+        zero_share = prss_zero(self.num_players, self.threshold, self.id,
+                               field, prfs, prss_key)
+        return Share(self, field, zero_share)
+
+    @increment_pc
+    def prss_double_share(self, field):
+        """Make a double-sharing using PRSS.
+
+        The pair of shares will have degree t and 2t where t is the
+        default threshold for the runtime.
+        """
+        r_t = self.prss_share_random(field)
+        z_2t = self.prss_share_zero(field)
+        return (r_t, r_t + z_2t)
+
+    @increment_pc
+    def prss_share_bit_double(self, field):
+        """Share a random bit over *field* and GF256.
+
+        The protocol is described in "Efficient Conversion of
+        Secret-shared Values Between Different Fields" by Ivan Damgård
+        and Rune Thorbek available as `Cryptology ePrint Archive,
+        Report 2008/221 <http://eprint.iacr.org/2008/221>`__.
+        """
+        n = self.num_players
+        k = self.options.security_parameter
+        prfs = self.players[self.id].prfs(2**k)
+        prss_key = tuple(self.program_counter)
+
+        b_p = self.prss_share_random(field, binary=True)
+        r_p, r_lsb = prss_lsb(n, self.id, field, prfs, prss_key)
+
+        b = self.open(b_p + r_p)
+        # Extract least significant bit and change field to GF256.
+        b.addCallback(lambda i: GF256(i.value & 1))
+        b.field = GF256
+
+        # Use r_lsb to flip b as needed.
+        return (b_p, b ^ r_lsb)
+
+    @increment_pc
+    def prss_shamir_share_bit_double(self, field):
+        """Shamir share a random bit over *field* and GF256."""
+        n = self.num_players
+        k = self.options.security_parameter
+        prfs = self.players[self.id].prfs(2**k)
+        prss_key = tuple(self.program_counter)
+        inputters = range(1, self.num_players + 1)
+
+        ri = rand.randint(0, 2**k - 1)
+        ri_p = self.shamir_share(inputters, field, ri)
+        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
+
+        r_p = reduce(self.add, ri_p)
+        r_lsb = reduce(self.add, ri_lsb)
+
+        b_p = self.prss_share_random(field, binary=True)
+        b = self.open(b_p + r_p)
+        # Extract least significant bit and change field to GF256.
+        b.addCallback(lambda i: GF256(i.value & 1))
+        b.field = GF256
+
+        # Use r_lsb to flip b as needed.
+        return (b_p, b ^ r_lsb)
+
+    @increment_pc
+    def shamir_share(self, inputters, field, number=None, threshold=None):
+        """Secret share *number* over *field* using Shamir's method.
+
+        The number is shared using polynomial of degree *threshold*
+        (defaults to :attr:`threshold`). Returns a list of shares
+        unless there is only one inputter in which case the
+        share is returned directly.
+
+        Communication cost: n elements transmitted.
+        """
+        assert number is None or self.id in inputters
+        if threshold is None:
+            threshold = self.threshold
+
+        results = []
+        for peer_id in inputters:
+            if peer_id == self.id:
+                pc = tuple(self.program_counter)
+                shares = shamir.share(field(number), threshold,
+                                      self.num_players)
+                for other_id, share in shares:
+                    if other_id.value == self.id:
+                        results.append(Share(self, share.field, share))
+                    else:
+                        self.protocols[other_id.value].sendShare(pc, share)
+            else:
+                results.append(self._expect_share(peer_id, field))
+
+        # Unpack a singleton list.
+        if len(results) == 1:
+            return results[0]
+        else:
+            return results
--- a/viff/runtime.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/viff/runtime.py	Wed Oct 29 15:54:15 2008 +0100
@@ -671,399 +671,17 @@
             wait_list.append(ready)
         return DeferredList(wait_list)
 
-class Runtime(BasicRuntime):
-    """The VIFF runtime.
 
-    The runtime is used for sharing values (:meth:`shamir_share` or
-    :meth:`prss_share`) into :class:`Share` object and opening such
-    shares (:meth:`open`) again. Calculations on shares is normally
-    done through overloaded arithmetic operations, but it is also
-    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
-    prefers.
-
-    Each player in the protocol uses a :class:`Runtime` object. To
-    create an instance and connect it correctly with the other
-    players, please use the :func:`create_runtime` function instead of
-    instantiating a Runtime directly. The :func:`create_runtime`
-    function will take care of setting up network connections and
-    return a :class:`Deferred` which triggers with the
-    :class:`Runtime` object when it is ready.
+def make_runtime_class(runtime_class=None, mixins=None):
+    """Creates a new runtime class with *runtime_class* as a base
+    class mixing in the *mixins*. By default
+    :class:`viff.passive.PassiveRuntime` will be used.
     """
-
-    def __init__(self, player, threshold, options=None):
-        """Initialize runtime."""
-        BasicRuntime.__init__(self, player, threshold, options)
-
-    @increment_pc
-    def open(self, share, receivers=None, threshold=None):
-        """Open a secret sharing.
-
-        The *receivers* are the players that will eventually obtain
-        the opened result. The default is to let everybody know the
-        result. By default the :attr:`threshold` + 1 shares are
-        reconstructed, but *threshold* can be used to override this.
-
-        Communication cost: every player sends one share to each
-        receiving player.
-        """
-        assert isinstance(share, Share)
-        # all players receive result by default
-        if receivers is None:
-            receivers = self.players.keys()
-        if threshold is None:
-            threshold = self.threshold
-
-        def filter_good_shares(results):
-            # Filter results, which is a list of (success, share)
-            # pairs.
-            return [result[1] for result in results
-                    if result is not None and result[0]][:threshold+1]
-
-        def recombine(shares):
-            assert len(shares) > threshold
-            result = ShareList(shares, threshold+1)
-            result.addCallback(filter_good_shares)
-            result.addCallback(shamir.recombine)
-            return result
-
-        def exchange(share):
-            # Send share to all receivers.
-            for peer_id in receivers:
-                if peer_id != self.id:
-                    pc = tuple(self.program_counter)
-                    self.protocols[peer_id].sendShare(pc, share)
-            # Receive and recombine shares if this player is a receiver.
-            if self.id in receivers:
-                deferreds = []
-                for peer_id in self.players:
-                    if peer_id == self.id:
-                        d = Share(self, share.field, (share.field(peer_id), share))
-                    else:
-                        d = self._expect_share(peer_id, share.field)
-                        self.schedule_callback(d, lambda s, peer_id: (s.field(peer_id), s), peer_id)
-                    deferreds.append(d)
-                return recombine(deferreds)
-
-        result = share.clone()
-        self.schedule_callback(result, exchange)
-        if self.id in receivers:
-            return result
-
-    @profile
-    def add(self, share_a, share_b):
-        """Addition of shares.
-
-        Communication cost: none.
-        """
-        field = getattr(share_a, "field", getattr(share_b, "field", None))
-        if not isinstance(share_a, Share):
-            share_a = Share(self, field, share_a)
-        if not isinstance(share_b, Share):
-            share_b = Share(self, field, share_b)
-
-        result = gather_shares([share_a, share_b])
-        result.addCallback(lambda (a, b): a + b)
-        return result
-
-    def sub(self, share_a, share_b):
-        """Subtraction of shares.
-
-        Communication cost: none.
-        """
-        field = getattr(share_a, "field", getattr(share_b, "field", None))
-        if not isinstance(share_a, Share):
-            share_a = Share(self, field, share_a)
-        if not isinstance(share_b, Share):
-            share_b = Share(self, field, share_b)
-
-        result = gather_shares([share_a, share_b])
-        result.addCallback(lambda (a, b): a - b)
-        return result
-
-    @profile
-    @increment_pc
-    def mul(self, share_a, share_b):
-        """Multiplication of shares.
-
-        Communication cost: 1 Shamir sharing.
-        """
-        assert isinstance(share_a, Share) or isinstance(share_b, Share), \
-            "At least one of share_a and share_b must be a Share."
-
-        if not isinstance(share_a, Share):
-            # Then share_b must be a Share => local multiplication. We
-            # clone first to avoid changing share_b.
-            result = share_b.clone()
-            result.addCallback(lambda b: share_a * b)
-            return result
-        if not isinstance(share_b, Share):
-            # Likewise when share_b is a constant.
-            result = share_a.clone()
-            result.addCallback(lambda a: a * share_b)
-            return result
-
-        # At this point both share_a and share_b must be Share
-        # objects. So we wait on them, multiply and reshare.
-
-        def share_recombine(number):
-            shares = shamir.share(number, self.threshold, self.num_players)
-
-            exchanged_shares = []
-            for peer_id, share in shares:
-                d = self._exchange_shares(peer_id.value, share)
-                d.addCallback(lambda share, peer_id: (peer_id, share), peer_id)
-                exchanged_shares.append(d)
-
-            # Recombine the first 2t+1 shares.
-            result = gather_shares(exchanged_shares[:2*self.threshold+1])
-            result.addCallback(shamir.recombine)
-            return result
-
-        result = gather_shares([share_a, share_b])
-        result.addCallback(lambda (a, b): a * b)
-        self.schedule_callback(result, share_recombine)
-        return result
-
-    @increment_pc
-    def xor(self, share_a, share_b):
-        field = getattr(share_a, "field", getattr(share_b, "field", None))
-        if not isinstance(share_a, Share):
-            if not isinstance(share_a, FieldElement):
-                share_a = field(share_a)
-            share_a = Share(self, field, share_a)
-        if not isinstance(share_b, Share):
-            if not isinstance(share_b, FieldElement):
-                share_b = field(share_b)
-            share_b = Share(self, field, share_b)
-
-        if field is GF256:
-            return share_a + share_b
-        else:
-            return share_a + share_b - 2 * share_a * share_b
-
-    @increment_pc
-    def prss_share(self, inputters, field, element=None):
-        """Creates pseudo-random secret sharings.
-
-        This protocol creates a secret sharing for each player in the
-        subset of players specified in *inputters*. Each inputter
-        provides an integer. The result is a list of shares, one for
-        each inputter.
-
-        The protocol uses the pseudo-random secret sharing technique
-        described in the paper "Share Conversion, Pseudorandom
-        Secret-Sharing and Applications to Secure Computation" by
-        Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC
-        2005, LNCS 3378. `Download
-        <http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps>`__
-
-        Communication cost: Each inputter does one broadcast.
-        """
-        # Verifying parameters.
-        if element is None:
-            assert self.id not in inputters, "No element given."
-        else:
-            assert self.id in inputters, \
-                "Element given, but we are not sharing?"
-
-        n = self.num_players
-
-        # Key used for PRSS.
-        key = tuple(self.program_counter)
-
-        # The shares for which we have all the keys.
-        all_shares = []
-
-        # Shares we calculate from doing PRSS with the other players.
-        tmp_shares = {}
-
-        prfs = self.players[self.id].dealer_prfs(field.modulus)
-
-        # Compute and broadcast correction value.
-        if self.id in inputters:
-            for player in self.players:
-                share = prss(n, player, field, prfs[self.id], key)
-                all_shares.append((field(player), share))
-            shared = shamir.recombine(all_shares[:self.threshold+1])
-            correction = element - shared
-            # if this player is inputter then broadcast correction value
-            # TODO: more efficient broadcast?
-            pc = tuple(self.program_counter)
-            for peer_id in self.players:
-                if self.id != peer_id:
-                    self.protocols[peer_id].sendShare(pc, correction)
-
-        # Receive correction value from inputters and compute share.
-        result = []
-        for player in inputters:
-            tmp_shares[player] = prss(n, self.id, field, prfs[player], key)
-            if player == self.id:
-                d = Share(self, field, correction)
-            else:
-                d = self._expect_share(player, field)
-            d.addCallback(lambda c, s: s + c, tmp_shares[player])
-            result.append(d)
-
-        # Unpack a singleton list.
-        if len(result) == 1:
-            return result[0]
-        else:
-            return result
-
-    @increment_pc
-    def prss_share_random(self, field, binary=False):
-        """Generate shares of a uniformly random element from the field given.
-
-        If binary is True, a 0/1 element is generated. No player
-        learns the value of the element.
-
-        Communication cost: none if binary=False, 1 open otherwise.
-        """
-        if field is GF256 and binary:
-            modulus = 2
-        else:
-            modulus = field.modulus
-
-        # Key used for PRSS.
-        prss_key = tuple(self.program_counter)
-        prfs = self.players[self.id].prfs(modulus)
-        share = prss(self.num_players, self.id, field, prfs, prss_key)
-
-        if field is GF256 or not binary:
-            return Share(self, field, share)
-
-        # Open the square and compute a square-root
-        result = self.open(Share(self, field, share*share),
-                           threshold=2*self.threshold)
-
-        def finish(square, share, binary):
-            if square == 0:
-                # We were unlucky, try again...
-                return self.prss_share_random(field, binary)
-            else:
-                # We can finish the calculation
-                root = square.sqrt()
-                # When the root is computed, we divide the share and
-                # convert the resulting -1/1 share into a 0/1 share.
-                return Share(self, field, (share/root + 1) / 2)
-
-        self.schedule_callback(result, finish, share, binary)
-        return result
-
-    @increment_pc
-    def prss_share_zero(self, field):
-        """Generate shares of the zero element from the field given.
-
-        Communication cost: none.
-        """
-        # Key used for PRSS.
-        prss_key = tuple(self.program_counter)
-        prfs = self.players[self.id].prfs(field.modulus)
-        zero_share = prss_zero(self.num_players, self.threshold, self.id,
-                               field, prfs, prss_key)
-        return Share(self, field, zero_share)
-
-    @increment_pc
-    def prss_double_share(self, field):
-        """Make a double-sharing using PRSS.
-
-        The pair of shares will have degree t and 2t where t is the
-        default threshold for the runtime.
-        """
-        r_t = self.prss_share_random(field)
-        z_2t = self.prss_share_zero(field)
-        return (r_t, r_t + z_2t)
-
-    @increment_pc
-    def prss_share_bit_double(self, field):
-        """Share a random bit over *field* and GF256.
-
-        The protocol is described in "Efficient Conversion of
-        Secret-shared Values Between Different Fields" by Ivan Damgård
-        and Rune Thorbek available as `Cryptology ePrint Archive,
-        Report 2008/221 <http://eprint.iacr.org/2008/221>`__.
-        """
-        n = self.num_players
-        k = self.options.security_parameter
-        prfs = self.players[self.id].prfs(2**k)
-        prss_key = tuple(self.program_counter)
-
-        b_p = self.prss_share_random(field, binary=True)
-        r_p, r_lsb = prss_lsb(n, self.id, field, prfs, prss_key)
-
-        b = self.open(b_p + r_p)
-        # Extract least significant bit and change field to GF256.
-        b.addCallback(lambda i: GF256(i.value & 1))
-        b.field = GF256
-
-        # Use r_lsb to flip b as needed.
-        return (b_p, b ^ r_lsb)
-
-    @increment_pc
-    def prss_shamir_share_bit_double(self, field):
-        """Shamir share a random bit over *field* and GF256."""
-        n = self.num_players
-        k = self.options.security_parameter
-        prfs = self.players[self.id].prfs(2**k)
-        prss_key = tuple(self.program_counter)
-        inputters = range(1, self.num_players + 1)
-
-        ri = rand.randint(0, 2**k - 1)
-        ri_p = self.shamir_share(inputters, field, ri)
-        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
-
-        r_p = reduce(self.add, ri_p)
-        r_lsb = reduce(self.add, ri_lsb)
-
-        b_p = self.prss_share_random(field, binary=True)
-        b = self.open(b_p + r_p)
-        # Extract least significant bit and change field to GF256.
-        b.addCallback(lambda i: GF256(i.value & 1))
-        b.field = GF256
-
-        # Use r_lsb to flip b as needed.
-        return (b_p, b ^ r_lsb)
-
-    @increment_pc
-    def shamir_share(self, inputters, field, number=None, threshold=None):
-        """Secret share *number* over *field* using Shamir's method.
-
-        The number is shared using polynomial of degree *threshold*
-        (defaults to :attr:`threshold`). Returns a list of shares
-        unless there is only one inputter in which case the
-        share is returned directly.
-
-        Communication cost: n elements transmitted.
-        """
-        assert number is None or self.id in inputters
-        if threshold is None:
-            threshold = self.threshold
-
-        results = []
-        for peer_id in inputters:
-            if peer_id == self.id:
-                pc = tuple(self.program_counter)
-                shares = shamir.share(field(number), threshold,
-                                      self.num_players)
-                for other_id, share in shares:
-                    if other_id.value == self.id:
-                        results.append(Share(self, share.field, share))
-                    else:
-                        self.protocols[other_id.value].sendShare(pc, share)
-            else:
-                results.append(self._expect_share(peer_id, field))
-
-        # Unpack a singleton list.
-        if len(results) == 1:
-            return results[0]
-        else:
-            return results
-
-
-def make_runtime_class(runtime_class=Runtime, mixins=None):
-    """Creates a new runtime class with *runtime_class* as a base
-    class mixing in the *mixins*.
-    """
+    if runtime_class is None:
+        # The import is put here because of circular depencencies
+        # between viff.runtime and viff.passive.
+        from viff.passive import PassiveRuntime
+        runtime_class = PassiveRuntime
     if mixins is None:
         return runtime_class
     else:
@@ -1073,7 +691,7 @@
         bases = (runtime_class,) + tuple(mixins) + (object,)
         return type("ExtendedRuntime", bases, {})
 
-def create_runtime(id, players, threshold, options=None, runtime_class=Runtime):
+def create_runtime(id, players, threshold, options=None, runtime_class=None):
     """Create a :class:`Runtime` and connect to the other players.
 
     This function should be used in normal programs instead of
@@ -1104,6 +722,12 @@
     Please see the example applications for more examples.
 
     """
+    if runtime_class is None:
+        # The import is put here because of circular depencencies
+        # between viff.runtime and viff.passive.
+        from viff.passive import PassiveRuntime
+        runtime_class = PassiveRuntime
+
     if options and options.profile:
         # To collect profiling information we monkey patch reactor.run
         # to do the collecting. It would be nicer to simply start the
--- a/viff/test/test_runtime_equal.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/viff/test/test_runtime_equal.py	Wed Oct 29 15:54:15 2008 +0100
@@ -22,13 +22,13 @@
 
 from viff.equality import ProbabilisticEqualityMixin
 from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
-from viff.runtime import Runtime
+from viff.passive import PassiveRuntime
 
 #: Declare doctests for Trial.
 __doctests__ = ['viff.equality']
 
 
-class EqualRuntime(Runtime, ProbabilisticEqualityMixin):
+class EqualRuntime(PassiveRuntime, ProbabilisticEqualityMixin):
     """A runtime with the equality mixin."""
     pass
 
--- a/viff/test/util.py	Mon Oct 27 09:38:46 2008 +0100
+++ b/viff/test/util.py	Wed Oct 29 15:54:15 2008 +0100
@@ -20,7 +20,8 @@
 from twisted.internet.defer import Deferred, gatherResults, maybeDeferred
 from twisted.trial.unittest import TestCase
 
-from viff.runtime import Runtime, Share, ShareExchanger, ShareExchangerFactory
+from viff.passive import PassiveRuntime
+from viff.runtime import Share, ShareExchanger, ShareExchangerFactory
 from viff.field import GF
 from viff.config import generate_configs, load_config
 from viff.util import rand
@@ -91,7 +92,7 @@
     #: Shamir sharing threshold.
     threshold = 1
     #: Default Runtime class to instantiate.
-    runtime_class = Runtime
+    runtime_class = PassiveRuntime
 
     #: A dictionary mapping player ids to pseudorandom generators.
     #: