changeset 1520:d5e0360a3566

BeDOZa: Moved bedoza related files to their own package.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Fri, 23 Jul 2010 13:17:48 +0200
parents d7840af5cbf8
children 9dcbcf1a3a6d
files viff/bedoza.py viff/bedoza/__init__.py viff/bedoza/bedoza.py viff/bedoza/bedoza_triple.py viff/bedoza/keylist.py viff/bedoza/maclist.py viff/bedoza_triple.py viff/test/test_bedoza_runtime.py viff/test/test_bedoza_triple.py
diffstat 9 files changed, 1176 insertions(+), 1118 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza.py	Fri Jul 23 11:18:04 2010 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,561 +0,0 @@
-# Copyright 2010 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/>.
-
-"""Full threshold actively secure runtime."""
-
-from twisted.internet.defer import Deferred, gatherResults, succeed
-
-from viff.util import rand
-from viff.runtime import Share, ShareList, gather_shares
-from viff.field import FieldElement
-from viff.constants import TEXT
-from viff.simplearithmetic import SimpleArithmeticRuntime
-
-from hash_broadcast import HashBroadcastMixin
-
-class BeDOZaException(Exception):
-    pass
-
-class BeDOZaShareContents(object):
-
-    def __init__(self, value, keyList, macs):
-        self.value = value
-        self.keyList = keyList
-        self.macs = macs
-
-    def get_value(self):
-        return self.value
-
-    def get_keys(self):
-        return self.keyList
-
-    def get_macs(self):
-        return self.macs
-
-    def get_mac(self, inx):
-        return self.macs.get_mac(inx)
-
-    def __add__(self, other):
-        zi = self.value + other.value
-        zks = self.keyList + other.keyList
-        zms = self.macs + other.macs
-        return BeDOZaShareContents(zi, zks, zms)
-
-    def __sub__(self, other):
-        zi = self.value - other.value
-        zks = self.keyList - other.keyList
-        zms = self.macs - other.macs
-        return BeDOZaShareContents(zi, zks, zms)
-
-    def add_public(self, c, my_id):
-        if my_id == 1:
-            self.value = self.value + c
-        self.keyList.set_key(0, self.keyList.get_key(0) - self.keyList.alpha * c)
-        return self
-    
-    def sub_public(self, c, my_id):
-        if my_id == 1:
-            self.value = self.value - c
-        self.keyList.set_key(0, self.keyList.get_key(0) + self.keyList.alpha * c)
-        return self
-
-    def cmul(self, c):
-        zi = c * self.value
-        zks = self.keyList.cmul(c)
-        zms = self.macs.cmul(c)
-        return BeDOZaShareContents(zi, zks, zms)
-
-    def __str__(self):
-        return "(%s, %s, %s)" % (str(self.value), str(self.keyList), str(self.macs))
-    
-class BeDOZaShare(Share):
-    """A share in the BeDOZa runtime.
-
-    A share in the BeDOZa runtime is a pair ``(x_i, authentication_codes)`` of:
-
-    - A share of a number, ``x_i``
-    - A list of authentication_codes, ``authentication_codes``
-
-    The :class:`Runtime` operates on shares, represented by this class.
-    Shares are asynchronous in the sense that they promise to attain a
-    value at some point in the future.
-
-    Shares overload the arithmetic operations so that ``x = a + b``
-    will create a new share *x*, which will eventually contain the
-    sum of *a* and *b*. Each share is associated with a
-    :class:`Runtime` and the arithmetic operations simply call back to
-    that runtime.
-    """
-
-    def __init__(self, runtime, field, value=None, keyList=None, authentication_codes=None):
-        if value == None and keyList == None and authentication_codes == None:
-            Share.__init__(self, runtime, field)
-        else:
-            Share.__init__(self, runtime, field, BeDOZaShareContents(value, keyList, authentication_codes))
-        
-
-class BeDOZaKeyList(object):
-    """A list of keys, one for each player.
-
-    We assume that the key for player *i* is stored in
-    location *i - 1* in the *keys* list given as argument to the constructor.
-    """
-
-    def __init__(self, alpha, keys):
-        self.alpha = alpha
-        self.keys = keys
-
-    def get_key(self, player_id):
-        return self.keys[player_id]
-
-    def set_key(self, player_id, v):
-        self.keys[player_id] = v
-
-    def cmul(self, c):
-        return BeDOZaKeyList(self.alpha, map(lambda k: c * k, self.keys))
-
-    def __add__(self, other):
-        """Addition."""
-        assert self.alpha == other.alpha
-        keys = []
-        for k1, k2 in zip(self.keys, other.keys):
-            keys.append(k1 + k2)
-        return BeDOZaKeyList(self.alpha, keys)
-
-    def __sub__(self, other):
-        """Subtraction."""
-        assert self.alpha == other.alpha
-        keys = []
-        for k1, k2 in zip(self.keys, other.keys):
-            keys.append(k1 - k2)
-        return BeDOZaKeyList(self.alpha, keys)
-
-    def __eq__(self, other):
-        return self.alpha == other.alpha and self.keys == other.keys
-
-    def __str__(self):
-        return "(%s, %s)" % (self.alpha, str(self.keys))
-
-    def __repr__(self):
-        return str(self)
-    
-class BeDOZaMACList(object):
-
-    def __init__(self, macs):
-        self.macs = macs
-
-    def get_macs(self):
-        return self.macs
-
-    def get_mac(self, inx):
-        return self.macs[inx]
-
-    def cmul(self, c):
-        return BeDOZaMACList(map(lambda m: c * m, self.macs))
-        
-    def __add__(self, other):
-        """Addition."""
-        macs = []
-        for c1, c2 in zip(self.macs, other.macs):
-            macs.append(c1 + c2)
-        return BeDOZaMACList(macs)
-
-    def __sub__(self, other):
-        """Subtraction."""
-        macs = []
-        for c1, c2 in zip(self.macs, other.macs):
-            macs.append(c1 - c2)
-        return BeDOZaMACList(macs)
-
-    def __eq__(self, other):
-        return self.macs == other.macs
-
-    def __str__(self):
-        return str(self.macs)
-
-    def __repr__(self):
-        return str(self)
-    
-class RandomShareGenerator:
-    """ TODO: This is a dummy implementation, and should be replaced with proper code."""
-    
-    def generate_random_shares(self, field, number_of_shares):
-        self.init_keys(field)
-        shares = []
-        for i in xrange(0, number_of_shares):
-            v = field(self.id)
-            shares.append(self.generate_share(field, v))
-        return shares
-
-    def generate_share(self, field, value):
-        my_keys = self.generate_keys(field)
-        macs = self.generate_auth_codes(self.id, value)
-        return BeDOZaShare(self, field, value, my_keys, macs)
-
-    def generate_auth_codes(self, playerId, value):
-        keys = map(lambda (alpha, akeys): (alpha, akeys[playerId - 1]), self.keys.values())
-        macs = self.authentication_codes(keys, value)
-        return macs
-
-    def authentication_codes(self, keys, v):
-        macs = []
-        for alpha, beta in keys:
-            macs.append(alpha * v + beta)
-        return BeDOZaMACList(macs)
-
-    def generate_keys(self, field):
-        alpha, betas = self.get_keys()
-        return BeDOZaKeyList(alpha, betas)
-
-    def init_keys(self, field):
-
-        self.keys = {}
-        for player_id in self.players:
-            betas = [field(56387295767672113),
-                     field(89238458945400961),
-                     field(12340004554789025),
-                     field(12907853897457058),
-                     field(90457903592570134),
-                     field(56256262346343232),
-                     field(23897437894556562),
-                     field(90297849575975574)]
-            self.keys[player_id] = (field(player_id), betas)
-
-    def get_keys(self):   
-        return self.keys[self.id]
-
-class BeDOZaMixin(HashBroadcastMixin, RandomShareGenerator):
- 
-    def MAC(self, alpha, beta, v):
-        return alpha * v + beta
-
-    def random_share(self, field):
-        """Retrieve a previously generated random share in the field, field.
-
-        If no more shares are left, generate self.random_share_number new ones.
-        """
-        if len(self.random_shares) == 0:
-            self.random_shares = self.generate_random_shares(field, self.random_share_number)
-
-        return self.random_shares.pop()
-
-    def output(self, share, receivers=None):
-        return self.open(share, receivers)
-
-    def open_multiple_values(self, shares, receivers=None):
-        """Share reconstruction of a list of shares."""
-        assert shares
-        # all players receive result by default
-        if receivers is None:
-            receivers = self.players.keys()
-
-        field = shares[0].field
-
-        self.increment_pc()
-
-        def recombine_value(player_shares_codes, keyLists, num_shares):
-            def check(ls, x, isOK):
-                true_str = str(True)
-                if reduce(lambda x, y: true_str == y, ls):
-                    return x
-                else:
-                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
-
-            n = len(self.players)
-            alpha = keyLists[0].alpha
-
-            values = num_shares * [0]
-            isOK = num_shares * [True]
-            for iny in xrange(num_shares):
-                keyList = keyLists[iny]
-                for inx, xs in enumerate(player_shares_codes):
-                    xi, mi = xs[iny]
-                    beta = keyList.get_key(inx)
-                    values[iny] += xi
-                    mi_prime = self.MAC(alpha, beta, xi)
-                    isOK[iny] = isOK[iny] and mi == mi_prime
-
-            isOK = reduce(lambda x, y: True == y, isOK)
-            ds = self.broadcast(self.players.keys(), self.players.keys(),
-                                str(isOK))
-            ds = gatherResults(ds)
-            ds.addCallbacks(check, self.error_handler, callbackArgs=(values, isOK))
-            return ds
-        
-        def exchange(ls, receivers):
-            # Send share to all receivers.
-            pc = tuple(self.program_counter)
-            keyLists = []
-            for other_id in receivers:
-                message_string = ""
-                for inx, beDOZaContents in enumerate(ls):
-                    keyLists.append(beDOZaContents.get_keys())
-                    message_string += "%s:%s;" % \
-                           (beDOZaContents.get_value().value, beDOZaContents.get_mac(other_id - 1).value)
-                self.protocols[other_id].sendData(pc, TEXT, message_string)
-
-            if self.id in receivers:
-                def deserialize(s):
-                    def field_long(x):
-                        return field(long(x))
-                    xs = s[0:-1].split(';')
-                    ys = [x.split(':') for x in xs]
-                    return [map(field_long, xs) for xs in ys]
-                num_players = len(self.players.keys())
-                values = num_players * [None]
-                for inx, other_id in enumerate(self.players.keys()):
-                    d = Deferred()
-                    d.addCallbacks(deserialize, self.error_handler)
-                    self._expect_data(other_id, TEXT, d)
-                    values[inx] = d
-                result = gatherResults(values)
-                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(keyLists, len(shares)))
-                return result
-
-        result = gather_shares(shares)
-        self.schedule_callback(result, exchange, receivers)
-        result.addErrback(self.error_handler)
-
-        # do actual communication
-        self.activate_reactor()
-
-        if self.id in receivers:
-            return result
-
-    def open_two_values(self, share_a, share_b, receivers=None):
-        """Share reconstruction of a list of shares."""
-        assert isinstance(share_a, Share)
-        assert isinstance(share_b, Share)
-        # all players receive result by default
-        if receivers is None:
-            receivers = self.players.keys()
-
-        field = share_a.field
-
-        self.increment_pc()
-
-        def recombine_value(shares_codes, keyList_a, keyList_b):
-            def check(ls, a, b, isOK):
-                true_str = str(True)
-                if reduce(lambda x, y: true_str == y, ls):
-                    return a, b
-                else:
-                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
-
-            n = len(self.players)
-            alpha_a = keyList_a.alpha
-            alpha_b = keyList_b.alpha
-
-            a = 0
-            b = 0
-            isOK = True
-            for inx in xrange(0, n):
-                ai = shares_codes[inx]
-                bi = shares_codes[2*n + inx]
-                mi_a = shares_codes[n + inx]
-                mi_b = shares_codes[3*n + inx]
-                beta_a = keyList_a.get_key(inx)
-                beta_b = keyList_b.get_key(inx)
-                a += ai
-                b += bi
-                mi_prime = self.MAC(alpha_a, beta_a, ai)
-                isOK = isOK and mi_a == mi_prime
-                mi_prime = self.MAC(alpha_b, beta_b, bi)
-                isOK = isOK and mi_b == mi_prime
-                
-            ds = self.broadcast(self.players.keys(), self.players.keys(),
-                                str(isOK))
-            ds = gatherResults(ds)
-            ds.addCallbacks(check, self.error_handler, callbackArgs=(a, b, isOK))
-            return ds
-        
-        def exchange((a, b), receivers):
-            # Send share to all receivers.
-            pc = tuple(self.program_counter)
-            for other_id in receivers:
-                self.protocols[other_id].sendShare(pc, a.get_value())
-                self.protocols[other_id].sendShare(pc, a.get_mac(other_id - 1))
-                self.protocols[other_id].sendShare(pc, b.get_value())
-                self.protocols[other_id].sendShare(pc, b.get_mac(other_id - 1))
-                
-            if self.id in receivers:
-                num_players = len(self.players.keys())
-                values_a = num_players * [None]
-                codes_a = num_players * [None]
-                values_b = num_players * [None]
-                codes_b = num_players * [None]
-                for inx, other_id in enumerate(self.players.keys()):
-                    values_a[inx] =  self._expect_share(other_id, field)
-                    codes_a[inx] = self._expect_share(other_id, field)
-                    values_b[inx] =  self._expect_share(other_id, field)
-                    codes_b[inx] = self._expect_share(other_id, field)
-                result = gatherResults(values_a + codes_a + values_b + codes_b)
-                self.schedule_callback(result, recombine_value, a.get_keys(), b.get_keys())
-                return result
-
-        result = gather_shares([share_a, share_b])
-        self.schedule_callback(result, exchange, receivers)
-        result.addErrback(self.error_handler)
-
-        # do actual communication
-        self.activate_reactor()
-
-        if self.id in receivers:
-            return result
-
-    def open(self, share, receivers=None):
-        """Share reconstruction."""
-        assert isinstance(share, Share)
-        # all players receive result by default
-        if receivers is None:
-            receivers = self.players.keys()
-
-        field = share.field
-
-        self.increment_pc()
-
-        def recombine_value(shares_codes, keyList):
-            isOK = True
-            n = len(self.players)
-            alpha = keyList.alpha
-            x = 0
-            for inx in xrange(0, n):
-                xi = shares_codes[inx]
-                mi = shares_codes[n + inx]
-                beta = keyList.get_key(inx)
-                x += xi
-                mi_prime = self.MAC(alpha, beta, xi)
-                isOK = isOK and mi == mi_prime
-            def check(ls, x, isOK):
-                true_str = str(True)
-                if reduce(lambda x, y: true_str == y, ls):
-                    return x
-                else:
-                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
-                
-            ds = self.broadcast(self.players.keys(), self.players.keys(),
-                                str(isOK))
-            ds = gatherResults(ds)
-            ds.addCallbacks(check, self.error_handler, callbackArgs=(x,isOK))
-            return ds
-
-        def exchange(shareContent, receivers):
-            # Send share to all receivers.
-            pc = tuple(self.program_counter)
-            for other_id in receivers:
-                self.protocols[other_id].sendShare(pc, shareContent.get_value())
-                self.protocols[other_id].sendShare(pc, shareContent.get_mac(other_id - 1))
-            if self.id in receivers:
-                num_players = len(self.players.keys())
-                values = num_players * [None]
-                codes = num_players * [None]
-                for inx, other_id in enumerate(self.players.keys()):
-                    values[inx] =  self._expect_share(other_id, field)
-                    codes[inx] = self._expect_share(other_id, field)
-                result = gatherResults(values + codes)
-                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(shareContent.get_keys(),))
-                return result
-
-        result = share.clone()
-        self.schedule_callback(result, exchange, receivers)
-        result.addErrback(self.error_handler)
-
-        # do actual communication
-        self.activate_reactor()
-
-        if self.id in receivers:
-            return result
-
-    def _plus_public(self, x, c, field):
-        x = x.add_public(c, self.id)
-        return BeDOZaShare(self, field, x.get_value(), x.get_keys(), x.get_macs())
-
-    def _plus(self, (x, y), field):
-        """Addition of share-contents *x* and *y*."""
-        return x + y
-
-    def _minus_public_right(self, x, c, field):
-        z = self._minus_public_right_without_share(x, c, field)
-        return BeDOZaShare(self, field, z.get_value(), z.get_keys(), z.get_macs())
-
-    def _minus_public_right_without_share(self, x, c, field):
-        return x.sub_public(c, self.id)
-
-    def _wrap_in_share(self, shareContents, field):
-        return BeDOZaShare(self, field,
-                           shareContents.get_value(),
-                           shareContents.get_keys(),
-                           shareContents.get_macs())
-
-    def _minus_public_left(self, x, c, field):
-        y = self._constant_multiply(x, field(-1))
-        return self._plus_public(y, c, field)
-    
-    def _minus(self, (x, y), field):
-        """Subtraction of share-tuples *x* and *y*."""
-        return x - y
-
-    def _constant_multiply(self, x, c):
-        """Multiplication of a share-tuple with a constant c."""
-        assert(isinstance(c, FieldElement))
-        return x.cmul(c)
-
-    def _get_triple(self, field):
-        """ TODO: This is a dummy implementation, and should be replaced with proper code."""
-        self.init_keys(field)
-        a, b, c = 0, 0, 0
-        share_a = field(2)
-        share_b = field(4)
-        n = len(self.players)
-        share_c = n * share_a * share_b
-        for playerid in self.players.keys():
-            if self.id == playerid:
-                triple_a = self.generate_share(field, share_a)
-                a += share_a.value
-                triple_b = self.generate_share(field, share_b)
-                b += share_b.value
-                triple_c = self.generate_share(field, share_c)
-                c += share_c.value
-        return [triple_a, triple_b, triple_c], False
-
-
-class BeDOZaRuntime(BeDOZaMixin, SimpleArithmeticRuntime):
-    """The BeDOZa runtime.
-
-    The runtime is used for sharing values (:meth:`secret_share` or
-    :meth:`shift`) into :class:`BeDOZaShare` 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:`~viff.runtime.Runtime`
-    object. To create an instance and connect it correctly with the
-    other players, please use the :func:`~viff.runtime.create_runtime`
-    function instead of instantiating a Runtime directly. The
-    :func:`~viff.runtime.create_runtime` function will take care of
-    setting up network connections and return a :class:`Deferred`
-    which triggers with the :class:`~viff.runtime.Runtime` object when
-    it is ready.
-    """
-
-    def __init__(self, player, threshold=None, options=None):
-        """Initialize runtime."""
-        SimpleArithmeticRuntime.__init__(self, player, threshold, options)
-        self.threshold = self.num_players - 1
-        self.random_share_number = 100
-        self.random_shares = []
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/__init__.py	Fri Jul 23 13:17:48 2010 +0200
@@ -0,0 +1,16 @@
+# Copyright 2010 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/>.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/bedoza.py	Fri Jul 23 13:17:48 2010 +0200
@@ -0,0 +1,481 @@
+# Copyright 2010 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/>.
+
+"""Full threshold actively secure runtime."""
+
+from twisted.internet.defer import Deferred, gatherResults, succeed
+
+from viff.util import rand
+from viff.runtime import Share, ShareList, gather_shares
+from viff.field import FieldElement
+from viff.constants import TEXT
+from viff.simplearithmetic import SimpleArithmeticRuntime
+
+from viff.hash_broadcast import HashBroadcastMixin
+
+from viff.bedoza.keylist import BeDOZaKeyList
+from viff.bedoza.maclist import BeDOZaMACList
+
+class BeDOZaException(Exception):
+    pass
+
+class BeDOZaShareContents(object):
+
+    def __init__(self, value, keyList, macs):
+        self.value = value
+        self.keyList = keyList
+        self.macs = macs
+
+    def get_value(self):
+        return self.value
+
+    def get_keys(self):
+        return self.keyList
+
+    def get_macs(self):
+        return self.macs
+
+    def get_mac(self, inx):
+        return self.macs.get_mac(inx)
+
+    def __add__(self, other):
+        zi = self.value + other.value
+        zks = self.keyList + other.keyList
+        zms = self.macs + other.macs
+        return BeDOZaShareContents(zi, zks, zms)
+
+    def __sub__(self, other):
+        zi = self.value - other.value
+        zks = self.keyList - other.keyList
+        zms = self.macs - other.macs
+        return BeDOZaShareContents(zi, zks, zms)
+
+    def add_public(self, c, my_id):
+        if my_id == 1:
+            self.value = self.value + c
+        self.keyList.set_key(0, self.keyList.get_key(0) - self.keyList.alpha * c)
+        return self
+    
+    def sub_public(self, c, my_id):
+        if my_id == 1:
+            self.value = self.value - c
+        self.keyList.set_key(0, self.keyList.get_key(0) + self.keyList.alpha * c)
+        return self
+
+    def cmul(self, c):
+        zi = c * self.value
+        zks = self.keyList.cmul(c)
+        zms = self.macs.cmul(c)
+        return BeDOZaShareContents(zi, zks, zms)
+
+    def __str__(self):
+        return "(%s, %s, %s)" % (str(self.value), str(self.keyList), str(self.macs))
+    
+class BeDOZaShare(Share):
+    """A share in the BeDOZa runtime.
+
+    A share in the BeDOZa runtime is a pair ``(x_i, authentication_codes)`` of:
+
+    - A share of a number, ``x_i``
+    - A list of authentication_codes, ``authentication_codes``
+
+    The :class:`Runtime` operates on shares, represented by this class.
+    Shares are asynchronous in the sense that they promise to attain a
+    value at some point in the future.
+
+    Shares overload the arithmetic operations so that ``x = a + b``
+    will create a new share *x*, which will eventually contain the
+    sum of *a* and *b*. Each share is associated with a
+    :class:`Runtime` and the arithmetic operations simply call back to
+    that runtime.
+    """
+
+    def __init__(self, runtime, field, value=None, keyList=None, authentication_codes=None):
+        if value == None and keyList == None and authentication_codes == None:
+            Share.__init__(self, runtime, field)
+        else:
+            Share.__init__(self, runtime, field, BeDOZaShareContents(value, keyList, authentication_codes))
+        
+class RandomShareGenerator:
+    """ TODO: This is a dummy implementation, and should be replaced with proper code."""
+    
+    def generate_random_shares(self, field, number_of_shares):
+        self.init_keys(field)
+        shares = []
+        for i in xrange(0, number_of_shares):
+            v = field(self.id)
+            shares.append(self.generate_share(field, v))
+        return shares
+
+    def generate_share(self, field, value):
+        my_keys = self.generate_keys(field)
+        macs = self.generate_auth_codes(self.id, value)
+        return BeDOZaShare(self, field, value, my_keys, macs)
+
+    def generate_auth_codes(self, playerId, value):
+        keys = map(lambda (alpha, akeys): (alpha, akeys[playerId - 1]), self.keys.values())
+        macs = self.authentication_codes(keys, value)
+        return macs
+
+    def authentication_codes(self, keys, v):
+        macs = []
+        for alpha, beta in keys:
+            macs.append(alpha * v + beta)
+        return BeDOZaMACList(macs)
+
+    def generate_keys(self, field):
+        alpha, betas = self.get_keys()
+        return BeDOZaKeyList(alpha, betas)
+
+    def init_keys(self, field):
+
+        self.keys = {}
+        for player_id in self.players:
+            betas = [field(56387295767672113),
+                     field(89238458945400961),
+                     field(12340004554789025),
+                     field(12907853897457058),
+                     field(90457903592570134),
+                     field(56256262346343232),
+                     field(23897437894556562),
+                     field(90297849575975574)]
+            self.keys[player_id] = (field(player_id), betas)
+
+    def get_keys(self):   
+        return self.keys[self.id]
+
+class BeDOZaMixin(HashBroadcastMixin, RandomShareGenerator):
+ 
+    def MAC(self, alpha, beta, v):
+        return alpha * v + beta
+
+    def random_share(self, field):
+        """Retrieve a previously generated random share in the field, field.
+
+        If no more shares are left, generate self.random_share_number new ones.
+        """
+        if len(self.random_shares) == 0:
+            self.random_shares = self.generate_random_shares(field, self.random_share_number)
+
+        return self.random_shares.pop()
+
+    def output(self, share, receivers=None):
+        return self.open(share, receivers)
+
+    def open_multiple_values(self, shares, receivers=None):
+        """Share reconstruction of a list of shares."""
+        assert shares
+        # all players receive result by default
+        if receivers is None:
+            receivers = self.players.keys()
+
+        field = shares[0].field
+
+        self.increment_pc()
+
+        def recombine_value(player_shares_codes, keyLists, num_shares):
+            def check(ls, x, isOK):
+                true_str = str(True)
+                if reduce(lambda x, y: true_str == y, ls):
+                    return x
+                else:
+                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
+
+            n = len(self.players)
+            alpha = keyLists[0].alpha
+
+            values = num_shares * [0]
+            isOK = num_shares * [True]
+            for iny in xrange(num_shares):
+                keyList = keyLists[iny]
+                for inx, xs in enumerate(player_shares_codes):
+                    xi, mi = xs[iny]
+                    beta = keyList.get_key(inx)
+                    values[iny] += xi
+                    mi_prime = self.MAC(alpha, beta, xi)
+                    isOK[iny] = isOK[iny] and mi == mi_prime
+
+            isOK = reduce(lambda x, y: True == y, isOK)
+            ds = self.broadcast(self.players.keys(), self.players.keys(),
+                                str(isOK))
+            ds = gatherResults(ds)
+            ds.addCallbacks(check, self.error_handler, callbackArgs=(values, isOK))
+            return ds
+        
+        def exchange(ls, receivers):
+            # Send share to all receivers.
+            pc = tuple(self.program_counter)
+            keyLists = []
+            for other_id in receivers:
+                message_string = ""
+                for inx, beDOZaContents in enumerate(ls):
+                    keyLists.append(beDOZaContents.get_keys())
+                    message_string += "%s:%s;" % \
+                           (beDOZaContents.get_value().value, beDOZaContents.get_mac(other_id - 1).value)
+                self.protocols[other_id].sendData(pc, TEXT, message_string)
+
+            if self.id in receivers:
+                def deserialize(s):
+                    def field_long(x):
+                        return field(long(x))
+                    xs = s[0:-1].split(';')
+                    ys = [x.split(':') for x in xs]
+                    return [map(field_long, xs) for xs in ys]
+                num_players = len(self.players.keys())
+                values = num_players * [None]
+                for inx, other_id in enumerate(self.players.keys()):
+                    d = Deferred()
+                    d.addCallbacks(deserialize, self.error_handler)
+                    self._expect_data(other_id, TEXT, d)
+                    values[inx] = d
+                result = gatherResults(values)
+                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(keyLists, len(shares)))
+                return result
+
+        result = gather_shares(shares)
+        self.schedule_callback(result, exchange, receivers)
+        result.addErrback(self.error_handler)
+
+        # do actual communication
+        self.activate_reactor()
+
+        if self.id in receivers:
+            return result
+
+    def open_two_values(self, share_a, share_b, receivers=None):
+        """Share reconstruction of a list of shares."""
+        assert isinstance(share_a, Share)
+        assert isinstance(share_b, Share)
+        # all players receive result by default
+        if receivers is None:
+            receivers = self.players.keys()
+
+        field = share_a.field
+
+        self.increment_pc()
+
+        def recombine_value(shares_codes, keyList_a, keyList_b):
+            def check(ls, a, b, isOK):
+                true_str = str(True)
+                if reduce(lambda x, y: true_str == y, ls):
+                    return a, b
+                else:
+                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
+
+            n = len(self.players)
+            alpha_a = keyList_a.alpha
+            alpha_b = keyList_b.alpha
+
+            a = 0
+            b = 0
+            isOK = True
+            for inx in xrange(0, n):
+                ai = shares_codes[inx]
+                bi = shares_codes[2*n + inx]
+                mi_a = shares_codes[n + inx]
+                mi_b = shares_codes[3*n + inx]
+                beta_a = keyList_a.get_key(inx)
+                beta_b = keyList_b.get_key(inx)
+                a += ai
+                b += bi
+                mi_prime = self.MAC(alpha_a, beta_a, ai)
+                isOK = isOK and mi_a == mi_prime
+                mi_prime = self.MAC(alpha_b, beta_b, bi)
+                isOK = isOK and mi_b == mi_prime
+                
+            ds = self.broadcast(self.players.keys(), self.players.keys(),
+                                str(isOK))
+            ds = gatherResults(ds)
+            ds.addCallbacks(check, self.error_handler, callbackArgs=(a, b, isOK))
+            return ds
+        
+        def exchange((a, b), receivers):
+            # Send share to all receivers.
+            pc = tuple(self.program_counter)
+            for other_id in receivers:
+                self.protocols[other_id].sendShare(pc, a.get_value())
+                self.protocols[other_id].sendShare(pc, a.get_mac(other_id - 1))
+                self.protocols[other_id].sendShare(pc, b.get_value())
+                self.protocols[other_id].sendShare(pc, b.get_mac(other_id - 1))
+                
+            if self.id in receivers:
+                num_players = len(self.players.keys())
+                values_a = num_players * [None]
+                codes_a = num_players * [None]
+                values_b = num_players * [None]
+                codes_b = num_players * [None]
+                for inx, other_id in enumerate(self.players.keys()):
+                    values_a[inx] =  self._expect_share(other_id, field)
+                    codes_a[inx] = self._expect_share(other_id, field)
+                    values_b[inx] =  self._expect_share(other_id, field)
+                    codes_b[inx] = self._expect_share(other_id, field)
+                result = gatherResults(values_a + codes_a + values_b + codes_b)
+                self.schedule_callback(result, recombine_value, a.get_keys(), b.get_keys())
+                return result
+
+        result = gather_shares([share_a, share_b])
+        self.schedule_callback(result, exchange, receivers)
+        result.addErrback(self.error_handler)
+
+        # do actual communication
+        self.activate_reactor()
+
+        if self.id in receivers:
+            return result
+
+    def open(self, share, receivers=None):
+        """Share reconstruction."""
+        assert isinstance(share, Share)
+        # all players receive result by default
+        if receivers is None:
+            receivers = self.players.keys()
+
+        field = share.field
+
+        self.increment_pc()
+
+        def recombine_value(shares_codes, keyList):
+            isOK = True
+            n = len(self.players)
+            alpha = keyList.alpha
+            x = 0
+            for inx in xrange(0, n):
+                xi = shares_codes[inx]
+                mi = shares_codes[n + inx]
+                beta = keyList.get_key(inx)
+                x += xi
+                mi_prime = self.MAC(alpha, beta, xi)
+                isOK = isOK and mi == mi_prime
+            def check(ls, x, isOK):
+                true_str = str(True)
+                if reduce(lambda x, y: true_str == y, ls):
+                    return x
+                else:
+                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
+                
+            ds = self.broadcast(self.players.keys(), self.players.keys(),
+                                str(isOK))
+            ds = gatherResults(ds)
+            ds.addCallbacks(check, self.error_handler, callbackArgs=(x,isOK))
+            return ds
+
+        def exchange(shareContent, receivers):
+            # Send share to all receivers.
+            pc = tuple(self.program_counter)
+            for other_id in receivers:
+                self.protocols[other_id].sendShare(pc, shareContent.get_value())
+                self.protocols[other_id].sendShare(pc, shareContent.get_mac(other_id - 1))
+            if self.id in receivers:
+                num_players = len(self.players.keys())
+                values = num_players * [None]
+                codes = num_players * [None]
+                for inx, other_id in enumerate(self.players.keys()):
+                    values[inx] =  self._expect_share(other_id, field)
+                    codes[inx] = self._expect_share(other_id, field)
+                result = gatherResults(values + codes)
+                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(shareContent.get_keys(),))
+                return result
+
+        result = share.clone()
+        self.schedule_callback(result, exchange, receivers)
+        result.addErrback(self.error_handler)
+
+        # do actual communication
+        self.activate_reactor()
+
+        if self.id in receivers:
+            return result
+
+    def _plus_public(self, x, c, field):
+        x = x.add_public(c, self.id)
+        return BeDOZaShare(self, field, x.get_value(), x.get_keys(), x.get_macs())
+
+    def _plus(self, (x, y), field):
+        """Addition of share-contents *x* and *y*."""
+        return x + y
+
+    def _minus_public_right(self, x, c, field):
+        z = self._minus_public_right_without_share(x, c, field)
+        return BeDOZaShare(self, field, z.get_value(), z.get_keys(), z.get_macs())
+
+    def _minus_public_right_without_share(self, x, c, field):
+        return x.sub_public(c, self.id)
+
+    def _wrap_in_share(self, shareContents, field):
+        return BeDOZaShare(self, field,
+                           shareContents.get_value(),
+                           shareContents.get_keys(),
+                           shareContents.get_macs())
+
+    def _minus_public_left(self, x, c, field):
+        y = self._constant_multiply(x, field(-1))
+        return self._plus_public(y, c, field)
+    
+    def _minus(self, (x, y), field):
+        """Subtraction of share-tuples *x* and *y*."""
+        return x - y
+
+    def _constant_multiply(self, x, c):
+        """Multiplication of a share-tuple with a constant c."""
+        assert(isinstance(c, FieldElement))
+        return x.cmul(c)
+
+    def _get_triple(self, field):
+        """ TODO: This is a dummy implementation, and should be replaced with proper code."""
+        self.init_keys(field)
+        a, b, c = 0, 0, 0
+        share_a = field(2)
+        share_b = field(4)
+        n = len(self.players)
+        share_c = n * share_a * share_b
+        for playerid in self.players.keys():
+            if self.id == playerid:
+                triple_a = self.generate_share(field, share_a)
+                a += share_a.value
+                triple_b = self.generate_share(field, share_b)
+                b += share_b.value
+                triple_c = self.generate_share(field, share_c)
+                c += share_c.value
+        return [triple_a, triple_b, triple_c], False
+
+
+class BeDOZaRuntime(BeDOZaMixin, SimpleArithmeticRuntime):
+    """The BeDOZa runtime.
+
+    The runtime is used for sharing values (:meth:`secret_share` or
+    :meth:`shift`) into :class:`BeDOZaShare` 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:`~viff.runtime.Runtime`
+    object. To create an instance and connect it correctly with the
+    other players, please use the :func:`~viff.runtime.create_runtime`
+    function instead of instantiating a Runtime directly. The
+    :func:`~viff.runtime.create_runtime` function will take care of
+    setting up network connections and return a :class:`Deferred`
+    which triggers with the :class:`~viff.runtime.Runtime` object when
+    it is ready.
+    """
+
+    def __init__(self, player, threshold=None, options=None):
+        """Initialize runtime."""
+        SimpleArithmeticRuntime.__init__(self, player, threshold, options)
+        self.threshold = self.num_players - 1
+        self.random_share_number = 100
+        self.random_shares = []
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/bedoza_triple.py	Fri Jul 23 13:17:48 2010 +0200
@@ -0,0 +1,556 @@
+# Copyright 2010 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/>.
+
+"""Triple generation for the BeDOZa protocol.
+    TODO: Explain more.
+"""
+
+import itertools
+
+from twisted.internet.defer import Deferred, gatherResults, succeed
+
+from viff.runtime import Runtime, Share, ShareList, gather_shares
+from viff.field import FieldElement, GF
+from viff.constants import TEXT
+from viff.util import rand
+
+from viff.bedoza.bedoza import BeDOZaShare, BeDOZaShareContents
+
+from viff.bedoza.keylist import BeDOZaKeyList
+from viff.bedoza.maclist import BeDOZaMACList
+
+# TODO: Use secure random instead!
+from random import Random
+
+from viff.hash_broadcast import HashBroadcastMixin
+
+try:
+    import pypaillier
+except ImportError:
+    # The pypaillier module is not released yet, so we cannot expect
+    # the import to work.
+    print "Error: The pypaillier module or one of the used functions " \
+        "are not available."
+
+class Triple(object):
+    def __init__(self, a, b, c):
+        self.a, self.b, self.c = a, b, c
+    def __str__(self):
+        return "(%s,%s,%s)" % (self.a, self.b, self.c)
+
+
+def _send(runtime, vals, serialize=str, deserialize=int):
+    """Send vals[i] to player i + 1. Returns deferred list.
+
+    Works as default for integers. If other stuff has to be
+    sent, supply another serialization, deserialition.
+    """
+    runtime.increment_pc()
+    
+    pc = tuple(runtime.program_counter)
+    for p in runtime.players:
+        msg = serialize(vals[p - 1])
+        runtime.protocols[p].sendData(pc, TEXT, msg)
+    def err_handler(err):
+        print err
+    values = []
+    for p in runtime.players:
+        d = Deferred()
+        d.addCallbacks(deserialize, err_handler)
+        runtime._expect_data(p, TEXT, d)
+        values.append(d)
+    result = gatherResults(values)
+    return result
+
+def _convolute(runtime, val, serialize=str, deserialize=int):
+    """As send, but sends the same val to all players."""
+    return _send(runtime, [val] * runtime.num_players,
+                 serialize=serialize, deserialize=deserialize)
+
+def _convolute_gf_elm(runtime, gf_elm):
+    return _convolute(runtime, gf_elm,
+                      serialize=lambda x: str(x.value),
+                      deserialize=lambda x: gf_elm.field(int(x)))
+
+def _send_gf_elm(runtime, vals):
+    return _send(runtime, vals, 
+                 serialize=lambda x: str(x.value),
+                 deserialize=lambda x: gf_elm.field(int(x)))
+
+
+class PartialShareContents(object):
+    """A BeDOZa share without macs, e.g. < a >.
+    TODO: BeDOZaShare should extend this class?
+    
+    TODO: Should the partial share contain the public encrypted shares?
+    TODO: It may be wrong to pass encrypted_shares to super constructor; 
+      does it mean that the already public values get passed along on the
+      network even though all players already posess them?
+    """
+    def __init__(self, value, enc_shares, N_squared_list):
+        self.value = value
+        self.enc_shares = enc_shares
+        self.N_squared_list = N_squared_list
+
+    def __str__(self):
+        return "PartialShareContents(%d; %s; %s)" % (self.value, self.enc_shares, self.N_squared_list)
+
+    def __add__(self, other):
+        z = self.value + other.value
+        z_enc_shares = []
+        for x, y, N_squared in zip(self.enc_shares, other.enc_shares, self.N_squared_list):
+            z_enc_shares.append((x * y) % N_squared)
+        return PartialShareContents(z, z_enc_shares, self.N_squared_list)
+
+# In VIFF, callbacks get the *contents* of a share as input. Hence, in order
+# to get a PartialShare as input to callbacks, we need this extra level of
+# wrapper indirection.
+class PartialShare(Share):
+    def __init__(self, runtime, field, value=None, enc_shares=None):
+        if value == None and enc_shares == None:
+            Share.__init__(self, runtime, field)
+        else:
+            N_squared_list = [ runtime.players[player_id].pubkey['n_square'] for player_id in runtime.players.keys()]
+            partial_share_contents = PartialShareContents(value, enc_shares, N_squared_list)
+            Share.__init__(self, runtime, field, partial_share_contents)
+
+
+class PartialShareGenerator:
+
+    def __init__(self, Zp, runtime, random, paillier):
+        self.paillier = paillier
+        self.Zp = Zp
+        self.runtime = runtime
+        self.random = random
+
+    def generate_share(self, value):
+        self.runtime.increment_pc()
+        
+        r = [self.Zp(self.random.randint(0, self.Zp.modulus - 1)) # TODO: Exclusve?
+             for _ in range(self.runtime.num_players - 1)]
+        if self.runtime.id == 1:
+            share = value - sum(r)
+        else:
+            share = r[self.runtime.id - 2]
+        enc_share = self.paillier.encrypt(share.value)
+        enc_shares = _convolute(self.runtime, enc_share)
+        def create_partial_share(enc_shares, share):
+            return PartialShare(self.runtime, self.Zp, share, enc_shares)
+        self.runtime.schedule_callback(enc_shares, create_partial_share, share)
+        return enc_shares
+
+    def generate_random_shares(self, n):
+        self.runtime.increment_pc()
+        N_squared_list = [ self.runtime.players[player_id].pubkey['n_square'] for player_id in self.runtime.players]
+        shares = [PartialShare(self.runtime, self.Zp) for _ in xrange(n)]
+        for inx in xrange(n):
+            r = self.random.randint(0, self.Zp.modulus - 1)
+            ri = self.Zp(r)
+            enc_share = self.paillier.encrypt(ri.value)
+            enc_shares = _convolute(self.runtime, enc_share)
+            def create_partial_share(enc_shares, ri, s, N_squared_list):
+                s.callback(PartialShareContents(ri, enc_shares, N_squared_list))
+            self.runtime.schedule_callback(enc_shares,
+                                           create_partial_share,
+                                           ri,
+                                           shares[inx],
+                                           N_squared_list)
+        return shares
+
+class ShareGenerator(PartialShareGenerator):
+
+    def __init__(self, Zp, runtime, random, paillier, u_bound, alpha):
+        self.u_bound = u_bound
+        self.alpha = alpha
+        PartialShareGenerator.__init__(self, Zp, runtime, random, paillier)
+
+    def generate_share(self, value):
+        self.runtime.increment_pc()
+        partial_share = PartialShareGenerator.generate_share(self, value)
+        full_share = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
+                             self.random, self.paillier, [partial_share])
+        return full_share[0]
+    
+    def generate_random_shares(self, n):
+        self.runtime.increment_pc()
+        partial_shares = PartialShareGenerator.generate_random_shares(self, n)
+        return add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
+                        self.random, self.paillier, partial_shares)
+
+class ModifiedPaillier(object):
+    """A slight modification of the Paillier cryptosystem.
+
+    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
+    than the usual Z_n where n is the Paillier modulus.
+
+    See Ivan's paper, beginning of section 6.
+    """
+
+    def __init__(self, runtime, random):
+        self.runtime = runtime;
+        self.random = random
+
+    def _f(self, x, n):
+        if x >= 0:
+            return x
+        else:
+            return n + x
+
+    def _f_inverse(self, y, n):
+        if 0 <= y <= (n + 1) / 2:
+            return y
+        else:
+            return y - n
+
+    def encrypt(self, value, player_id=None):
+        """Encrypt using public key of player player_id.
+
+        Defaults to own public key.
+        """
+        assert isinstance(value, int) or isinstance(value, long), \
+            "paillier: encrypts only integers and longs, got %s" % value.__class__
+        if not player_id:
+            player_id = self.runtime.id
+        n = self.runtime.players[player_id].pubkey['n']
+        min = -(n - 1) / 2 + 1
+        max = (n + 1) / 2
+        assert min <= value <= max, \
+            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
+            "[%d ; %d]"  % (value, min, max)
+        pubkey = self.runtime.players[player_id].pubkey
+        randomness = self.random.randint(1, long(n))
+        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
+
+    def decrypt(self, enc_value):
+        """Decrypt using own private key."""
+        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
+            "paillier decrypts only longs, got %s" % enc_value.__class__
+        n = self.runtime.players[self.runtime.id].pubkey['n']
+        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
+        assert 0 <= enc_value < n_square, \
+            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
+            % (enc_value, n_square)
+        seckey = self.runtime.players[self.runtime.id].seckey
+        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
+
+    def get_modulus(self, player_id):
+        return self.runtime.players[player_id].pubkey['n']
+
+    def get_modulus_square(self, player_id):
+        return self.runtime.players[player_id].pubkey['n_square']
+
+def add_macs(runtime, field, u_bound, alpha, random, paillier, partial_shares):
+    """Adds macs to the set of PartialBeDOZaShares.
+        
+    Returns a deferred which yields a list of full shares, e.g.
+    including macs.  (the full shares are deferreds of type
+    BeDOZaShare.)
+    """        
+    # TODO: Would be nice with a class ShareContents like the class
+    # PartialShareContents used here.
+        
+    runtime.increment_pc() # Huh!?
+
+    def do_add_macs(partial_share_contents, result_shares):
+        num_players = runtime.num_players
+        lists_of_mac_keys = [ [] for x in runtime.players ]
+        lists_of_c_list = [ [] for x in runtime.players ]
+        for partial_share_content in partial_share_contents:
+            for j in xrange(0, num_players):
+                # TODO: This is probably not the fastes way to generate
+                # the betas.
+                beta = random.randint(0, u_bound)
+                # TODO: Outcommented until mod paillier works for negative numbers.
+                # if rand.choice([True, False]):
+                #    beta = -beta
+                enc_beta = paillier.encrypt(beta, player_id=j + 1)
+                c_j = partial_share_content.enc_shares[j]
+                n2 = paillier.get_modulus_square(j + 1)
+                c = (pow(c_j, alpha, n2) * enc_beta) % n2
+                lists_of_c_list[j].append(c)
+                lists_of_mac_keys[j].append(field(beta))
+
+        received_cs = _send(runtime, lists_of_c_list, deserialize=eval)
+
+        def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
+            shares = []               
+            for inx in xrange(0, len(partial_share_contents)):
+                mac_keys = []
+                decrypted_cs = []
+                for c_list, mkeys in zip(recevied_cs,
+                                         lists_of_mac_keys):
+                    decrypted_cs.append(field(paillier.decrypt(c_list[inx])))
+                    mac_keys.append(mkeys[inx])
+                partial_share = partial_share_contents[inx]
+                mac_key_list = BeDOZaKeyList(alpha, mac_keys)
+
+                mac_msg_list = BeDOZaMACList(decrypted_cs)
+                result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
+                                                                mac_key_list,
+                                                                mac_msg_list))
+            return shares
+
+        runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
+        return received_cs
+
+    result_shares = [Share(runtime, field) for x in xrange(len(partial_shares))]
+    runtime.schedule_callback(gatherResults(partial_shares),
+                              do_add_macs,
+                              result_shares)
+    return result_shares
+
+
+class TripleGenerator(object):
+
+    def __init__(self, runtime, p, random):
+        assert p > 1
+        self.random = random
+        # TODO: Generate Paillier cipher with N_i sufficiently larger than p
+        self.runtime = runtime
+        self.p = p
+        self.Zp = GF(p)
+        self.k = self._bit_length_of(p)
+        self.u_bound = 2**(4 * self.k)
+
+        paillier_random = Random(self.random.getrandbits(128))
+        alpha_random = Random(self.random.getrandbits(128))
+        self.paillier = ModifiedPaillier(runtime, paillier_random)
+        
+        # Debug output.
+        #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
+        #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
+        #print "n_%d bitlength: %d" % (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
+
+        #self.Zp = GF(p)
+        #self.Zn2 = GF(self.paillier.pubkey['n_square'])
+        #self.alpha = self.Zp(self.random.randint(0, p - 1))
+        self.alpha = alpha_random.randint(0, p - 1)
+        self.n2 = runtime.players[runtime.id].pubkey['n_square']
+
+    def _bit_length_of(self, i):
+        bit_length = 0
+        while i:
+            i >>= 1
+            bit_length += 1
+        return bit_length
+
+    def generate_triples(self, n):
+        """Generates and returns a set of n triples.
+        
+        Data sent over the network is packaged in large hunks in order
+        to optimize. TODO: Explain better.
+
+        TODO: This method needs to have enough RAM to represent all n
+        triples in memory at the same time. Is there a nice way to
+        stream this, e.g. by using Python generators?
+        """
+
+        self.runtime.increment_pc()
+        
+        def check(v, a, b, c):
+            if v.value != 0:
+                raise Exception("TripleTest failed - The two triples were inconsistent.")
+            return (a, b, c)
+        
+        def compute_value(r, a, b, c, x, y, z):
+            l = self.runtime._cmul(r, x, self.Zp)
+            m = self.runtime._cmul(r, y, self.Zp)
+            k = self.runtime._cmul(r*r, z, self.Zp)
+            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
+            v = self.runtime.open(v)
+            v.addCallback(check, a, b, c)
+            return v
+
+        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier, self.u_bound, self.alpha)
+        
+        random_shares = gen.generate_random_shares(n)
+
+        results = [Deferred() for _ in xrange(n)]
+        
+        triples = self._generate_passive_triples(2 * n)
+
+        for inx in xrange(n):
+            a = triples[inx]
+            b = triples[inx + 2 * n]
+            c = triples[inx + 4 * n]
+            x = triples[inx + n]
+            y = triples[inx + 3 * n]
+            z = triples[inx + 5 * n]
+            r = self.runtime.open(random_shares[inx])
+            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
+            r.chainDeferred(results[inx])
+        return results
+          
+        # TODO: Do some ZK stuff.
+
+    def _generate_passive_triples(self, n):
+        """Generates and returns a list of 3n shares corresponding to
+        n passive tuples. The first n are the a's, then comes n b's
+        followed by n c's.
+        
+        Consistency is only guaranteed if all players follow the protool.
+        """
+
+        self.runtime.increment_pc()
+        
+        gen = PartialShareGenerator(self.Zp, self.runtime, self.random, self.paillier)
+        partial_shares = []
+        for _ in xrange(2 * n):
+             partial_shares.append(gen.generate_share(self.random.randint(0, self.Zp.modulus - 1)))
+
+
+        partial_shares_c = self._full_mul(partial_shares[0:n], partial_shares[n:2*n])
+
+        full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, partial_shares + partial_shares_c)
+
+        return full_shares  
+
+        # for player i:
+        #     receive c from player i and set 
+        #         m^i=Decrypt(c)
+    
+    def _mul(self, inx, jnx, ais=None, cjs=None):
+        """Multiply each of the field elements in *ais* with the
+        corresponding encrypted elements in *cjs*.
+        
+        Returns a deferred which will yield a list of PartialShareContents.
+        """
+        CKIND = 1
+        DiKIND = 2
+        DjKIND = 3
+        
+        self.runtime.increment_pc()
+
+        pc = tuple(self.runtime.program_counter)
+
+        deferreds = []
+        zis = []
+        if self.runtime.id == inx:
+            Nj_square = self.paillier.get_modulus_square(jnx)
+            cs = []
+            dis = []
+            for ai, cj in zip(ais, cjs):
+                u = rand.randint(0, self.u_bound)
+                Ej_u = self.paillier.encrypt(u, jnx)
+                cs.append( (pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
+                zi = self.Zp(-u)
+                zis.append(zi)
+                dis.append(self.paillier.encrypt(zi.value, inx))
+            self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
+
+            for player_id in self.runtime.players:
+                self.runtime.protocols[player_id].sendData(pc, DiKIND, str(dis))
+
+        if self.runtime.id == jnx:
+            cs = Deferred()
+            self.runtime._expect_data(inx, CKIND, cs)
+            def decrypt(cs, pc, zis):
+                zjs = []
+                djs = []
+                for c in eval(cs):
+                    t = self.paillier.decrypt(c)
+                    zj = self.Zp(t)
+                    zjs.append(zj)
+                    djs.append(self.paillier.encrypt(zj.value, jnx))
+                for player_id in self.runtime.players:
+                    self.runtime.protocols[player_id].sendData(pc, DjKIND, str(djs))
+                if not zis == []:
+                    return [x + y for x, y in zip(zis, zjs)]
+                else:
+                    return zjs 
+            cs.addCallback(decrypt, pc, zis)
+            deferreds.append(cs)
+        else:
+            zis_deferred = Deferred()
+            zis_deferred.callback(zis)
+            deferreds.append(zis_deferred)
+
+        dis = Deferred()
+        self.runtime._expect_data(inx, DiKIND, dis)
+        djs = Deferred()
+        self.runtime._expect_data(jnx, DjKIND, djs)
+
+        deferreds.append(dis)
+        deferreds.append(djs)
+        r = gatherResults(deferreds)
+        def wrap((values, dis, djs), inx, jnx):
+            dis = eval(dis)
+            djs = eval(djs)
+            n_square_i = self.paillier.get_modulus_square(inx)
+            n_square_j = self.paillier.get_modulus_square(jnx)
+            N_squared_list = [self.paillier.get_modulus_square(player_id) for player_id in self.runtime.players]
+            ps = []
+            for v, di, dj in itertools.izip_longest(values, dis, djs, fillvalue=self.Zp(0)):
+                value = v 
+                enc_shares = len(self.runtime.players) * [1]
+                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
+                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
+                ps.append(PartialShareContents(value, enc_shares, N_squared_list))
+            return ps
+        r.addCallback(wrap, inx, jnx)
+        return r
+
+    def _full_mul(self, a, b):
+        """Multiply each of the PartialShares in the list *a* with the
+        corresponding PartialShare in the list *b*.
+        
+        Returns a deferred which will yield a list of PartialShares.
+        """
+        self.runtime.increment_pc()
+        
+        def do_full_mul(shares, result_shares):
+            """Share content belonging to ai, bi are at:
+            shares[i], shares[len(shares) + i].
+            """
+            deferreds = []
+            len_shares = len(shares)
+            a_values = [s.value for s in shares[0:len_shares/2]]
+            b_enc_shares = []
+            for inx in self.runtime.players:              
+                b_enc_shares.append([s.enc_shares[inx - 1] for s in shares[len_shares/2:]])
+            for inx in xrange(0, len(self.runtime.players)):
+                for jnx in xrange(0, len(self.runtime.players)):
+                    deferreds.append(self._mul(inx + 1,
+                                               jnx + 1,
+                                               a_values,
+                                               b_enc_shares[jnx]))
+                        
+            def compute_shares(partialShareContents, len_shares, result_shares):
+                num_players = len(self.runtime.players)
+                pcs = len(partialShareContents[0]) * [None]
+                for ps in partialShareContents:
+                    for inx in xrange(0, len(ps)):
+                        if pcs[inx] == None:
+                            pcs[inx] = ps[inx]
+                        else:
+                            pcs[inx] += ps[inx]
+                for p, s in zip(pcs, result_shares):
+                    s.callback(p)
+                return None
+            d = gatherResults(deferreds)
+            d.addCallback(compute_shares, len_shares, result_shares)
+            return d
+        result_shares = [Share(self.runtime, self.Zp) for x in a]
+        self.runtime.schedule_callback(gatherResults(a + b),
+                                       do_full_mul,
+                                       result_shares)
+        return result_shares
+
+
+# TODO: Represent all numbers by GF objects, Zp, Zn, etc.
+# E.g. paillier encrypt should return Zn^2 elms and decrypt should
+# return Zp elements.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/keylist.py	Fri Jul 23 13:17:48 2010 +0200
@@ -0,0 +1,62 @@
+# Copyright 2010 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/>.
+
+class BeDOZaKeyList(object):
+    """A list of keys, one for each player.
+
+    We assume that the key for player *i* is stored in
+    location *i - 1* in the *keys* list given as argument to the constructor.
+    """
+
+    def __init__(self, alpha, keys):
+        self.alpha = alpha
+        self.keys = keys
+
+    def get_key(self, player_id):
+        return self.keys[player_id]
+
+    def set_key(self, player_id, v):
+        self.keys[player_id] = v
+
+    def cmul(self, c):
+        return BeDOZaKeyList(self.alpha, map(lambda k: c * k, self.keys))
+
+    def __add__(self, other):
+        """Addition."""
+        assert self.alpha == other.alpha
+        keys = []
+        for k1, k2 in zip(self.keys, other.keys):
+            keys.append(k1 + k2)
+        return BeDOZaKeyList(self.alpha, keys)
+
+    def __sub__(self, other):
+        """Subtraction."""
+        assert self.alpha == other.alpha
+        keys = []
+        for k1, k2 in zip(self.keys, other.keys):
+            keys.append(k1 - k2)
+        return BeDOZaKeyList(self.alpha, keys)
+
+    def __eq__(self, other):
+        return self.alpha == other.alpha and self.keys == other.keys
+
+    def __str__(self):
+        return "(%s, %s)" % (self.alpha, str(self.keys))
+
+    def __repr__(self):
+        return str(self)
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/bedoza/maclist.py	Fri Jul 23 13:17:48 2010 +0200
@@ -0,0 +1,54 @@
+# Copyright 2010 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/>.
+
+class BeDOZaMACList(object):
+
+    def __init__(self, macs):
+        self.macs = macs
+
+    def get_macs(self):
+        return self.macs
+
+    def get_mac(self, inx):
+        return self.macs[inx]
+
+    def cmul(self, c):
+        return BeDOZaMACList(map(lambda m: c * m, self.macs))
+        
+    def __add__(self, other):
+        """Addition."""
+        macs = []
+        for c1, c2 in zip(self.macs, other.macs):
+            macs.append(c1 + c2)
+        return BeDOZaMACList(macs)
+
+    def __sub__(self, other):
+        """Subtraction."""
+        macs = []
+        for c1, c2 in zip(self.macs, other.macs):
+            macs.append(c1 - c2)
+        return BeDOZaMACList(macs)
+
+    def __eq__(self, other):
+        return self.macs == other.macs
+
+    def __str__(self):
+        return str(self.macs)
+
+    def __repr__(self):
+        return str(self)
+    
--- a/viff/bedoza_triple.py	Fri Jul 23 11:18:04 2010 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,553 +0,0 @@
-# Copyright 2010 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/>.
-
-"""Triple generation for the BeDOZa protocol.
-    TODO: Explain more.
-"""
-
-import itertools
-
-from twisted.internet.defer import Deferred, gatherResults, succeed
-
-from viff.runtime import Runtime, Share, ShareList, gather_shares
-from viff.field import FieldElement, GF
-from viff.constants import TEXT
-from viff.util import rand
-
-from bedoza import BeDOZaKeyList, BeDOZaMACList, BeDOZaShare, BeDOZaShareContents
-
-# TODO: Use secure random instead!
-from random import Random
-
-from hash_broadcast import HashBroadcastMixin
-
-try:
-    import pypaillier
-except ImportError:
-    # The pypaillier module is not released yet, so we cannot expect
-    # the import to work.
-    print "Error: The pypaillier module or one of the used functions " \
-        "are not available."
-
-class Triple(object):
-    def __init__(self, a, b, c):
-        self.a, self.b, self.c = a, b, c
-    def __str__(self):
-        return "(%s,%s,%s)" % (self.a, self.b, self.c)
-
-
-def _send(runtime, vals, serialize=str, deserialize=int):
-    """Send vals[i] to player i + 1. Returns deferred list.
-
-    Works as default for integers. If other stuff has to be
-    sent, supply another serialization, deserialition.
-    """
-    runtime.increment_pc()
-    
-    pc = tuple(runtime.program_counter)
-    for p in runtime.players:
-        msg = serialize(vals[p - 1])
-        runtime.protocols[p].sendData(pc, TEXT, msg)
-    def err_handler(err):
-        print err
-    values = []
-    for p in runtime.players:
-        d = Deferred()
-        d.addCallbacks(deserialize, err_handler)
-        runtime._expect_data(p, TEXT, d)
-        values.append(d)
-    result = gatherResults(values)
-    return result
-
-def _convolute(runtime, val, serialize=str, deserialize=int):
-    """As send, but sends the same val to all players."""
-    return _send(runtime, [val] * runtime.num_players,
-                 serialize=serialize, deserialize=deserialize)
-
-def _convolute_gf_elm(runtime, gf_elm):
-    return _convolute(runtime, gf_elm,
-                      serialize=lambda x: str(x.value),
-                      deserialize=lambda x: gf_elm.field(int(x)))
-
-def _send_gf_elm(runtime, vals):
-    return _send(runtime, vals, 
-                 serialize=lambda x: str(x.value),
-                 deserialize=lambda x: gf_elm.field(int(x)))
-
-
-class PartialShareContents(object):
-    """A BeDOZa share without macs, e.g. < a >.
-    TODO: BeDOZaShare should extend this class?
-    
-    TODO: Should the partial share contain the public encrypted shares?
-    TODO: It may be wrong to pass encrypted_shares to super constructor; 
-      does it mean that the already public values get passed along on the
-      network even though all players already posess them?
-    """
-    def __init__(self, value, enc_shares, N_squared_list):
-        self.value = value
-        self.enc_shares = enc_shares
-        self.N_squared_list = N_squared_list
-
-    def __str__(self):
-        return "PartialShareContents(%d; %s; %s)" % (self.value, self.enc_shares, self.N_squared_list)
-
-    def __add__(self, other):
-        z = self.value + other.value
-        z_enc_shares = []
-        for x, y, N_squared in zip(self.enc_shares, other.enc_shares, self.N_squared_list):
-            z_enc_shares.append((x * y) % N_squared)
-        return PartialShareContents(z, z_enc_shares, self.N_squared_list)
-
-# In VIFF, callbacks get the *contents* of a share as input. Hence, in order
-# to get a PartialShare as input to callbacks, we need this extra level of
-# wrapper indirection.
-class PartialShare(Share):
-    def __init__(self, runtime, field, value=None, enc_shares=None):
-        if value == None and enc_shares == None:
-            Share.__init__(self, runtime, field)
-        else:
-            N_squared_list = [ runtime.players[player_id].pubkey['n_square'] for player_id in runtime.players.keys()]
-            partial_share_contents = PartialShareContents(value, enc_shares, N_squared_list)
-            Share.__init__(self, runtime, field, partial_share_contents)
-
-
-class PartialShareGenerator:
-
-    def __init__(self, Zp, runtime, random, paillier):
-        self.paillier = paillier
-        self.Zp = Zp
-        self.runtime = runtime
-        self.random = random
-
-    def generate_share(self, value):
-        self.runtime.increment_pc()
-        
-        r = [self.Zp(self.random.randint(0, self.Zp.modulus - 1)) # TODO: Exclusve?
-             for _ in range(self.runtime.num_players - 1)]
-        if self.runtime.id == 1:
-            share = value - sum(r)
-        else:
-            share = r[self.runtime.id - 2]
-        enc_share = self.paillier.encrypt(share.value)
-        enc_shares = _convolute(self.runtime, enc_share)
-        def create_partial_share(enc_shares, share):
-            return PartialShare(self.runtime, self.Zp, share, enc_shares)
-        self.runtime.schedule_callback(enc_shares, create_partial_share, share)
-        return enc_shares
-
-    def generate_random_shares(self, n):
-        self.runtime.increment_pc()
-        N_squared_list = [ self.runtime.players[player_id].pubkey['n_square'] for player_id in self.runtime.players]
-        shares = [PartialShare(self.runtime, self.Zp) for _ in xrange(n)]
-        for inx in xrange(n):
-            r = self.random.randint(0, self.Zp.modulus - 1)
-            ri = self.Zp(r)
-            enc_share = self.paillier.encrypt(ri.value)
-            enc_shares = _convolute(self.runtime, enc_share)
-            def create_partial_share(enc_shares, ri, s, N_squared_list):
-                s.callback(PartialShareContents(ri, enc_shares, N_squared_list))
-            self.runtime.schedule_callback(enc_shares,
-                                           create_partial_share,
-                                           ri,
-                                           shares[inx],
-                                           N_squared_list)
-        return shares
-
-class ShareGenerator(PartialShareGenerator):
-
-    def __init__(self, Zp, runtime, random, paillier, u_bound, alpha):
-        self.u_bound = u_bound
-        self.alpha = alpha
-        PartialShareGenerator.__init__(self, Zp, runtime, random, paillier)
-
-    def generate_share(self, value):
-        self.runtime.increment_pc()
-        partial_share = PartialShareGenerator.generate_share(self, value)
-        full_share = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
-                             self.random, self.paillier, [partial_share])
-        return full_share[0]
-    
-    def generate_random_shares(self, n):
-        self.runtime.increment_pc()
-        partial_shares = PartialShareGenerator.generate_random_shares(self, n)
-        return add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
-                        self.random, self.paillier, partial_shares)
-
-class ModifiedPaillier(object):
-    """A slight modification of the Paillier cryptosystem.
-
-    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
-    than the usual Z_n where n is the Paillier modulus.
-
-    See Ivan's paper, beginning of section 6.
-    """
-
-    def __init__(self, runtime, random):
-        self.runtime = runtime;
-        self.random = random
-
-    def _f(self, x, n):
-        if x >= 0:
-            return x
-        else:
-            return n + x
-
-    def _f_inverse(self, y, n):
-        if 0 <= y <= (n + 1) / 2:
-            return y
-        else:
-            return y - n
-
-    def encrypt(self, value, player_id=None):
-        """Encrypt using public key of player player_id.
-
-        Defaults to own public key.
-        """
-        assert isinstance(value, int) or isinstance(value, long), \
-            "paillier: encrypts only integers and longs, got %s" % value.__class__
-        if not player_id:
-            player_id = self.runtime.id
-        n = self.runtime.players[player_id].pubkey['n']
-        min = -(n - 1) / 2 + 1
-        max = (n + 1) / 2
-        assert min <= value <= max, \
-            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
-            "[%d ; %d]"  % (value, min, max)
-        pubkey = self.runtime.players[player_id].pubkey
-        randomness = self.random.randint(1, long(n))
-        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
-
-    def decrypt(self, enc_value):
-        """Decrypt using own private key."""
-        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
-            "paillier decrypts only longs, got %s" % enc_value.__class__
-        n = self.runtime.players[self.runtime.id].pubkey['n']
-        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
-        assert 0 <= enc_value < n_square, \
-            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
-            % (enc_value, n_square)
-        seckey = self.runtime.players[self.runtime.id].seckey
-        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
-
-    def get_modulus(self, player_id):
-        return self.runtime.players[player_id].pubkey['n']
-
-    def get_modulus_square(self, player_id):
-        return self.runtime.players[player_id].pubkey['n_square']
-
-def add_macs(runtime, field, u_bound, alpha, random, paillier, partial_shares):
-    """Adds macs to the set of PartialBeDOZaShares.
-        
-    Returns a deferred which yields a list of full shares, e.g.
-    including macs.  (the full shares are deferreds of type
-    BeDOZaShare.)
-    """        
-    # TODO: Would be nice with a class ShareContents like the class
-    # PartialShareContents used here.
-        
-    runtime.increment_pc() # Huh!?
-
-    def do_add_macs(partial_share_contents, result_shares):
-        num_players = runtime.num_players
-        lists_of_mac_keys = [ [] for x in runtime.players ]
-        lists_of_c_list = [ [] for x in runtime.players ]
-        for partial_share_content in partial_share_contents:
-            for j in xrange(0, num_players):
-                # TODO: This is probably not the fastes way to generate
-                # the betas.
-                beta = random.randint(0, u_bound)
-                # TODO: Outcommented until mod paillier works for negative numbers.
-                # if rand.choice([True, False]):
-                #    beta = -beta
-                enc_beta = paillier.encrypt(beta, player_id=j + 1)
-                c_j = partial_share_content.enc_shares[j]
-                n2 = paillier.get_modulus_square(j + 1)
-                c = (pow(c_j, alpha, n2) * enc_beta) % n2
-                lists_of_c_list[j].append(c)
-                lists_of_mac_keys[j].append(field(beta))
-
-        received_cs = _send(runtime, lists_of_c_list, deserialize=eval)
-
-        def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
-            shares = []               
-            for inx in xrange(0, len(partial_share_contents)):
-                mac_keys = []
-                decrypted_cs = []
-                for c_list, mkeys in zip(recevied_cs,
-                                         lists_of_mac_keys):
-                    decrypted_cs.append(field(paillier.decrypt(c_list[inx])))
-                    mac_keys.append(mkeys[inx])
-                partial_share = partial_share_contents[inx]
-                mac_key_list = BeDOZaKeyList(alpha, mac_keys)
-
-                mac_msg_list = BeDOZaMACList(decrypted_cs)
-                result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
-                                                                mac_key_list,
-                                                                mac_msg_list))
-            return shares
-
-        runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
-        return received_cs
-
-    result_shares = [Share(runtime, field) for x in xrange(len(partial_shares))]
-    runtime.schedule_callback(gatherResults(partial_shares),
-                              do_add_macs,
-                              result_shares)
-    return result_shares
-
-
-class TripleGenerator(object):
-
-    def __init__(self, runtime, p, random):
-        assert p > 1
-        self.random = random
-        # TODO: Generate Paillier cipher with N_i sufficiently larger than p
-        self.runtime = runtime
-        self.p = p
-        self.Zp = GF(p)
-        self.k = self._bit_length_of(p)
-        self.u_bound = 2**(4 * self.k)
-
-        paillier_random = Random(self.random.getrandbits(128))
-        alpha_random = Random(self.random.getrandbits(128))
-        self.paillier = ModifiedPaillier(runtime, paillier_random)
-        
-        # Debug output.
-        #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
-        #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
-        #print "n_%d bitlength: %d" % (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
-
-        #self.Zp = GF(p)
-        #self.Zn2 = GF(self.paillier.pubkey['n_square'])
-        #self.alpha = self.Zp(self.random.randint(0, p - 1))
-        self.alpha = alpha_random.randint(0, p - 1)
-        self.n2 = runtime.players[runtime.id].pubkey['n_square']
-
-    def _bit_length_of(self, i):
-        bit_length = 0
-        while i:
-            i >>= 1
-            bit_length += 1
-        return bit_length
-
-    def generate_triples(self, n):
-        """Generates and returns a set of n triples.
-        
-        Data sent over the network is packaged in large hunks in order
-        to optimize. TODO: Explain better.
-
-        TODO: This method needs to have enough RAM to represent all n
-        triples in memory at the same time. Is there a nice way to
-        stream this, e.g. by using Python generators?
-        """
-
-        self.runtime.increment_pc()
-        
-        def check(v, a, b, c):
-            if v.value != 0:
-                raise Exception("TripleTest failed - The two triples were inconsistent.")
-            return (a, b, c)
-        
-        def compute_value(r, a, b, c, x, y, z):
-            l = self.runtime._cmul(r, x, self.Zp)
-            m = self.runtime._cmul(r, y, self.Zp)
-            k = self.runtime._cmul(r*r, z, self.Zp)
-            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
-            v = self.runtime.open(v)
-            v.addCallback(check, a, b, c)
-            return v
-
-        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier, self.u_bound, self.alpha)
-        
-        random_shares = gen.generate_random_shares(n)
-
-        results = [Deferred() for _ in xrange(n)]
-        
-        triples = self._generate_passive_triples(2 * n)
-
-        for inx in xrange(n):
-            a = triples[inx]
-            b = triples[inx + 2 * n]
-            c = triples[inx + 4 * n]
-            x = triples[inx + n]
-            y = triples[inx + 3 * n]
-            z = triples[inx + 5 * n]
-            r = self.runtime.open(random_shares[inx])
-            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
-            r.chainDeferred(results[inx])
-        return results
-          
-        # TODO: Do some ZK stuff.
-
-    def _generate_passive_triples(self, n):
-        """Generates and returns a list of 3n shares corresponding to
-        n passive tuples. The first n are the a's, then comes n b's
-        followed by n c's.
-        
-        Consistency is only guaranteed if all players follow the protool.
-        """
-
-        self.runtime.increment_pc()
-        
-        gen = PartialShareGenerator(self.Zp, self.runtime, self.random, self.paillier)
-        partial_shares = []
-        for _ in xrange(2 * n):
-             partial_shares.append(gen.generate_share(self.random.randint(0, self.Zp.modulus - 1)))
-
-
-        partial_shares_c = self._full_mul(partial_shares[0:n], partial_shares[n:2*n])
-
-        full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, partial_shares + partial_shares_c)
-
-        return full_shares  
-
-        # for player i:
-        #     receive c from player i and set 
-        #         m^i=Decrypt(c)
-    
-    def _mul(self, inx, jnx, ais=None, cjs=None):
-        """Multiply each of the field elements in *ais* with the
-        corresponding encrypted elements in *cjs*.
-        
-        Returns a deferred which will yield a list of PartialShareContents.
-        """
-        CKIND = 1
-        DiKIND = 2
-        DjKIND = 3
-        
-        self.runtime.increment_pc()
-
-        pc = tuple(self.runtime.program_counter)
-
-        deferreds = []
-        zis = []
-        if self.runtime.id == inx:
-            Nj_square = self.paillier.get_modulus_square(jnx)
-            cs = []
-            dis = []
-            for ai, cj in zip(ais, cjs):
-                u = rand.randint(0, self.u_bound)
-                Ej_u = self.paillier.encrypt(u, jnx)
-                cs.append( (pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
-                zi = self.Zp(-u)
-                zis.append(zi)
-                dis.append(self.paillier.encrypt(zi.value, inx))
-            self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
-
-            for player_id in self.runtime.players:
-                self.runtime.protocols[player_id].sendData(pc, DiKIND, str(dis))
-
-        if self.runtime.id == jnx:
-            cs = Deferred()
-            self.runtime._expect_data(inx, CKIND, cs)
-            def decrypt(cs, pc, zis):
-                zjs = []
-                djs = []
-                for c in eval(cs):
-                    t = self.paillier.decrypt(c)
-                    zj = self.Zp(t)
-                    zjs.append(zj)
-                    djs.append(self.paillier.encrypt(zj.value, jnx))
-                for player_id in self.runtime.players:
-                    self.runtime.protocols[player_id].sendData(pc, DjKIND, str(djs))
-                if not zis == []:
-                    return [x + y for x, y in zip(zis, zjs)]
-                else:
-                    return zjs 
-            cs.addCallback(decrypt, pc, zis)
-            deferreds.append(cs)
-        else:
-            zis_deferred = Deferred()
-            zis_deferred.callback(zis)
-            deferreds.append(zis_deferred)
-
-        dis = Deferred()
-        self.runtime._expect_data(inx, DiKIND, dis)
-        djs = Deferred()
-        self.runtime._expect_data(jnx, DjKIND, djs)
-
-        deferreds.append(dis)
-        deferreds.append(djs)
-        r = gatherResults(deferreds)
-        def wrap((values, dis, djs), inx, jnx):
-            dis = eval(dis)
-            djs = eval(djs)
-            n_square_i = self.paillier.get_modulus_square(inx)
-            n_square_j = self.paillier.get_modulus_square(jnx)
-            N_squared_list = [self.paillier.get_modulus_square(player_id) for player_id in self.runtime.players]
-            ps = []
-            for v, di, dj in itertools.izip_longest(values, dis, djs, fillvalue=self.Zp(0)):
-                value = v 
-                enc_shares = len(self.runtime.players) * [1]
-                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
-                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
-                ps.append(PartialShareContents(value, enc_shares, N_squared_list))
-            return ps
-        r.addCallback(wrap, inx, jnx)
-        return r
-
-    def _full_mul(self, a, b):
-        """Multiply each of the PartialShares in the list *a* with the
-        corresponding PartialShare in the list *b*.
-        
-        Returns a deferred which will yield a list of PartialShares.
-        """
-        self.runtime.increment_pc()
-        
-        def do_full_mul(shares, result_shares):
-            """Share content belonging to ai, bi are at:
-            shares[i], shares[len(shares) + i].
-            """
-            deferreds = []
-            len_shares = len(shares)
-            a_values = [s.value for s in shares[0:len_shares/2]]
-            b_enc_shares = []
-            for inx in self.runtime.players:              
-                b_enc_shares.append([s.enc_shares[inx - 1] for s in shares[len_shares/2:]])
-            for inx in xrange(0, len(self.runtime.players)):
-                for jnx in xrange(0, len(self.runtime.players)):
-                    deferreds.append(self._mul(inx + 1,
-                                               jnx + 1,
-                                               a_values,
-                                               b_enc_shares[jnx]))
-                        
-            def compute_shares(partialShareContents, len_shares, result_shares):
-                num_players = len(self.runtime.players)
-                pcs = len(partialShareContents[0]) * [None]
-                for ps in partialShareContents:
-                    for inx in xrange(0, len(ps)):
-                        if pcs[inx] == None:
-                            pcs[inx] = ps[inx]
-                        else:
-                            pcs[inx] += ps[inx]
-                for p, s in zip(pcs, result_shares):
-                    s.callback(p)
-                return None
-            d = gatherResults(deferreds)
-            d.addCallback(compute_shares, len_shares, result_shares)
-            return d
-        result_shares = [Share(self.runtime, self.Zp) for x in a]
-        self.runtime.schedule_callback(gatherResults(a + b),
-                                       do_full_mul,
-                                       result_shares)
-        return result_shares
-
-
-# TODO: Represent all numbers by GF objects, Zp, Zn, etc.
-# E.g. paillier encrypt should return Zn^2 elms and decrypt should
-# return Zp elements.
--- a/viff/test/test_bedoza_runtime.py	Fri Jul 23 11:18:04 2010 +0200
+++ b/viff/test/test_bedoza_runtime.py	Fri Jul 23 13:17:48 2010 +0200
@@ -22,7 +22,9 @@
 from viff.test.util import RuntimeTestCase, protocol
 from viff.runtime import gather_shares, Share
 from viff.config import generate_configs
-from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaShareContents, BeDOZaKeyList, BeDOZaMACList
+from viff.bedoza.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaShareContents
+from viff.bedoza.keylist import BeDOZaKeyList
+from viff.bedoza.maclist import BeDOZaMACList
 from viff.field import FieldElement, GF
 from viff.util import rand
 
--- a/viff/test/test_bedoza_triple.py	Fri Jul 23 11:18:04 2010 +0200
+++ b/viff/test/test_bedoza_triple.py	Fri Jul 23 13:17:48 2010 +0200
@@ -29,10 +29,11 @@
 from viff.constants import TEXT
 from viff.runtime import gather_shares, Share
 from viff.config import generate_configs
-from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaKeyList
 
-from viff.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier, PartialShareGenerator, ShareGenerator
-from viff.bedoza_triple import _send, _convolute, _convolute_gf_elm, add_macs
+from viff.bedoza.bedoza import BeDOZaRuntime, BeDOZaShare
+from viff.bedoza.keylist import BeDOZaKeyList
+from viff.bedoza.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier, PartialShareGenerator, ShareGenerator
+from viff.bedoza.bedoza_triple import _send, _convolute, _convolute_gf_elm, add_macs
 
 from viff.field import FieldElement, GF
 from viff.config import generate_configs