viff

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 diff
     1.1 --- a/viff/bedoza.py	Fri Jul 23 11:18:04 2010 +0200
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,561 +0,0 @@
     1.4 -# Copyright 2010 VIFF Development Team.
     1.5 -#
     1.6 -# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.7 -#
     1.8 -# VIFF is free software: you can redistribute it and/or modify it
     1.9 -# under the terms of the GNU Lesser General Public License (LGPL) as
    1.10 -# published by the Free Software Foundation, either version 3 of the
    1.11 -# License, or (at your option) any later version.
    1.12 -#
    1.13 -# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.14 -# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.15 -# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.16 -# Public License for more details.
    1.17 -#
    1.18 -# You should have received a copy of the GNU Lesser General Public
    1.19 -# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.20 -
    1.21 -"""Full threshold actively secure runtime."""
    1.22 -
    1.23 -from twisted.internet.defer import Deferred, gatherResults, succeed
    1.24 -
    1.25 -from viff.util import rand
    1.26 -from viff.runtime import Share, ShareList, gather_shares
    1.27 -from viff.field import FieldElement
    1.28 -from viff.constants import TEXT
    1.29 -from viff.simplearithmetic import SimpleArithmeticRuntime
    1.30 -
    1.31 -from hash_broadcast import HashBroadcastMixin
    1.32 -
    1.33 -class BeDOZaException(Exception):
    1.34 -    pass
    1.35 -
    1.36 -class BeDOZaShareContents(object):
    1.37 -
    1.38 -    def __init__(self, value, keyList, macs):
    1.39 -        self.value = value
    1.40 -        self.keyList = keyList
    1.41 -        self.macs = macs
    1.42 -
    1.43 -    def get_value(self):
    1.44 -        return self.value
    1.45 -
    1.46 -    def get_keys(self):
    1.47 -        return self.keyList
    1.48 -
    1.49 -    def get_macs(self):
    1.50 -        return self.macs
    1.51 -
    1.52 -    def get_mac(self, inx):
    1.53 -        return self.macs.get_mac(inx)
    1.54 -
    1.55 -    def __add__(self, other):
    1.56 -        zi = self.value + other.value
    1.57 -        zks = self.keyList + other.keyList
    1.58 -        zms = self.macs + other.macs
    1.59 -        return BeDOZaShareContents(zi, zks, zms)
    1.60 -
    1.61 -    def __sub__(self, other):
    1.62 -        zi = self.value - other.value
    1.63 -        zks = self.keyList - other.keyList
    1.64 -        zms = self.macs - other.macs
    1.65 -        return BeDOZaShareContents(zi, zks, zms)
    1.66 -
    1.67 -    def add_public(self, c, my_id):
    1.68 -        if my_id == 1:
    1.69 -            self.value = self.value + c
    1.70 -        self.keyList.set_key(0, self.keyList.get_key(0) - self.keyList.alpha * c)
    1.71 -        return self
    1.72 -    
    1.73 -    def sub_public(self, c, my_id):
    1.74 -        if my_id == 1:
    1.75 -            self.value = self.value - c
    1.76 -        self.keyList.set_key(0, self.keyList.get_key(0) + self.keyList.alpha * c)
    1.77 -        return self
    1.78 -
    1.79 -    def cmul(self, c):
    1.80 -        zi = c * self.value
    1.81 -        zks = self.keyList.cmul(c)
    1.82 -        zms = self.macs.cmul(c)
    1.83 -        return BeDOZaShareContents(zi, zks, zms)
    1.84 -
    1.85 -    def __str__(self):
    1.86 -        return "(%s, %s, %s)" % (str(self.value), str(self.keyList), str(self.macs))
    1.87 -    
    1.88 -class BeDOZaShare(Share):
    1.89 -    """A share in the BeDOZa runtime.
    1.90 -
    1.91 -    A share in the BeDOZa runtime is a pair ``(x_i, authentication_codes)`` of:
    1.92 -
    1.93 -    - A share of a number, ``x_i``
    1.94 -    - A list of authentication_codes, ``authentication_codes``
    1.95 -
    1.96 -    The :class:`Runtime` operates on shares, represented by this class.
    1.97 -    Shares are asynchronous in the sense that they promise to attain a
    1.98 -    value at some point in the future.
    1.99 -
   1.100 -    Shares overload the arithmetic operations so that ``x = a + b``
   1.101 -    will create a new share *x*, which will eventually contain the
   1.102 -    sum of *a* and *b*. Each share is associated with a
   1.103 -    :class:`Runtime` and the arithmetic operations simply call back to
   1.104 -    that runtime.
   1.105 -    """
   1.106 -
   1.107 -    def __init__(self, runtime, field, value=None, keyList=None, authentication_codes=None):
   1.108 -        if value == None and keyList == None and authentication_codes == None:
   1.109 -            Share.__init__(self, runtime, field)
   1.110 -        else:
   1.111 -            Share.__init__(self, runtime, field, BeDOZaShareContents(value, keyList, authentication_codes))
   1.112 -        
   1.113 -
   1.114 -class BeDOZaKeyList(object):
   1.115 -    """A list of keys, one for each player.
   1.116 -
   1.117 -    We assume that the key for player *i* is stored in
   1.118 -    location *i - 1* in the *keys* list given as argument to the constructor.
   1.119 -    """
   1.120 -
   1.121 -    def __init__(self, alpha, keys):
   1.122 -        self.alpha = alpha
   1.123 -        self.keys = keys
   1.124 -
   1.125 -    def get_key(self, player_id):
   1.126 -        return self.keys[player_id]
   1.127 -
   1.128 -    def set_key(self, player_id, v):
   1.129 -        self.keys[player_id] = v
   1.130 -
   1.131 -    def cmul(self, c):
   1.132 -        return BeDOZaKeyList(self.alpha, map(lambda k: c * k, self.keys))
   1.133 -
   1.134 -    def __add__(self, other):
   1.135 -        """Addition."""
   1.136 -        assert self.alpha == other.alpha
   1.137 -        keys = []
   1.138 -        for k1, k2 in zip(self.keys, other.keys):
   1.139 -            keys.append(k1 + k2)
   1.140 -        return BeDOZaKeyList(self.alpha, keys)
   1.141 -
   1.142 -    def __sub__(self, other):
   1.143 -        """Subtraction."""
   1.144 -        assert self.alpha == other.alpha
   1.145 -        keys = []
   1.146 -        for k1, k2 in zip(self.keys, other.keys):
   1.147 -            keys.append(k1 - k2)
   1.148 -        return BeDOZaKeyList(self.alpha, keys)
   1.149 -
   1.150 -    def __eq__(self, other):
   1.151 -        return self.alpha == other.alpha and self.keys == other.keys
   1.152 -
   1.153 -    def __str__(self):
   1.154 -        return "(%s, %s)" % (self.alpha, str(self.keys))
   1.155 -
   1.156 -    def __repr__(self):
   1.157 -        return str(self)
   1.158 -    
   1.159 -class BeDOZaMACList(object):
   1.160 -
   1.161 -    def __init__(self, macs):
   1.162 -        self.macs = macs
   1.163 -
   1.164 -    def get_macs(self):
   1.165 -        return self.macs
   1.166 -
   1.167 -    def get_mac(self, inx):
   1.168 -        return self.macs[inx]
   1.169 -
   1.170 -    def cmul(self, c):
   1.171 -        return BeDOZaMACList(map(lambda m: c * m, self.macs))
   1.172 -        
   1.173 -    def __add__(self, other):
   1.174 -        """Addition."""
   1.175 -        macs = []
   1.176 -        for c1, c2 in zip(self.macs, other.macs):
   1.177 -            macs.append(c1 + c2)
   1.178 -        return BeDOZaMACList(macs)
   1.179 -
   1.180 -    def __sub__(self, other):
   1.181 -        """Subtraction."""
   1.182 -        macs = []
   1.183 -        for c1, c2 in zip(self.macs, other.macs):
   1.184 -            macs.append(c1 - c2)
   1.185 -        return BeDOZaMACList(macs)
   1.186 -
   1.187 -    def __eq__(self, other):
   1.188 -        return self.macs == other.macs
   1.189 -
   1.190 -    def __str__(self):
   1.191 -        return str(self.macs)
   1.192 -
   1.193 -    def __repr__(self):
   1.194 -        return str(self)
   1.195 -    
   1.196 -class RandomShareGenerator:
   1.197 -    """ TODO: This is a dummy implementation, and should be replaced with proper code."""
   1.198 -    
   1.199 -    def generate_random_shares(self, field, number_of_shares):
   1.200 -        self.init_keys(field)
   1.201 -        shares = []
   1.202 -        for i in xrange(0, number_of_shares):
   1.203 -            v = field(self.id)
   1.204 -            shares.append(self.generate_share(field, v))
   1.205 -        return shares
   1.206 -
   1.207 -    def generate_share(self, field, value):
   1.208 -        my_keys = self.generate_keys(field)
   1.209 -        macs = self.generate_auth_codes(self.id, value)
   1.210 -        return BeDOZaShare(self, field, value, my_keys, macs)
   1.211 -
   1.212 -    def generate_auth_codes(self, playerId, value):
   1.213 -        keys = map(lambda (alpha, akeys): (alpha, akeys[playerId - 1]), self.keys.values())
   1.214 -        macs = self.authentication_codes(keys, value)
   1.215 -        return macs
   1.216 -
   1.217 -    def authentication_codes(self, keys, v):
   1.218 -        macs = []
   1.219 -        for alpha, beta in keys:
   1.220 -            macs.append(alpha * v + beta)
   1.221 -        return BeDOZaMACList(macs)
   1.222 -
   1.223 -    def generate_keys(self, field):
   1.224 -        alpha, betas = self.get_keys()
   1.225 -        return BeDOZaKeyList(alpha, betas)
   1.226 -
   1.227 -    def init_keys(self, field):
   1.228 -
   1.229 -        self.keys = {}
   1.230 -        for player_id in self.players:
   1.231 -            betas = [field(56387295767672113),
   1.232 -                     field(89238458945400961),
   1.233 -                     field(12340004554789025),
   1.234 -                     field(12907853897457058),
   1.235 -                     field(90457903592570134),
   1.236 -                     field(56256262346343232),
   1.237 -                     field(23897437894556562),
   1.238 -                     field(90297849575975574)]
   1.239 -            self.keys[player_id] = (field(player_id), betas)
   1.240 -
   1.241 -    def get_keys(self):   
   1.242 -        return self.keys[self.id]
   1.243 -
   1.244 -class BeDOZaMixin(HashBroadcastMixin, RandomShareGenerator):
   1.245 - 
   1.246 -    def MAC(self, alpha, beta, v):
   1.247 -        return alpha * v + beta
   1.248 -
   1.249 -    def random_share(self, field):
   1.250 -        """Retrieve a previously generated random share in the field, field.
   1.251 -
   1.252 -        If no more shares are left, generate self.random_share_number new ones.
   1.253 -        """
   1.254 -        if len(self.random_shares) == 0:
   1.255 -            self.random_shares = self.generate_random_shares(field, self.random_share_number)
   1.256 -
   1.257 -        return self.random_shares.pop()
   1.258 -
   1.259 -    def output(self, share, receivers=None):
   1.260 -        return self.open(share, receivers)
   1.261 -
   1.262 -    def open_multiple_values(self, shares, receivers=None):
   1.263 -        """Share reconstruction of a list of shares."""
   1.264 -        assert shares
   1.265 -        # all players receive result by default
   1.266 -        if receivers is None:
   1.267 -            receivers = self.players.keys()
   1.268 -
   1.269 -        field = shares[0].field
   1.270 -
   1.271 -        self.increment_pc()
   1.272 -
   1.273 -        def recombine_value(player_shares_codes, keyLists, num_shares):
   1.274 -            def check(ls, x, isOK):
   1.275 -                true_str = str(True)
   1.276 -                if reduce(lambda x, y: true_str == y, ls):
   1.277 -                    return x
   1.278 -                else:
   1.279 -                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   1.280 -
   1.281 -            n = len(self.players)
   1.282 -            alpha = keyLists[0].alpha
   1.283 -
   1.284 -            values = num_shares * [0]
   1.285 -            isOK = num_shares * [True]
   1.286 -            for iny in xrange(num_shares):
   1.287 -                keyList = keyLists[iny]
   1.288 -                for inx, xs in enumerate(player_shares_codes):
   1.289 -                    xi, mi = xs[iny]
   1.290 -                    beta = keyList.get_key(inx)
   1.291 -                    values[iny] += xi
   1.292 -                    mi_prime = self.MAC(alpha, beta, xi)
   1.293 -                    isOK[iny] = isOK[iny] and mi == mi_prime
   1.294 -
   1.295 -            isOK = reduce(lambda x, y: True == y, isOK)
   1.296 -            ds = self.broadcast(self.players.keys(), self.players.keys(),
   1.297 -                                str(isOK))
   1.298 -            ds = gatherResults(ds)
   1.299 -            ds.addCallbacks(check, self.error_handler, callbackArgs=(values, isOK))
   1.300 -            return ds
   1.301 -        
   1.302 -        def exchange(ls, receivers):
   1.303 -            # Send share to all receivers.
   1.304 -            pc = tuple(self.program_counter)
   1.305 -            keyLists = []
   1.306 -            for other_id in receivers:
   1.307 -                message_string = ""
   1.308 -                for inx, beDOZaContents in enumerate(ls):
   1.309 -                    keyLists.append(beDOZaContents.get_keys())
   1.310 -                    message_string += "%s:%s;" % \
   1.311 -                           (beDOZaContents.get_value().value, beDOZaContents.get_mac(other_id - 1).value)
   1.312 -                self.protocols[other_id].sendData(pc, TEXT, message_string)
   1.313 -
   1.314 -            if self.id in receivers:
   1.315 -                def deserialize(s):
   1.316 -                    def field_long(x):
   1.317 -                        return field(long(x))
   1.318 -                    xs = s[0:-1].split(';')
   1.319 -                    ys = [x.split(':') for x in xs]
   1.320 -                    return [map(field_long, xs) for xs in ys]
   1.321 -                num_players = len(self.players.keys())
   1.322 -                values = num_players * [None]
   1.323 -                for inx, other_id in enumerate(self.players.keys()):
   1.324 -                    d = Deferred()
   1.325 -                    d.addCallbacks(deserialize, self.error_handler)
   1.326 -                    self._expect_data(other_id, TEXT, d)
   1.327 -                    values[inx] = d
   1.328 -                result = gatherResults(values)
   1.329 -                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(keyLists, len(shares)))
   1.330 -                return result
   1.331 -
   1.332 -        result = gather_shares(shares)
   1.333 -        self.schedule_callback(result, exchange, receivers)
   1.334 -        result.addErrback(self.error_handler)
   1.335 -
   1.336 -        # do actual communication
   1.337 -        self.activate_reactor()
   1.338 -
   1.339 -        if self.id in receivers:
   1.340 -            return result
   1.341 -
   1.342 -    def open_two_values(self, share_a, share_b, receivers=None):
   1.343 -        """Share reconstruction of a list of shares."""
   1.344 -        assert isinstance(share_a, Share)
   1.345 -        assert isinstance(share_b, Share)
   1.346 -        # all players receive result by default
   1.347 -        if receivers is None:
   1.348 -            receivers = self.players.keys()
   1.349 -
   1.350 -        field = share_a.field
   1.351 -
   1.352 -        self.increment_pc()
   1.353 -
   1.354 -        def recombine_value(shares_codes, keyList_a, keyList_b):
   1.355 -            def check(ls, a, b, isOK):
   1.356 -                true_str = str(True)
   1.357 -                if reduce(lambda x, y: true_str == y, ls):
   1.358 -                    return a, b
   1.359 -                else:
   1.360 -                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   1.361 -
   1.362 -            n = len(self.players)
   1.363 -            alpha_a = keyList_a.alpha
   1.364 -            alpha_b = keyList_b.alpha
   1.365 -
   1.366 -            a = 0
   1.367 -            b = 0
   1.368 -            isOK = True
   1.369 -            for inx in xrange(0, n):
   1.370 -                ai = shares_codes[inx]
   1.371 -                bi = shares_codes[2*n + inx]
   1.372 -                mi_a = shares_codes[n + inx]
   1.373 -                mi_b = shares_codes[3*n + inx]
   1.374 -                beta_a = keyList_a.get_key(inx)
   1.375 -                beta_b = keyList_b.get_key(inx)
   1.376 -                a += ai
   1.377 -                b += bi
   1.378 -                mi_prime = self.MAC(alpha_a, beta_a, ai)
   1.379 -                isOK = isOK and mi_a == mi_prime
   1.380 -                mi_prime = self.MAC(alpha_b, beta_b, bi)
   1.381 -                isOK = isOK and mi_b == mi_prime
   1.382 -                
   1.383 -            ds = self.broadcast(self.players.keys(), self.players.keys(),
   1.384 -                                str(isOK))
   1.385 -            ds = gatherResults(ds)
   1.386 -            ds.addCallbacks(check, self.error_handler, callbackArgs=(a, b, isOK))
   1.387 -            return ds
   1.388 -        
   1.389 -        def exchange((a, b), receivers):
   1.390 -            # Send share to all receivers.
   1.391 -            pc = tuple(self.program_counter)
   1.392 -            for other_id in receivers:
   1.393 -                self.protocols[other_id].sendShare(pc, a.get_value())
   1.394 -                self.protocols[other_id].sendShare(pc, a.get_mac(other_id - 1))
   1.395 -                self.protocols[other_id].sendShare(pc, b.get_value())
   1.396 -                self.protocols[other_id].sendShare(pc, b.get_mac(other_id - 1))
   1.397 -                
   1.398 -            if self.id in receivers:
   1.399 -                num_players = len(self.players.keys())
   1.400 -                values_a = num_players * [None]
   1.401 -                codes_a = num_players * [None]
   1.402 -                values_b = num_players * [None]
   1.403 -                codes_b = num_players * [None]
   1.404 -                for inx, other_id in enumerate(self.players.keys()):
   1.405 -                    values_a[inx] =  self._expect_share(other_id, field)
   1.406 -                    codes_a[inx] = self._expect_share(other_id, field)
   1.407 -                    values_b[inx] =  self._expect_share(other_id, field)
   1.408 -                    codes_b[inx] = self._expect_share(other_id, field)
   1.409 -                result = gatherResults(values_a + codes_a + values_b + codes_b)
   1.410 -                self.schedule_callback(result, recombine_value, a.get_keys(), b.get_keys())
   1.411 -                return result
   1.412 -
   1.413 -        result = gather_shares([share_a, share_b])
   1.414 -        self.schedule_callback(result, exchange, receivers)
   1.415 -        result.addErrback(self.error_handler)
   1.416 -
   1.417 -        # do actual communication
   1.418 -        self.activate_reactor()
   1.419 -
   1.420 -        if self.id in receivers:
   1.421 -            return result
   1.422 -
   1.423 -    def open(self, share, receivers=None):
   1.424 -        """Share reconstruction."""
   1.425 -        assert isinstance(share, Share)
   1.426 -        # all players receive result by default
   1.427 -        if receivers is None:
   1.428 -            receivers = self.players.keys()
   1.429 -
   1.430 -        field = share.field
   1.431 -
   1.432 -        self.increment_pc()
   1.433 -
   1.434 -        def recombine_value(shares_codes, keyList):
   1.435 -            isOK = True
   1.436 -            n = len(self.players)
   1.437 -            alpha = keyList.alpha
   1.438 -            x = 0
   1.439 -            for inx in xrange(0, n):
   1.440 -                xi = shares_codes[inx]
   1.441 -                mi = shares_codes[n + inx]
   1.442 -                beta = keyList.get_key(inx)
   1.443 -                x += xi
   1.444 -                mi_prime = self.MAC(alpha, beta, xi)
   1.445 -                isOK = isOK and mi == mi_prime
   1.446 -            def check(ls, x, isOK):
   1.447 -                true_str = str(True)
   1.448 -                if reduce(lambda x, y: true_str == y, ls):
   1.449 -                    return x
   1.450 -                else:
   1.451 -                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   1.452 -                
   1.453 -            ds = self.broadcast(self.players.keys(), self.players.keys(),
   1.454 -                                str(isOK))
   1.455 -            ds = gatherResults(ds)
   1.456 -            ds.addCallbacks(check, self.error_handler, callbackArgs=(x,isOK))
   1.457 -            return ds
   1.458 -
   1.459 -        def exchange(shareContent, receivers):
   1.460 -            # Send share to all receivers.
   1.461 -            pc = tuple(self.program_counter)
   1.462 -            for other_id in receivers:
   1.463 -                self.protocols[other_id].sendShare(pc, shareContent.get_value())
   1.464 -                self.protocols[other_id].sendShare(pc, shareContent.get_mac(other_id - 1))
   1.465 -            if self.id in receivers:
   1.466 -                num_players = len(self.players.keys())
   1.467 -                values = num_players * [None]
   1.468 -                codes = num_players * [None]
   1.469 -                for inx, other_id in enumerate(self.players.keys()):
   1.470 -                    values[inx] =  self._expect_share(other_id, field)
   1.471 -                    codes[inx] = self._expect_share(other_id, field)
   1.472 -                result = gatherResults(values + codes)
   1.473 -                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(shareContent.get_keys(),))
   1.474 -                return result
   1.475 -
   1.476 -        result = share.clone()
   1.477 -        self.schedule_callback(result, exchange, receivers)
   1.478 -        result.addErrback(self.error_handler)
   1.479 -
   1.480 -        # do actual communication
   1.481 -        self.activate_reactor()
   1.482 -
   1.483 -        if self.id in receivers:
   1.484 -            return result
   1.485 -
   1.486 -    def _plus_public(self, x, c, field):
   1.487 -        x = x.add_public(c, self.id)
   1.488 -        return BeDOZaShare(self, field, x.get_value(), x.get_keys(), x.get_macs())
   1.489 -
   1.490 -    def _plus(self, (x, y), field):
   1.491 -        """Addition of share-contents *x* and *y*."""
   1.492 -        return x + y
   1.493 -
   1.494 -    def _minus_public_right(self, x, c, field):
   1.495 -        z = self._minus_public_right_without_share(x, c, field)
   1.496 -        return BeDOZaShare(self, field, z.get_value(), z.get_keys(), z.get_macs())
   1.497 -
   1.498 -    def _minus_public_right_without_share(self, x, c, field):
   1.499 -        return x.sub_public(c, self.id)
   1.500 -
   1.501 -    def _wrap_in_share(self, shareContents, field):
   1.502 -        return BeDOZaShare(self, field,
   1.503 -                           shareContents.get_value(),
   1.504 -                           shareContents.get_keys(),
   1.505 -                           shareContents.get_macs())
   1.506 -
   1.507 -    def _minus_public_left(self, x, c, field):
   1.508 -        y = self._constant_multiply(x, field(-1))
   1.509 -        return self._plus_public(y, c, field)
   1.510 -    
   1.511 -    def _minus(self, (x, y), field):
   1.512 -        """Subtraction of share-tuples *x* and *y*."""
   1.513 -        return x - y
   1.514 -
   1.515 -    def _constant_multiply(self, x, c):
   1.516 -        """Multiplication of a share-tuple with a constant c."""
   1.517 -        assert(isinstance(c, FieldElement))
   1.518 -        return x.cmul(c)
   1.519 -
   1.520 -    def _get_triple(self, field):
   1.521 -        """ TODO: This is a dummy implementation, and should be replaced with proper code."""
   1.522 -        self.init_keys(field)
   1.523 -        a, b, c = 0, 0, 0
   1.524 -        share_a = field(2)
   1.525 -        share_b = field(4)
   1.526 -        n = len(self.players)
   1.527 -        share_c = n * share_a * share_b
   1.528 -        for playerid in self.players.keys():
   1.529 -            if self.id == playerid:
   1.530 -                triple_a = self.generate_share(field, share_a)
   1.531 -                a += share_a.value
   1.532 -                triple_b = self.generate_share(field, share_b)
   1.533 -                b += share_b.value
   1.534 -                triple_c = self.generate_share(field, share_c)
   1.535 -                c += share_c.value
   1.536 -        return [triple_a, triple_b, triple_c], False
   1.537 -
   1.538 -
   1.539 -class BeDOZaRuntime(BeDOZaMixin, SimpleArithmeticRuntime):
   1.540 -    """The BeDOZa runtime.
   1.541 -
   1.542 -    The runtime is used for sharing values (:meth:`secret_share` or
   1.543 -    :meth:`shift`) into :class:`BeDOZaShare` object and opening such
   1.544 -    shares (:meth:`open`) again. Calculations on shares is normally
   1.545 -    done through overloaded arithmetic operations, but it is also
   1.546 -    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
   1.547 -    prefers.
   1.548 -
   1.549 -    Each player in the protocol uses a :class:`~viff.runtime.Runtime`
   1.550 -    object. To create an instance and connect it correctly with the
   1.551 -    other players, please use the :func:`~viff.runtime.create_runtime`
   1.552 -    function instead of instantiating a Runtime directly. The
   1.553 -    :func:`~viff.runtime.create_runtime` function will take care of
   1.554 -    setting up network connections and return a :class:`Deferred`
   1.555 -    which triggers with the :class:`~viff.runtime.Runtime` object when
   1.556 -    it is ready.
   1.557 -    """
   1.558 -
   1.559 -    def __init__(self, player, threshold=None, options=None):
   1.560 -        """Initialize runtime."""
   1.561 -        SimpleArithmeticRuntime.__init__(self, player, threshold, options)
   1.562 -        self.threshold = self.num_players - 1
   1.563 -        self.random_share_number = 100
   1.564 -        self.random_shares = []
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/viff/bedoza/__init__.py	Fri Jul 23 13:17:48 2010 +0200
     2.3 @@ -0,0 +1,16 @@
     2.4 +# Copyright 2010 VIFF Development Team.
     2.5 +#
     2.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     2.7 +#
     2.8 +# VIFF is free software: you can redistribute it and/or modify it
     2.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    2.10 +# published by the Free Software Foundation, either version 3 of the
    2.11 +# License, or (at your option) any later version.
    2.12 +#
    2.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    2.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    2.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    2.16 +# Public License for more details.
    2.17 +#
    2.18 +# You should have received a copy of the GNU Lesser General Public
    2.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/viff/bedoza/bedoza.py	Fri Jul 23 13:17:48 2010 +0200
     3.3 @@ -0,0 +1,481 @@
     3.4 +# Copyright 2010 VIFF Development Team.
     3.5 +#
     3.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     3.7 +#
     3.8 +# VIFF is free software: you can redistribute it and/or modify it
     3.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    3.10 +# published by the Free Software Foundation, either version 3 of the
    3.11 +# License, or (at your option) any later version.
    3.12 +#
    3.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    3.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    3.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    3.16 +# Public License for more details.
    3.17 +#
    3.18 +# You should have received a copy of the GNU Lesser General Public
    3.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    3.20 +
    3.21 +"""Full threshold actively secure runtime."""
    3.22 +
    3.23 +from twisted.internet.defer import Deferred, gatherResults, succeed
    3.24 +
    3.25 +from viff.util import rand
    3.26 +from viff.runtime import Share, ShareList, gather_shares
    3.27 +from viff.field import FieldElement
    3.28 +from viff.constants import TEXT
    3.29 +from viff.simplearithmetic import SimpleArithmeticRuntime
    3.30 +
    3.31 +from viff.hash_broadcast import HashBroadcastMixin
    3.32 +
    3.33 +from viff.bedoza.keylist import BeDOZaKeyList
    3.34 +from viff.bedoza.maclist import BeDOZaMACList
    3.35 +
    3.36 +class BeDOZaException(Exception):
    3.37 +    pass
    3.38 +
    3.39 +class BeDOZaShareContents(object):
    3.40 +
    3.41 +    def __init__(self, value, keyList, macs):
    3.42 +        self.value = value
    3.43 +        self.keyList = keyList
    3.44 +        self.macs = macs
    3.45 +
    3.46 +    def get_value(self):
    3.47 +        return self.value
    3.48 +
    3.49 +    def get_keys(self):
    3.50 +        return self.keyList
    3.51 +
    3.52 +    def get_macs(self):
    3.53 +        return self.macs
    3.54 +
    3.55 +    def get_mac(self, inx):
    3.56 +        return self.macs.get_mac(inx)
    3.57 +
    3.58 +    def __add__(self, other):
    3.59 +        zi = self.value + other.value
    3.60 +        zks = self.keyList + other.keyList
    3.61 +        zms = self.macs + other.macs
    3.62 +        return BeDOZaShareContents(zi, zks, zms)
    3.63 +
    3.64 +    def __sub__(self, other):
    3.65 +        zi = self.value - other.value
    3.66 +        zks = self.keyList - other.keyList
    3.67 +        zms = self.macs - other.macs
    3.68 +        return BeDOZaShareContents(zi, zks, zms)
    3.69 +
    3.70 +    def add_public(self, c, my_id):
    3.71 +        if my_id == 1:
    3.72 +            self.value = self.value + c
    3.73 +        self.keyList.set_key(0, self.keyList.get_key(0) - self.keyList.alpha * c)
    3.74 +        return self
    3.75 +    
    3.76 +    def sub_public(self, c, my_id):
    3.77 +        if my_id == 1:
    3.78 +            self.value = self.value - c
    3.79 +        self.keyList.set_key(0, self.keyList.get_key(0) + self.keyList.alpha * c)
    3.80 +        return self
    3.81 +
    3.82 +    def cmul(self, c):
    3.83 +        zi = c * self.value
    3.84 +        zks = self.keyList.cmul(c)
    3.85 +        zms = self.macs.cmul(c)
    3.86 +        return BeDOZaShareContents(zi, zks, zms)
    3.87 +
    3.88 +    def __str__(self):
    3.89 +        return "(%s, %s, %s)" % (str(self.value), str(self.keyList), str(self.macs))
    3.90 +    
    3.91 +class BeDOZaShare(Share):
    3.92 +    """A share in the BeDOZa runtime.
    3.93 +
    3.94 +    A share in the BeDOZa runtime is a pair ``(x_i, authentication_codes)`` of:
    3.95 +
    3.96 +    - A share of a number, ``x_i``
    3.97 +    - A list of authentication_codes, ``authentication_codes``
    3.98 +
    3.99 +    The :class:`Runtime` operates on shares, represented by this class.
   3.100 +    Shares are asynchronous in the sense that they promise to attain a
   3.101 +    value at some point in the future.
   3.102 +
   3.103 +    Shares overload the arithmetic operations so that ``x = a + b``
   3.104 +    will create a new share *x*, which will eventually contain the
   3.105 +    sum of *a* and *b*. Each share is associated with a
   3.106 +    :class:`Runtime` and the arithmetic operations simply call back to
   3.107 +    that runtime.
   3.108 +    """
   3.109 +
   3.110 +    def __init__(self, runtime, field, value=None, keyList=None, authentication_codes=None):
   3.111 +        if value == None and keyList == None and authentication_codes == None:
   3.112 +            Share.__init__(self, runtime, field)
   3.113 +        else:
   3.114 +            Share.__init__(self, runtime, field, BeDOZaShareContents(value, keyList, authentication_codes))
   3.115 +        
   3.116 +class RandomShareGenerator:
   3.117 +    """ TODO: This is a dummy implementation, and should be replaced with proper code."""
   3.118 +    
   3.119 +    def generate_random_shares(self, field, number_of_shares):
   3.120 +        self.init_keys(field)
   3.121 +        shares = []
   3.122 +        for i in xrange(0, number_of_shares):
   3.123 +            v = field(self.id)
   3.124 +            shares.append(self.generate_share(field, v))
   3.125 +        return shares
   3.126 +
   3.127 +    def generate_share(self, field, value):
   3.128 +        my_keys = self.generate_keys(field)
   3.129 +        macs = self.generate_auth_codes(self.id, value)
   3.130 +        return BeDOZaShare(self, field, value, my_keys, macs)
   3.131 +
   3.132 +    def generate_auth_codes(self, playerId, value):
   3.133 +        keys = map(lambda (alpha, akeys): (alpha, akeys[playerId - 1]), self.keys.values())
   3.134 +        macs = self.authentication_codes(keys, value)
   3.135 +        return macs
   3.136 +
   3.137 +    def authentication_codes(self, keys, v):
   3.138 +        macs = []
   3.139 +        for alpha, beta in keys:
   3.140 +            macs.append(alpha * v + beta)
   3.141 +        return BeDOZaMACList(macs)
   3.142 +
   3.143 +    def generate_keys(self, field):
   3.144 +        alpha, betas = self.get_keys()
   3.145 +        return BeDOZaKeyList(alpha, betas)
   3.146 +
   3.147 +    def init_keys(self, field):
   3.148 +
   3.149 +        self.keys = {}
   3.150 +        for player_id in self.players:
   3.151 +            betas = [field(56387295767672113),
   3.152 +                     field(89238458945400961),
   3.153 +                     field(12340004554789025),
   3.154 +                     field(12907853897457058),
   3.155 +                     field(90457903592570134),
   3.156 +                     field(56256262346343232),
   3.157 +                     field(23897437894556562),
   3.158 +                     field(90297849575975574)]
   3.159 +            self.keys[player_id] = (field(player_id), betas)
   3.160 +
   3.161 +    def get_keys(self):   
   3.162 +        return self.keys[self.id]
   3.163 +
   3.164 +class BeDOZaMixin(HashBroadcastMixin, RandomShareGenerator):
   3.165 + 
   3.166 +    def MAC(self, alpha, beta, v):
   3.167 +        return alpha * v + beta
   3.168 +
   3.169 +    def random_share(self, field):
   3.170 +        """Retrieve a previously generated random share in the field, field.
   3.171 +
   3.172 +        If no more shares are left, generate self.random_share_number new ones.
   3.173 +        """
   3.174 +        if len(self.random_shares) == 0:
   3.175 +            self.random_shares = self.generate_random_shares(field, self.random_share_number)
   3.176 +
   3.177 +        return self.random_shares.pop()
   3.178 +
   3.179 +    def output(self, share, receivers=None):
   3.180 +        return self.open(share, receivers)
   3.181 +
   3.182 +    def open_multiple_values(self, shares, receivers=None):
   3.183 +        """Share reconstruction of a list of shares."""
   3.184 +        assert shares
   3.185 +        # all players receive result by default
   3.186 +        if receivers is None:
   3.187 +            receivers = self.players.keys()
   3.188 +
   3.189 +        field = shares[0].field
   3.190 +
   3.191 +        self.increment_pc()
   3.192 +
   3.193 +        def recombine_value(player_shares_codes, keyLists, num_shares):
   3.194 +            def check(ls, x, isOK):
   3.195 +                true_str = str(True)
   3.196 +                if reduce(lambda x, y: true_str == y, ls):
   3.197 +                    return x
   3.198 +                else:
   3.199 +                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   3.200 +
   3.201 +            n = len(self.players)
   3.202 +            alpha = keyLists[0].alpha
   3.203 +
   3.204 +            values = num_shares * [0]
   3.205 +            isOK = num_shares * [True]
   3.206 +            for iny in xrange(num_shares):
   3.207 +                keyList = keyLists[iny]
   3.208 +                for inx, xs in enumerate(player_shares_codes):
   3.209 +                    xi, mi = xs[iny]
   3.210 +                    beta = keyList.get_key(inx)
   3.211 +                    values[iny] += xi
   3.212 +                    mi_prime = self.MAC(alpha, beta, xi)
   3.213 +                    isOK[iny] = isOK[iny] and mi == mi_prime
   3.214 +
   3.215 +            isOK = reduce(lambda x, y: True == y, isOK)
   3.216 +            ds = self.broadcast(self.players.keys(), self.players.keys(),
   3.217 +                                str(isOK))
   3.218 +            ds = gatherResults(ds)
   3.219 +            ds.addCallbacks(check, self.error_handler, callbackArgs=(values, isOK))
   3.220 +            return ds
   3.221 +        
   3.222 +        def exchange(ls, receivers):
   3.223 +            # Send share to all receivers.
   3.224 +            pc = tuple(self.program_counter)
   3.225 +            keyLists = []
   3.226 +            for other_id in receivers:
   3.227 +                message_string = ""
   3.228 +                for inx, beDOZaContents in enumerate(ls):
   3.229 +                    keyLists.append(beDOZaContents.get_keys())
   3.230 +                    message_string += "%s:%s;" % \
   3.231 +                           (beDOZaContents.get_value().value, beDOZaContents.get_mac(other_id - 1).value)
   3.232 +                self.protocols[other_id].sendData(pc, TEXT, message_string)
   3.233 +
   3.234 +            if self.id in receivers:
   3.235 +                def deserialize(s):
   3.236 +                    def field_long(x):
   3.237 +                        return field(long(x))
   3.238 +                    xs = s[0:-1].split(';')
   3.239 +                    ys = [x.split(':') for x in xs]
   3.240 +                    return [map(field_long, xs) for xs in ys]
   3.241 +                num_players = len(self.players.keys())
   3.242 +                values = num_players * [None]
   3.243 +                for inx, other_id in enumerate(self.players.keys()):
   3.244 +                    d = Deferred()
   3.245 +                    d.addCallbacks(deserialize, self.error_handler)
   3.246 +                    self._expect_data(other_id, TEXT, d)
   3.247 +                    values[inx] = d
   3.248 +                result = gatherResults(values)
   3.249 +                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(keyLists, len(shares)))
   3.250 +                return result
   3.251 +
   3.252 +        result = gather_shares(shares)
   3.253 +        self.schedule_callback(result, exchange, receivers)
   3.254 +        result.addErrback(self.error_handler)
   3.255 +
   3.256 +        # do actual communication
   3.257 +        self.activate_reactor()
   3.258 +
   3.259 +        if self.id in receivers:
   3.260 +            return result
   3.261 +
   3.262 +    def open_two_values(self, share_a, share_b, receivers=None):
   3.263 +        """Share reconstruction of a list of shares."""
   3.264 +        assert isinstance(share_a, Share)
   3.265 +        assert isinstance(share_b, Share)
   3.266 +        # all players receive result by default
   3.267 +        if receivers is None:
   3.268 +            receivers = self.players.keys()
   3.269 +
   3.270 +        field = share_a.field
   3.271 +
   3.272 +        self.increment_pc()
   3.273 +
   3.274 +        def recombine_value(shares_codes, keyList_a, keyList_b):
   3.275 +            def check(ls, a, b, isOK):
   3.276 +                true_str = str(True)
   3.277 +                if reduce(lambda x, y: true_str == y, ls):
   3.278 +                    return a, b
   3.279 +                else:
   3.280 +                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   3.281 +
   3.282 +            n = len(self.players)
   3.283 +            alpha_a = keyList_a.alpha
   3.284 +            alpha_b = keyList_b.alpha
   3.285 +
   3.286 +            a = 0
   3.287 +            b = 0
   3.288 +            isOK = True
   3.289 +            for inx in xrange(0, n):
   3.290 +                ai = shares_codes[inx]
   3.291 +                bi = shares_codes[2*n + inx]
   3.292 +                mi_a = shares_codes[n + inx]
   3.293 +                mi_b = shares_codes[3*n + inx]
   3.294 +                beta_a = keyList_a.get_key(inx)
   3.295 +                beta_b = keyList_b.get_key(inx)
   3.296 +                a += ai
   3.297 +                b += bi
   3.298 +                mi_prime = self.MAC(alpha_a, beta_a, ai)
   3.299 +                isOK = isOK and mi_a == mi_prime
   3.300 +                mi_prime = self.MAC(alpha_b, beta_b, bi)
   3.301 +                isOK = isOK and mi_b == mi_prime
   3.302 +                
   3.303 +            ds = self.broadcast(self.players.keys(), self.players.keys(),
   3.304 +                                str(isOK))
   3.305 +            ds = gatherResults(ds)
   3.306 +            ds.addCallbacks(check, self.error_handler, callbackArgs=(a, b, isOK))
   3.307 +            return ds
   3.308 +        
   3.309 +        def exchange((a, b), receivers):
   3.310 +            # Send share to all receivers.
   3.311 +            pc = tuple(self.program_counter)
   3.312 +            for other_id in receivers:
   3.313 +                self.protocols[other_id].sendShare(pc, a.get_value())
   3.314 +                self.protocols[other_id].sendShare(pc, a.get_mac(other_id - 1))
   3.315 +                self.protocols[other_id].sendShare(pc, b.get_value())
   3.316 +                self.protocols[other_id].sendShare(pc, b.get_mac(other_id - 1))
   3.317 +                
   3.318 +            if self.id in receivers:
   3.319 +                num_players = len(self.players.keys())
   3.320 +                values_a = num_players * [None]
   3.321 +                codes_a = num_players * [None]
   3.322 +                values_b = num_players * [None]
   3.323 +                codes_b = num_players * [None]
   3.324 +                for inx, other_id in enumerate(self.players.keys()):
   3.325 +                    values_a[inx] =  self._expect_share(other_id, field)
   3.326 +                    codes_a[inx] = self._expect_share(other_id, field)
   3.327 +                    values_b[inx] =  self._expect_share(other_id, field)
   3.328 +                    codes_b[inx] = self._expect_share(other_id, field)
   3.329 +                result = gatherResults(values_a + codes_a + values_b + codes_b)
   3.330 +                self.schedule_callback(result, recombine_value, a.get_keys(), b.get_keys())
   3.331 +                return result
   3.332 +
   3.333 +        result = gather_shares([share_a, share_b])
   3.334 +        self.schedule_callback(result, exchange, receivers)
   3.335 +        result.addErrback(self.error_handler)
   3.336 +
   3.337 +        # do actual communication
   3.338 +        self.activate_reactor()
   3.339 +
   3.340 +        if self.id in receivers:
   3.341 +            return result
   3.342 +
   3.343 +    def open(self, share, receivers=None):
   3.344 +        """Share reconstruction."""
   3.345 +        assert isinstance(share, Share)
   3.346 +        # all players receive result by default
   3.347 +        if receivers is None:
   3.348 +            receivers = self.players.keys()
   3.349 +
   3.350 +        field = share.field
   3.351 +
   3.352 +        self.increment_pc()
   3.353 +
   3.354 +        def recombine_value(shares_codes, keyList):
   3.355 +            isOK = True
   3.356 +            n = len(self.players)
   3.357 +            alpha = keyList.alpha
   3.358 +            x = 0
   3.359 +            for inx in xrange(0, n):
   3.360 +                xi = shares_codes[inx]
   3.361 +                mi = shares_codes[n + inx]
   3.362 +                beta = keyList.get_key(inx)
   3.363 +                x += xi
   3.364 +                mi_prime = self.MAC(alpha, beta, xi)
   3.365 +                isOK = isOK and mi == mi_prime
   3.366 +            def check(ls, x, isOK):
   3.367 +                true_str = str(True)
   3.368 +                if reduce(lambda x, y: true_str == y, ls):
   3.369 +                    return x
   3.370 +                else:
   3.371 +                    raise BeDOZaException("Wrong commitment. Some player revieved a wrong commitment. My commitments were: %s", isOK)
   3.372 +                
   3.373 +            ds = self.broadcast(self.players.keys(), self.players.keys(),
   3.374 +                                str(isOK))
   3.375 +            ds = gatherResults(ds)
   3.376 +            ds.addCallbacks(check, self.error_handler, callbackArgs=(x,isOK))
   3.377 +            return ds
   3.378 +
   3.379 +        def exchange(shareContent, receivers):
   3.380 +            # Send share to all receivers.
   3.381 +            pc = tuple(self.program_counter)
   3.382 +            for other_id in receivers:
   3.383 +                self.protocols[other_id].sendShare(pc, shareContent.get_value())
   3.384 +                self.protocols[other_id].sendShare(pc, shareContent.get_mac(other_id - 1))
   3.385 +            if self.id in receivers:
   3.386 +                num_players = len(self.players.keys())
   3.387 +                values = num_players * [None]
   3.388 +                codes = num_players * [None]
   3.389 +                for inx, other_id in enumerate(self.players.keys()):
   3.390 +                    values[inx] =  self._expect_share(other_id, field)
   3.391 +                    codes[inx] = self._expect_share(other_id, field)
   3.392 +                result = gatherResults(values + codes)
   3.393 +                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(shareContent.get_keys(),))
   3.394 +                return result
   3.395 +
   3.396 +        result = share.clone()
   3.397 +        self.schedule_callback(result, exchange, receivers)
   3.398 +        result.addErrback(self.error_handler)
   3.399 +
   3.400 +        # do actual communication
   3.401 +        self.activate_reactor()
   3.402 +
   3.403 +        if self.id in receivers:
   3.404 +            return result
   3.405 +
   3.406 +    def _plus_public(self, x, c, field):
   3.407 +        x = x.add_public(c, self.id)
   3.408 +        return BeDOZaShare(self, field, x.get_value(), x.get_keys(), x.get_macs())
   3.409 +
   3.410 +    def _plus(self, (x, y), field):
   3.411 +        """Addition of share-contents *x* and *y*."""
   3.412 +        return x + y
   3.413 +
   3.414 +    def _minus_public_right(self, x, c, field):
   3.415 +        z = self._minus_public_right_without_share(x, c, field)
   3.416 +        return BeDOZaShare(self, field, z.get_value(), z.get_keys(), z.get_macs())
   3.417 +
   3.418 +    def _minus_public_right_without_share(self, x, c, field):
   3.419 +        return x.sub_public(c, self.id)
   3.420 +
   3.421 +    def _wrap_in_share(self, shareContents, field):
   3.422 +        return BeDOZaShare(self, field,
   3.423 +                           shareContents.get_value(),
   3.424 +                           shareContents.get_keys(),
   3.425 +                           shareContents.get_macs())
   3.426 +
   3.427 +    def _minus_public_left(self, x, c, field):
   3.428 +        y = self._constant_multiply(x, field(-1))
   3.429 +        return self._plus_public(y, c, field)
   3.430 +    
   3.431 +    def _minus(self, (x, y), field):
   3.432 +        """Subtraction of share-tuples *x* and *y*."""
   3.433 +        return x - y
   3.434 +
   3.435 +    def _constant_multiply(self, x, c):
   3.436 +        """Multiplication of a share-tuple with a constant c."""
   3.437 +        assert(isinstance(c, FieldElement))
   3.438 +        return x.cmul(c)
   3.439 +
   3.440 +    def _get_triple(self, field):
   3.441 +        """ TODO: This is a dummy implementation, and should be replaced with proper code."""
   3.442 +        self.init_keys(field)
   3.443 +        a, b, c = 0, 0, 0
   3.444 +        share_a = field(2)
   3.445 +        share_b = field(4)
   3.446 +        n = len(self.players)
   3.447 +        share_c = n * share_a * share_b
   3.448 +        for playerid in self.players.keys():
   3.449 +            if self.id == playerid:
   3.450 +                triple_a = self.generate_share(field, share_a)
   3.451 +                a += share_a.value
   3.452 +                triple_b = self.generate_share(field, share_b)
   3.453 +                b += share_b.value
   3.454 +                triple_c = self.generate_share(field, share_c)
   3.455 +                c += share_c.value
   3.456 +        return [triple_a, triple_b, triple_c], False
   3.457 +
   3.458 +
   3.459 +class BeDOZaRuntime(BeDOZaMixin, SimpleArithmeticRuntime):
   3.460 +    """The BeDOZa runtime.
   3.461 +
   3.462 +    The runtime is used for sharing values (:meth:`secret_share` or
   3.463 +    :meth:`shift`) into :class:`BeDOZaShare` object and opening such
   3.464 +    shares (:meth:`open`) again. Calculations on shares is normally
   3.465 +    done through overloaded arithmetic operations, but it is also
   3.466 +    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
   3.467 +    prefers.
   3.468 +
   3.469 +    Each player in the protocol uses a :class:`~viff.runtime.Runtime`
   3.470 +    object. To create an instance and connect it correctly with the
   3.471 +    other players, please use the :func:`~viff.runtime.create_runtime`
   3.472 +    function instead of instantiating a Runtime directly. The
   3.473 +    :func:`~viff.runtime.create_runtime` function will take care of
   3.474 +    setting up network connections and return a :class:`Deferred`
   3.475 +    which triggers with the :class:`~viff.runtime.Runtime` object when
   3.476 +    it is ready.
   3.477 +    """
   3.478 +
   3.479 +    def __init__(self, player, threshold=None, options=None):
   3.480 +        """Initialize runtime."""
   3.481 +        SimpleArithmeticRuntime.__init__(self, player, threshold, options)
   3.482 +        self.threshold = self.num_players - 1
   3.483 +        self.random_share_number = 100
   3.484 +        self.random_shares = []
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/viff/bedoza/bedoza_triple.py	Fri Jul 23 13:17:48 2010 +0200
     4.3 @@ -0,0 +1,556 @@
     4.4 +# Copyright 2010 VIFF Development Team.
     4.5 +#
     4.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     4.7 +#
     4.8 +# VIFF is free software: you can redistribute it and/or modify it
     4.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    4.10 +# published by the Free Software Foundation, either version 3 of the
    4.11 +# License, or (at your option) any later version.
    4.12 +#
    4.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    4.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    4.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    4.16 +# Public License for more details.
    4.17 +#
    4.18 +# You should have received a copy of the GNU Lesser General Public
    4.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    4.20 +
    4.21 +"""Triple generation for the BeDOZa protocol.
    4.22 +    TODO: Explain more.
    4.23 +"""
    4.24 +
    4.25 +import itertools
    4.26 +
    4.27 +from twisted.internet.defer import Deferred, gatherResults, succeed
    4.28 +
    4.29 +from viff.runtime import Runtime, Share, ShareList, gather_shares
    4.30 +from viff.field import FieldElement, GF
    4.31 +from viff.constants import TEXT
    4.32 +from viff.util import rand
    4.33 +
    4.34 +from viff.bedoza.bedoza import BeDOZaShare, BeDOZaShareContents
    4.35 +
    4.36 +from viff.bedoza.keylist import BeDOZaKeyList
    4.37 +from viff.bedoza.maclist import BeDOZaMACList
    4.38 +
    4.39 +# TODO: Use secure random instead!
    4.40 +from random import Random
    4.41 +
    4.42 +from viff.hash_broadcast import HashBroadcastMixin
    4.43 +
    4.44 +try:
    4.45 +    import pypaillier
    4.46 +except ImportError:
    4.47 +    # The pypaillier module is not released yet, so we cannot expect
    4.48 +    # the import to work.
    4.49 +    print "Error: The pypaillier module or one of the used functions " \
    4.50 +        "are not available."
    4.51 +
    4.52 +class Triple(object):
    4.53 +    def __init__(self, a, b, c):
    4.54 +        self.a, self.b, self.c = a, b, c
    4.55 +    def __str__(self):
    4.56 +        return "(%s,%s,%s)" % (self.a, self.b, self.c)
    4.57 +
    4.58 +
    4.59 +def _send(runtime, vals, serialize=str, deserialize=int):
    4.60 +    """Send vals[i] to player i + 1. Returns deferred list.
    4.61 +
    4.62 +    Works as default for integers. If other stuff has to be
    4.63 +    sent, supply another serialization, deserialition.
    4.64 +    """
    4.65 +    runtime.increment_pc()
    4.66 +    
    4.67 +    pc = tuple(runtime.program_counter)
    4.68 +    for p in runtime.players:
    4.69 +        msg = serialize(vals[p - 1])
    4.70 +        runtime.protocols[p].sendData(pc, TEXT, msg)
    4.71 +    def err_handler(err):
    4.72 +        print err
    4.73 +    values = []
    4.74 +    for p in runtime.players:
    4.75 +        d = Deferred()
    4.76 +        d.addCallbacks(deserialize, err_handler)
    4.77 +        runtime._expect_data(p, TEXT, d)
    4.78 +        values.append(d)
    4.79 +    result = gatherResults(values)
    4.80 +    return result
    4.81 +
    4.82 +def _convolute(runtime, val, serialize=str, deserialize=int):
    4.83 +    """As send, but sends the same val to all players."""
    4.84 +    return _send(runtime, [val] * runtime.num_players,
    4.85 +                 serialize=serialize, deserialize=deserialize)
    4.86 +
    4.87 +def _convolute_gf_elm(runtime, gf_elm):
    4.88 +    return _convolute(runtime, gf_elm,
    4.89 +                      serialize=lambda x: str(x.value),
    4.90 +                      deserialize=lambda x: gf_elm.field(int(x)))
    4.91 +
    4.92 +def _send_gf_elm(runtime, vals):
    4.93 +    return _send(runtime, vals, 
    4.94 +                 serialize=lambda x: str(x.value),
    4.95 +                 deserialize=lambda x: gf_elm.field(int(x)))
    4.96 +
    4.97 +
    4.98 +class PartialShareContents(object):
    4.99 +    """A BeDOZa share without macs, e.g. < a >.
   4.100 +    TODO: BeDOZaShare should extend this class?
   4.101 +    
   4.102 +    TODO: Should the partial share contain the public encrypted shares?
   4.103 +    TODO: It may be wrong to pass encrypted_shares to super constructor; 
   4.104 +      does it mean that the already public values get passed along on the
   4.105 +      network even though all players already posess them?
   4.106 +    """
   4.107 +    def __init__(self, value, enc_shares, N_squared_list):
   4.108 +        self.value = value
   4.109 +        self.enc_shares = enc_shares
   4.110 +        self.N_squared_list = N_squared_list
   4.111 +
   4.112 +    def __str__(self):
   4.113 +        return "PartialShareContents(%d; %s; %s)" % (self.value, self.enc_shares, self.N_squared_list)
   4.114 +
   4.115 +    def __add__(self, other):
   4.116 +        z = self.value + other.value
   4.117 +        z_enc_shares = []
   4.118 +        for x, y, N_squared in zip(self.enc_shares, other.enc_shares, self.N_squared_list):
   4.119 +            z_enc_shares.append((x * y) % N_squared)
   4.120 +        return PartialShareContents(z, z_enc_shares, self.N_squared_list)
   4.121 +
   4.122 +# In VIFF, callbacks get the *contents* of a share as input. Hence, in order
   4.123 +# to get a PartialShare as input to callbacks, we need this extra level of
   4.124 +# wrapper indirection.
   4.125 +class PartialShare(Share):
   4.126 +    def __init__(self, runtime, field, value=None, enc_shares=None):
   4.127 +        if value == None and enc_shares == None:
   4.128 +            Share.__init__(self, runtime, field)
   4.129 +        else:
   4.130 +            N_squared_list = [ runtime.players[player_id].pubkey['n_square'] for player_id in runtime.players.keys()]
   4.131 +            partial_share_contents = PartialShareContents(value, enc_shares, N_squared_list)
   4.132 +            Share.__init__(self, runtime, field, partial_share_contents)
   4.133 +
   4.134 +
   4.135 +class PartialShareGenerator:
   4.136 +
   4.137 +    def __init__(self, Zp, runtime, random, paillier):
   4.138 +        self.paillier = paillier
   4.139 +        self.Zp = Zp
   4.140 +        self.runtime = runtime
   4.141 +        self.random = random
   4.142 +
   4.143 +    def generate_share(self, value):
   4.144 +        self.runtime.increment_pc()
   4.145 +        
   4.146 +        r = [self.Zp(self.random.randint(0, self.Zp.modulus - 1)) # TODO: Exclusve?
   4.147 +             for _ in range(self.runtime.num_players - 1)]
   4.148 +        if self.runtime.id == 1:
   4.149 +            share = value - sum(r)
   4.150 +        else:
   4.151 +            share = r[self.runtime.id - 2]
   4.152 +        enc_share = self.paillier.encrypt(share.value)
   4.153 +        enc_shares = _convolute(self.runtime, enc_share)
   4.154 +        def create_partial_share(enc_shares, share):
   4.155 +            return PartialShare(self.runtime, self.Zp, share, enc_shares)
   4.156 +        self.runtime.schedule_callback(enc_shares, create_partial_share, share)
   4.157 +        return enc_shares
   4.158 +
   4.159 +    def generate_random_shares(self, n):
   4.160 +        self.runtime.increment_pc()
   4.161 +        N_squared_list = [ self.runtime.players[player_id].pubkey['n_square'] for player_id in self.runtime.players]
   4.162 +        shares = [PartialShare(self.runtime, self.Zp) for _ in xrange(n)]
   4.163 +        for inx in xrange(n):
   4.164 +            r = self.random.randint(0, self.Zp.modulus - 1)
   4.165 +            ri = self.Zp(r)
   4.166 +            enc_share = self.paillier.encrypt(ri.value)
   4.167 +            enc_shares = _convolute(self.runtime, enc_share)
   4.168 +            def create_partial_share(enc_shares, ri, s, N_squared_list):
   4.169 +                s.callback(PartialShareContents(ri, enc_shares, N_squared_list))
   4.170 +            self.runtime.schedule_callback(enc_shares,
   4.171 +                                           create_partial_share,
   4.172 +                                           ri,
   4.173 +                                           shares[inx],
   4.174 +                                           N_squared_list)
   4.175 +        return shares
   4.176 +
   4.177 +class ShareGenerator(PartialShareGenerator):
   4.178 +
   4.179 +    def __init__(self, Zp, runtime, random, paillier, u_bound, alpha):
   4.180 +        self.u_bound = u_bound
   4.181 +        self.alpha = alpha
   4.182 +        PartialShareGenerator.__init__(self, Zp, runtime, random, paillier)
   4.183 +
   4.184 +    def generate_share(self, value):
   4.185 +        self.runtime.increment_pc()
   4.186 +        partial_share = PartialShareGenerator.generate_share(self, value)
   4.187 +        full_share = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
   4.188 +                             self.random, self.paillier, [partial_share])
   4.189 +        return full_share[0]
   4.190 +    
   4.191 +    def generate_random_shares(self, n):
   4.192 +        self.runtime.increment_pc()
   4.193 +        partial_shares = PartialShareGenerator.generate_random_shares(self, n)
   4.194 +        return add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
   4.195 +                        self.random, self.paillier, partial_shares)
   4.196 +
   4.197 +class ModifiedPaillier(object):
   4.198 +    """A slight modification of the Paillier cryptosystem.
   4.199 +
   4.200 +    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
   4.201 +    than the usual Z_n where n is the Paillier modulus.
   4.202 +
   4.203 +    See Ivan's paper, beginning of section 6.
   4.204 +    """
   4.205 +
   4.206 +    def __init__(self, runtime, random):
   4.207 +        self.runtime = runtime;
   4.208 +        self.random = random
   4.209 +
   4.210 +    def _f(self, x, n):
   4.211 +        if x >= 0:
   4.212 +            return x
   4.213 +        else:
   4.214 +            return n + x
   4.215 +
   4.216 +    def _f_inverse(self, y, n):
   4.217 +        if 0 <= y <= (n + 1) / 2:
   4.218 +            return y
   4.219 +        else:
   4.220 +            return y - n
   4.221 +
   4.222 +    def encrypt(self, value, player_id=None):
   4.223 +        """Encrypt using public key of player player_id.
   4.224 +
   4.225 +        Defaults to own public key.
   4.226 +        """
   4.227 +        assert isinstance(value, int) or isinstance(value, long), \
   4.228 +            "paillier: encrypts only integers and longs, got %s" % value.__class__
   4.229 +        if not player_id:
   4.230 +            player_id = self.runtime.id
   4.231 +        n = self.runtime.players[player_id].pubkey['n']
   4.232 +        min = -(n - 1) / 2 + 1
   4.233 +        max = (n + 1) / 2
   4.234 +        assert min <= value <= max, \
   4.235 +            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
   4.236 +            "[%d ; %d]"  % (value, min, max)
   4.237 +        pubkey = self.runtime.players[player_id].pubkey
   4.238 +        randomness = self.random.randint(1, long(n))
   4.239 +        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
   4.240 +
   4.241 +    def decrypt(self, enc_value):
   4.242 +        """Decrypt using own private key."""
   4.243 +        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
   4.244 +            "paillier decrypts only longs, got %s" % enc_value.__class__
   4.245 +        n = self.runtime.players[self.runtime.id].pubkey['n']
   4.246 +        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
   4.247 +        assert 0 <= enc_value < n_square, \
   4.248 +            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
   4.249 +            % (enc_value, n_square)
   4.250 +        seckey = self.runtime.players[self.runtime.id].seckey
   4.251 +        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
   4.252 +
   4.253 +    def get_modulus(self, player_id):
   4.254 +        return self.runtime.players[player_id].pubkey['n']
   4.255 +
   4.256 +    def get_modulus_square(self, player_id):
   4.257 +        return self.runtime.players[player_id].pubkey['n_square']
   4.258 +
   4.259 +def add_macs(runtime, field, u_bound, alpha, random, paillier, partial_shares):
   4.260 +    """Adds macs to the set of PartialBeDOZaShares.
   4.261 +        
   4.262 +    Returns a deferred which yields a list of full shares, e.g.
   4.263 +    including macs.  (the full shares are deferreds of type
   4.264 +    BeDOZaShare.)
   4.265 +    """        
   4.266 +    # TODO: Would be nice with a class ShareContents like the class
   4.267 +    # PartialShareContents used here.
   4.268 +        
   4.269 +    runtime.increment_pc() # Huh!?
   4.270 +
   4.271 +    def do_add_macs(partial_share_contents, result_shares):
   4.272 +        num_players = runtime.num_players
   4.273 +        lists_of_mac_keys = [ [] for x in runtime.players ]
   4.274 +        lists_of_c_list = [ [] for x in runtime.players ]
   4.275 +        for partial_share_content in partial_share_contents:
   4.276 +            for j in xrange(0, num_players):
   4.277 +                # TODO: This is probably not the fastes way to generate
   4.278 +                # the betas.
   4.279 +                beta = random.randint(0, u_bound)
   4.280 +                # TODO: Outcommented until mod paillier works for negative numbers.
   4.281 +                # if rand.choice([True, False]):
   4.282 +                #    beta = -beta
   4.283 +                enc_beta = paillier.encrypt(beta, player_id=j + 1)
   4.284 +                c_j = partial_share_content.enc_shares[j]
   4.285 +                n2 = paillier.get_modulus_square(j + 1)
   4.286 +                c = (pow(c_j, alpha, n2) * enc_beta) % n2
   4.287 +                lists_of_c_list[j].append(c)
   4.288 +                lists_of_mac_keys[j].append(field(beta))
   4.289 +
   4.290 +        received_cs = _send(runtime, lists_of_c_list, deserialize=eval)
   4.291 +
   4.292 +        def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
   4.293 +            shares = []               
   4.294 +            for inx in xrange(0, len(partial_share_contents)):
   4.295 +                mac_keys = []
   4.296 +                decrypted_cs = []
   4.297 +                for c_list, mkeys in zip(recevied_cs,
   4.298 +                                         lists_of_mac_keys):
   4.299 +                    decrypted_cs.append(field(paillier.decrypt(c_list[inx])))
   4.300 +                    mac_keys.append(mkeys[inx])
   4.301 +                partial_share = partial_share_contents[inx]
   4.302 +                mac_key_list = BeDOZaKeyList(alpha, mac_keys)
   4.303 +
   4.304 +                mac_msg_list = BeDOZaMACList(decrypted_cs)
   4.305 +                result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
   4.306 +                                                                mac_key_list,
   4.307 +                                                                mac_msg_list))
   4.308 +            return shares
   4.309 +
   4.310 +        runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
   4.311 +        return received_cs
   4.312 +
   4.313 +    result_shares = [Share(runtime, field) for x in xrange(len(partial_shares))]
   4.314 +    runtime.schedule_callback(gatherResults(partial_shares),
   4.315 +                              do_add_macs,
   4.316 +                              result_shares)
   4.317 +    return result_shares
   4.318 +
   4.319 +
   4.320 +class TripleGenerator(object):
   4.321 +
   4.322 +    def __init__(self, runtime, p, random):
   4.323 +        assert p > 1
   4.324 +        self.random = random
   4.325 +        # TODO: Generate Paillier cipher with N_i sufficiently larger than p
   4.326 +        self.runtime = runtime
   4.327 +        self.p = p
   4.328 +        self.Zp = GF(p)
   4.329 +        self.k = self._bit_length_of(p)
   4.330 +        self.u_bound = 2**(4 * self.k)
   4.331 +
   4.332 +        paillier_random = Random(self.random.getrandbits(128))
   4.333 +        alpha_random = Random(self.random.getrandbits(128))
   4.334 +        self.paillier = ModifiedPaillier(runtime, paillier_random)
   4.335 +        
   4.336 +        # Debug output.
   4.337 +        #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
   4.338 +        #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
   4.339 +        #print "n_%d bitlength: %d" % (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
   4.340 +
   4.341 +        #self.Zp = GF(p)
   4.342 +        #self.Zn2 = GF(self.paillier.pubkey['n_square'])
   4.343 +        #self.alpha = self.Zp(self.random.randint(0, p - 1))
   4.344 +        self.alpha = alpha_random.randint(0, p - 1)
   4.345 +        self.n2 = runtime.players[runtime.id].pubkey['n_square']
   4.346 +
   4.347 +    def _bit_length_of(self, i):
   4.348 +        bit_length = 0
   4.349 +        while i:
   4.350 +            i >>= 1
   4.351 +            bit_length += 1
   4.352 +        return bit_length
   4.353 +
   4.354 +    def generate_triples(self, n):
   4.355 +        """Generates and returns a set of n triples.
   4.356 +        
   4.357 +        Data sent over the network is packaged in large hunks in order
   4.358 +        to optimize. TODO: Explain better.
   4.359 +
   4.360 +        TODO: This method needs to have enough RAM to represent all n
   4.361 +        triples in memory at the same time. Is there a nice way to
   4.362 +        stream this, e.g. by using Python generators?
   4.363 +        """
   4.364 +
   4.365 +        self.runtime.increment_pc()
   4.366 +        
   4.367 +        def check(v, a, b, c):
   4.368 +            if v.value != 0:
   4.369 +                raise Exception("TripleTest failed - The two triples were inconsistent.")
   4.370 +            return (a, b, c)
   4.371 +        
   4.372 +        def compute_value(r, a, b, c, x, y, z):
   4.373 +            l = self.runtime._cmul(r, x, self.Zp)
   4.374 +            m = self.runtime._cmul(r, y, self.Zp)
   4.375 +            k = self.runtime._cmul(r*r, z, self.Zp)
   4.376 +            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
   4.377 +            v = self.runtime.open(v)
   4.378 +            v.addCallback(check, a, b, c)
   4.379 +            return v
   4.380 +
   4.381 +        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier, self.u_bound, self.alpha)
   4.382 +        
   4.383 +        random_shares = gen.generate_random_shares(n)
   4.384 +
   4.385 +        results = [Deferred() for _ in xrange(n)]
   4.386 +        
   4.387 +        triples = self._generate_passive_triples(2 * n)
   4.388 +
   4.389 +        for inx in xrange(n):
   4.390 +            a = triples[inx]
   4.391 +            b = triples[inx + 2 * n]
   4.392 +            c = triples[inx + 4 * n]
   4.393 +            x = triples[inx + n]
   4.394 +            y = triples[inx + 3 * n]
   4.395 +            z = triples[inx + 5 * n]
   4.396 +            r = self.runtime.open(random_shares[inx])
   4.397 +            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
   4.398 +            r.chainDeferred(results[inx])
   4.399 +        return results
   4.400 +          
   4.401 +        # TODO: Do some ZK stuff.
   4.402 +
   4.403 +    def _generate_passive_triples(self, n):
   4.404 +        """Generates and returns a list of 3n shares corresponding to
   4.405 +        n passive tuples. The first n are the a's, then comes n b's
   4.406 +        followed by n c's.
   4.407 +        
   4.408 +        Consistency is only guaranteed if all players follow the protool.
   4.409 +        """
   4.410 +
   4.411 +        self.runtime.increment_pc()
   4.412 +        
   4.413 +        gen = PartialShareGenerator(self.Zp, self.runtime, self.random, self.paillier)
   4.414 +        partial_shares = []
   4.415 +        for _ in xrange(2 * n):
   4.416 +             partial_shares.append(gen.generate_share(self.random.randint(0, self.Zp.modulus - 1)))
   4.417 +
   4.418 +
   4.419 +        partial_shares_c = self._full_mul(partial_shares[0:n], partial_shares[n:2*n])
   4.420 +
   4.421 +        full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, partial_shares + partial_shares_c)
   4.422 +
   4.423 +        return full_shares  
   4.424 +
   4.425 +        # for player i:
   4.426 +        #     receive c from player i and set 
   4.427 +        #         m^i=Decrypt(c)
   4.428 +    
   4.429 +    def _mul(self, inx, jnx, ais=None, cjs=None):
   4.430 +        """Multiply each of the field elements in *ais* with the
   4.431 +        corresponding encrypted elements in *cjs*.
   4.432 +        
   4.433 +        Returns a deferred which will yield a list of PartialShareContents.
   4.434 +        """
   4.435 +        CKIND = 1
   4.436 +        DiKIND = 2
   4.437 +        DjKIND = 3
   4.438 +        
   4.439 +        self.runtime.increment_pc()
   4.440 +
   4.441 +        pc = tuple(self.runtime.program_counter)
   4.442 +
   4.443 +        deferreds = []
   4.444 +        zis = []
   4.445 +        if self.runtime.id == inx:
   4.446 +            Nj_square = self.paillier.get_modulus_square(jnx)
   4.447 +            cs = []
   4.448 +            dis = []
   4.449 +            for ai, cj in zip(ais, cjs):
   4.450 +                u = rand.randint(0, self.u_bound)
   4.451 +                Ej_u = self.paillier.encrypt(u, jnx)
   4.452 +                cs.append( (pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
   4.453 +                zi = self.Zp(-u)
   4.454 +                zis.append(zi)
   4.455 +                dis.append(self.paillier.encrypt(zi.value, inx))
   4.456 +            self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
   4.457 +
   4.458 +            for player_id in self.runtime.players:
   4.459 +                self.runtime.protocols[player_id].sendData(pc, DiKIND, str(dis))
   4.460 +
   4.461 +        if self.runtime.id == jnx:
   4.462 +            cs = Deferred()
   4.463 +            self.runtime._expect_data(inx, CKIND, cs)
   4.464 +            def decrypt(cs, pc, zis):
   4.465 +                zjs = []
   4.466 +                djs = []
   4.467 +                for c in eval(cs):
   4.468 +                    t = self.paillier.decrypt(c)
   4.469 +                    zj = self.Zp(t)
   4.470 +                    zjs.append(zj)
   4.471 +                    djs.append(self.paillier.encrypt(zj.value, jnx))
   4.472 +                for player_id in self.runtime.players:
   4.473 +                    self.runtime.protocols[player_id].sendData(pc, DjKIND, str(djs))
   4.474 +                if not zis == []:
   4.475 +                    return [x + y for x, y in zip(zis, zjs)]
   4.476 +                else:
   4.477 +                    return zjs 
   4.478 +            cs.addCallback(decrypt, pc, zis)
   4.479 +            deferreds.append(cs)
   4.480 +        else:
   4.481 +            zis_deferred = Deferred()
   4.482 +            zis_deferred.callback(zis)
   4.483 +            deferreds.append(zis_deferred)
   4.484 +
   4.485 +        dis = Deferred()
   4.486 +        self.runtime._expect_data(inx, DiKIND, dis)
   4.487 +        djs = Deferred()
   4.488 +        self.runtime._expect_data(jnx, DjKIND, djs)
   4.489 +
   4.490 +        deferreds.append(dis)
   4.491 +        deferreds.append(djs)
   4.492 +        r = gatherResults(deferreds)
   4.493 +        def wrap((values, dis, djs), inx, jnx):
   4.494 +            dis = eval(dis)
   4.495 +            djs = eval(djs)
   4.496 +            n_square_i = self.paillier.get_modulus_square(inx)
   4.497 +            n_square_j = self.paillier.get_modulus_square(jnx)
   4.498 +            N_squared_list = [self.paillier.get_modulus_square(player_id) for player_id in self.runtime.players]
   4.499 +            ps = []
   4.500 +            for v, di, dj in itertools.izip_longest(values, dis, djs, fillvalue=self.Zp(0)):
   4.501 +                value = v 
   4.502 +                enc_shares = len(self.runtime.players) * [1]
   4.503 +                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
   4.504 +                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
   4.505 +                ps.append(PartialShareContents(value, enc_shares, N_squared_list))
   4.506 +            return ps
   4.507 +        r.addCallback(wrap, inx, jnx)
   4.508 +        return r
   4.509 +
   4.510 +    def _full_mul(self, a, b):
   4.511 +        """Multiply each of the PartialShares in the list *a* with the
   4.512 +        corresponding PartialShare in the list *b*.
   4.513 +        
   4.514 +        Returns a deferred which will yield a list of PartialShares.
   4.515 +        """
   4.516 +        self.runtime.increment_pc()
   4.517 +        
   4.518 +        def do_full_mul(shares, result_shares):
   4.519 +            """Share content belonging to ai, bi are at:
   4.520 +            shares[i], shares[len(shares) + i].
   4.521 +            """
   4.522 +            deferreds = []
   4.523 +            len_shares = len(shares)
   4.524 +            a_values = [s.value for s in shares[0:len_shares/2]]
   4.525 +            b_enc_shares = []
   4.526 +            for inx in self.runtime.players:              
   4.527 +                b_enc_shares.append([s.enc_shares[inx - 1] for s in shares[len_shares/2:]])
   4.528 +            for inx in xrange(0, len(self.runtime.players)):
   4.529 +                for jnx in xrange(0, len(self.runtime.players)):
   4.530 +                    deferreds.append(self._mul(inx + 1,
   4.531 +                                               jnx + 1,
   4.532 +                                               a_values,
   4.533 +                                               b_enc_shares[jnx]))
   4.534 +                        
   4.535 +            def compute_shares(partialShareContents, len_shares, result_shares):
   4.536 +                num_players = len(self.runtime.players)
   4.537 +                pcs = len(partialShareContents[0]) * [None]
   4.538 +                for ps in partialShareContents:
   4.539 +                    for inx in xrange(0, len(ps)):
   4.540 +                        if pcs[inx] == None:
   4.541 +                            pcs[inx] = ps[inx]
   4.542 +                        else:
   4.543 +                            pcs[inx] += ps[inx]
   4.544 +                for p, s in zip(pcs, result_shares):
   4.545 +                    s.callback(p)
   4.546 +                return None
   4.547 +            d = gatherResults(deferreds)
   4.548 +            d.addCallback(compute_shares, len_shares, result_shares)
   4.549 +            return d
   4.550 +        result_shares = [Share(self.runtime, self.Zp) for x in a]
   4.551 +        self.runtime.schedule_callback(gatherResults(a + b),
   4.552 +                                       do_full_mul,
   4.553 +                                       result_shares)
   4.554 +        return result_shares
   4.555 +
   4.556 +
   4.557 +# TODO: Represent all numbers by GF objects, Zp, Zn, etc.
   4.558 +# E.g. paillier encrypt should return Zn^2 elms and decrypt should
   4.559 +# return Zp elements.
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/viff/bedoza/keylist.py	Fri Jul 23 13:17:48 2010 +0200
     5.3 @@ -0,0 +1,62 @@
     5.4 +# Copyright 2010 VIFF Development Team.
     5.5 +#
     5.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     5.7 +#
     5.8 +# VIFF is free software: you can redistribute it and/or modify it
     5.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    5.10 +# published by the Free Software Foundation, either version 3 of the
    5.11 +# License, or (at your option) any later version.
    5.12 +#
    5.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    5.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    5.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    5.16 +# Public License for more details.
    5.17 +#
    5.18 +# You should have received a copy of the GNU Lesser General Public
    5.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    5.20 +
    5.21 +class BeDOZaKeyList(object):
    5.22 +    """A list of keys, one for each player.
    5.23 +
    5.24 +    We assume that the key for player *i* is stored in
    5.25 +    location *i - 1* in the *keys* list given as argument to the constructor.
    5.26 +    """
    5.27 +
    5.28 +    def __init__(self, alpha, keys):
    5.29 +        self.alpha = alpha
    5.30 +        self.keys = keys
    5.31 +
    5.32 +    def get_key(self, player_id):
    5.33 +        return self.keys[player_id]
    5.34 +
    5.35 +    def set_key(self, player_id, v):
    5.36 +        self.keys[player_id] = v
    5.37 +
    5.38 +    def cmul(self, c):
    5.39 +        return BeDOZaKeyList(self.alpha, map(lambda k: c * k, self.keys))
    5.40 +
    5.41 +    def __add__(self, other):
    5.42 +        """Addition."""
    5.43 +        assert self.alpha == other.alpha
    5.44 +        keys = []
    5.45 +        for k1, k2 in zip(self.keys, other.keys):
    5.46 +            keys.append(k1 + k2)
    5.47 +        return BeDOZaKeyList(self.alpha, keys)
    5.48 +
    5.49 +    def __sub__(self, other):
    5.50 +        """Subtraction."""
    5.51 +        assert self.alpha == other.alpha
    5.52 +        keys = []
    5.53 +        for k1, k2 in zip(self.keys, other.keys):
    5.54 +            keys.append(k1 - k2)
    5.55 +        return BeDOZaKeyList(self.alpha, keys)
    5.56 +
    5.57 +    def __eq__(self, other):
    5.58 +        return self.alpha == other.alpha and self.keys == other.keys
    5.59 +
    5.60 +    def __str__(self):
    5.61 +        return "(%s, %s)" % (self.alpha, str(self.keys))
    5.62 +
    5.63 +    def __repr__(self):
    5.64 +        return str(self)
    5.65 +
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/viff/bedoza/maclist.py	Fri Jul 23 13:17:48 2010 +0200
     6.3 @@ -0,0 +1,54 @@
     6.4 +# Copyright 2010 VIFF Development Team.
     6.5 +#
     6.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     6.7 +#
     6.8 +# VIFF is free software: you can redistribute it and/or modify it
     6.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    6.10 +# published by the Free Software Foundation, either version 3 of the
    6.11 +# License, or (at your option) any later version.
    6.12 +#
    6.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    6.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    6.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    6.16 +# Public License for more details.
    6.17 +#
    6.18 +# You should have received a copy of the GNU Lesser General Public
    6.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    6.20 +
    6.21 +class BeDOZaMACList(object):
    6.22 +
    6.23 +    def __init__(self, macs):
    6.24 +        self.macs = macs
    6.25 +
    6.26 +    def get_macs(self):
    6.27 +        return self.macs
    6.28 +
    6.29 +    def get_mac(self, inx):
    6.30 +        return self.macs[inx]
    6.31 +
    6.32 +    def cmul(self, c):
    6.33 +        return BeDOZaMACList(map(lambda m: c * m, self.macs))
    6.34 +        
    6.35 +    def __add__(self, other):
    6.36 +        """Addition."""
    6.37 +        macs = []
    6.38 +        for c1, c2 in zip(self.macs, other.macs):
    6.39 +            macs.append(c1 + c2)
    6.40 +        return BeDOZaMACList(macs)
    6.41 +
    6.42 +    def __sub__(self, other):
    6.43 +        """Subtraction."""
    6.44 +        macs = []
    6.45 +        for c1, c2 in zip(self.macs, other.macs):
    6.46 +            macs.append(c1 - c2)
    6.47 +        return BeDOZaMACList(macs)
    6.48 +
    6.49 +    def __eq__(self, other):
    6.50 +        return self.macs == other.macs
    6.51 +
    6.52 +    def __str__(self):
    6.53 +        return str(self.macs)
    6.54 +
    6.55 +    def __repr__(self):
    6.56 +        return str(self)
    6.57 +    
     7.1 --- a/viff/bedoza_triple.py	Fri Jul 23 11:18:04 2010 +0200
     7.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.3 @@ -1,553 +0,0 @@
     7.4 -# Copyright 2010 VIFF Development Team.
     7.5 -#
     7.6 -# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     7.7 -#
     7.8 -# VIFF is free software: you can redistribute it and/or modify it
     7.9 -# under the terms of the GNU Lesser General Public License (LGPL) as
    7.10 -# published by the Free Software Foundation, either version 3 of the
    7.11 -# License, or (at your option) any later version.
    7.12 -#
    7.13 -# VIFF is distributed in the hope that it will be useful, but WITHOUT
    7.14 -# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    7.15 -# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    7.16 -# Public License for more details.
    7.17 -#
    7.18 -# You should have received a copy of the GNU Lesser General Public
    7.19 -# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    7.20 -
    7.21 -"""Triple generation for the BeDOZa protocol.
    7.22 -    TODO: Explain more.
    7.23 -"""
    7.24 -
    7.25 -import itertools
    7.26 -
    7.27 -from twisted.internet.defer import Deferred, gatherResults, succeed
    7.28 -
    7.29 -from viff.runtime import Runtime, Share, ShareList, gather_shares
    7.30 -from viff.field import FieldElement, GF
    7.31 -from viff.constants import TEXT
    7.32 -from viff.util import rand
    7.33 -
    7.34 -from bedoza import BeDOZaKeyList, BeDOZaMACList, BeDOZaShare, BeDOZaShareContents
    7.35 -
    7.36 -# TODO: Use secure random instead!
    7.37 -from random import Random
    7.38 -
    7.39 -from hash_broadcast import HashBroadcastMixin
    7.40 -
    7.41 -try:
    7.42 -    import pypaillier
    7.43 -except ImportError:
    7.44 -    # The pypaillier module is not released yet, so we cannot expect
    7.45 -    # the import to work.
    7.46 -    print "Error: The pypaillier module or one of the used functions " \
    7.47 -        "are not available."
    7.48 -
    7.49 -class Triple(object):
    7.50 -    def __init__(self, a, b, c):
    7.51 -        self.a, self.b, self.c = a, b, c
    7.52 -    def __str__(self):
    7.53 -        return "(%s,%s,%s)" % (self.a, self.b, self.c)
    7.54 -
    7.55 -
    7.56 -def _send(runtime, vals, serialize=str, deserialize=int):
    7.57 -    """Send vals[i] to player i + 1. Returns deferred list.
    7.58 -
    7.59 -    Works as default for integers. If other stuff has to be
    7.60 -    sent, supply another serialization, deserialition.
    7.61 -    """
    7.62 -    runtime.increment_pc()
    7.63 -    
    7.64 -    pc = tuple(runtime.program_counter)
    7.65 -    for p in runtime.players:
    7.66 -        msg = serialize(vals[p - 1])
    7.67 -        runtime.protocols[p].sendData(pc, TEXT, msg)
    7.68 -    def err_handler(err):
    7.69 -        print err
    7.70 -    values = []
    7.71 -    for p in runtime.players:
    7.72 -        d = Deferred()
    7.73 -        d.addCallbacks(deserialize, err_handler)
    7.74 -        runtime._expect_data(p, TEXT, d)
    7.75 -        values.append(d)
    7.76 -    result = gatherResults(values)
    7.77 -    return result
    7.78 -
    7.79 -def _convolute(runtime, val, serialize=str, deserialize=int):
    7.80 -    """As send, but sends the same val to all players."""
    7.81 -    return _send(runtime, [val] * runtime.num_players,
    7.82 -                 serialize=serialize, deserialize=deserialize)
    7.83 -
    7.84 -def _convolute_gf_elm(runtime, gf_elm):
    7.85 -    return _convolute(runtime, gf_elm,
    7.86 -                      serialize=lambda x: str(x.value),
    7.87 -                      deserialize=lambda x: gf_elm.field(int(x)))
    7.88 -
    7.89 -def _send_gf_elm(runtime, vals):
    7.90 -    return _send(runtime, vals, 
    7.91 -                 serialize=lambda x: str(x.value),
    7.92 -                 deserialize=lambda x: gf_elm.field(int(x)))
    7.93 -
    7.94 -
    7.95 -class PartialShareContents(object):
    7.96 -    """A BeDOZa share without macs, e.g. < a >.
    7.97 -    TODO: BeDOZaShare should extend this class?
    7.98 -    
    7.99 -    TODO: Should the partial share contain the public encrypted shares?
   7.100 -    TODO: It may be wrong to pass encrypted_shares to super constructor; 
   7.101 -      does it mean that the already public values get passed along on the
   7.102 -      network even though all players already posess them?
   7.103 -    """
   7.104 -    def __init__(self, value, enc_shares, N_squared_list):
   7.105 -        self.value = value
   7.106 -        self.enc_shares = enc_shares
   7.107 -        self.N_squared_list = N_squared_list
   7.108 -
   7.109 -    def __str__(self):
   7.110 -        return "PartialShareContents(%d; %s; %s)" % (self.value, self.enc_shares, self.N_squared_list)
   7.111 -
   7.112 -    def __add__(self, other):
   7.113 -        z = self.value + other.value
   7.114 -        z_enc_shares = []
   7.115 -        for x, y, N_squared in zip(self.enc_shares, other.enc_shares, self.N_squared_list):
   7.116 -            z_enc_shares.append((x * y) % N_squared)
   7.117 -        return PartialShareContents(z, z_enc_shares, self.N_squared_list)
   7.118 -
   7.119 -# In VIFF, callbacks get the *contents* of a share as input. Hence, in order
   7.120 -# to get a PartialShare as input to callbacks, we need this extra level of
   7.121 -# wrapper indirection.
   7.122 -class PartialShare(Share):
   7.123 -    def __init__(self, runtime, field, value=None, enc_shares=None):
   7.124 -        if value == None and enc_shares == None:
   7.125 -            Share.__init__(self, runtime, field)
   7.126 -        else:
   7.127 -            N_squared_list = [ runtime.players[player_id].pubkey['n_square'] for player_id in runtime.players.keys()]
   7.128 -            partial_share_contents = PartialShareContents(value, enc_shares, N_squared_list)
   7.129 -            Share.__init__(self, runtime, field, partial_share_contents)
   7.130 -
   7.131 -
   7.132 -class PartialShareGenerator:
   7.133 -
   7.134 -    def __init__(self, Zp, runtime, random, paillier):
   7.135 -        self.paillier = paillier
   7.136 -        self.Zp = Zp
   7.137 -        self.runtime = runtime
   7.138 -        self.random = random
   7.139 -
   7.140 -    def generate_share(self, value):
   7.141 -        self.runtime.increment_pc()
   7.142 -        
   7.143 -        r = [self.Zp(self.random.randint(0, self.Zp.modulus - 1)) # TODO: Exclusve?
   7.144 -             for _ in range(self.runtime.num_players - 1)]
   7.145 -        if self.runtime.id == 1:
   7.146 -            share = value - sum(r)
   7.147 -        else:
   7.148 -            share = r[self.runtime.id - 2]
   7.149 -        enc_share = self.paillier.encrypt(share.value)
   7.150 -        enc_shares = _convolute(self.runtime, enc_share)
   7.151 -        def create_partial_share(enc_shares, share):
   7.152 -            return PartialShare(self.runtime, self.Zp, share, enc_shares)
   7.153 -        self.runtime.schedule_callback(enc_shares, create_partial_share, share)
   7.154 -        return enc_shares
   7.155 -
   7.156 -    def generate_random_shares(self, n):
   7.157 -        self.runtime.increment_pc()
   7.158 -        N_squared_list = [ self.runtime.players[player_id].pubkey['n_square'] for player_id in self.runtime.players]
   7.159 -        shares = [PartialShare(self.runtime, self.Zp) for _ in xrange(n)]
   7.160 -        for inx in xrange(n):
   7.161 -            r = self.random.randint(0, self.Zp.modulus - 1)
   7.162 -            ri = self.Zp(r)
   7.163 -            enc_share = self.paillier.encrypt(ri.value)
   7.164 -            enc_shares = _convolute(self.runtime, enc_share)
   7.165 -            def create_partial_share(enc_shares, ri, s, N_squared_list):
   7.166 -                s.callback(PartialShareContents(ri, enc_shares, N_squared_list))
   7.167 -            self.runtime.schedule_callback(enc_shares,
   7.168 -                                           create_partial_share,
   7.169 -                                           ri,
   7.170 -                                           shares[inx],
   7.171 -                                           N_squared_list)
   7.172 -        return shares
   7.173 -
   7.174 -class ShareGenerator(PartialShareGenerator):
   7.175 -
   7.176 -    def __init__(self, Zp, runtime, random, paillier, u_bound, alpha):
   7.177 -        self.u_bound = u_bound
   7.178 -        self.alpha = alpha
   7.179 -        PartialShareGenerator.__init__(self, Zp, runtime, random, paillier)
   7.180 -
   7.181 -    def generate_share(self, value):
   7.182 -        self.runtime.increment_pc()
   7.183 -        partial_share = PartialShareGenerator.generate_share(self, value)
   7.184 -        full_share = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
   7.185 -                             self.random, self.paillier, [partial_share])
   7.186 -        return full_share[0]
   7.187 -    
   7.188 -    def generate_random_shares(self, n):
   7.189 -        self.runtime.increment_pc()
   7.190 -        partial_shares = PartialShareGenerator.generate_random_shares(self, n)
   7.191 -        return add_macs(self.runtime, self.Zp, self.u_bound, self.alpha,
   7.192 -                        self.random, self.paillier, partial_shares)
   7.193 -
   7.194 -class ModifiedPaillier(object):
   7.195 -    """A slight modification of the Paillier cryptosystem.
   7.196 -
   7.197 -    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
   7.198 -    than the usual Z_n where n is the Paillier modulus.
   7.199 -
   7.200 -    See Ivan's paper, beginning of section 6.
   7.201 -    """
   7.202 -
   7.203 -    def __init__(self, runtime, random):
   7.204 -        self.runtime = runtime;
   7.205 -        self.random = random
   7.206 -
   7.207 -    def _f(self, x, n):
   7.208 -        if x >= 0:
   7.209 -            return x
   7.210 -        else:
   7.211 -            return n + x
   7.212 -
   7.213 -    def _f_inverse(self, y, n):
   7.214 -        if 0 <= y <= (n + 1) / 2:
   7.215 -            return y
   7.216 -        else:
   7.217 -            return y - n
   7.218 -
   7.219 -    def encrypt(self, value, player_id=None):
   7.220 -        """Encrypt using public key of player player_id.
   7.221 -
   7.222 -        Defaults to own public key.
   7.223 -        """
   7.224 -        assert isinstance(value, int) or isinstance(value, long), \
   7.225 -            "paillier: encrypts only integers and longs, got %s" % value.__class__
   7.226 -        if not player_id:
   7.227 -            player_id = self.runtime.id
   7.228 -        n = self.runtime.players[player_id].pubkey['n']
   7.229 -        min = -(n - 1) / 2 + 1
   7.230 -        max = (n + 1) / 2
   7.231 -        assert min <= value <= max, \
   7.232 -            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
   7.233 -            "[%d ; %d]"  % (value, min, max)
   7.234 -        pubkey = self.runtime.players[player_id].pubkey
   7.235 -        randomness = self.random.randint(1, long(n))
   7.236 -        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
   7.237 -
   7.238 -    def decrypt(self, enc_value):
   7.239 -        """Decrypt using own private key."""
   7.240 -        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
   7.241 -            "paillier decrypts only longs, got %s" % enc_value.__class__
   7.242 -        n = self.runtime.players[self.runtime.id].pubkey['n']
   7.243 -        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
   7.244 -        assert 0 <= enc_value < n_square, \
   7.245 -            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
   7.246 -            % (enc_value, n_square)
   7.247 -        seckey = self.runtime.players[self.runtime.id].seckey
   7.248 -        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
   7.249 -
   7.250 -    def get_modulus(self, player_id):
   7.251 -        return self.runtime.players[player_id].pubkey['n']
   7.252 -
   7.253 -    def get_modulus_square(self, player_id):
   7.254 -        return self.runtime.players[player_id].pubkey['n_square']
   7.255 -
   7.256 -def add_macs(runtime, field, u_bound, alpha, random, paillier, partial_shares):
   7.257 -    """Adds macs to the set of PartialBeDOZaShares.
   7.258 -        
   7.259 -    Returns a deferred which yields a list of full shares, e.g.
   7.260 -    including macs.  (the full shares are deferreds of type
   7.261 -    BeDOZaShare.)
   7.262 -    """        
   7.263 -    # TODO: Would be nice with a class ShareContents like the class
   7.264 -    # PartialShareContents used here.
   7.265 -        
   7.266 -    runtime.increment_pc() # Huh!?
   7.267 -
   7.268 -    def do_add_macs(partial_share_contents, result_shares):
   7.269 -        num_players = runtime.num_players
   7.270 -        lists_of_mac_keys = [ [] for x in runtime.players ]
   7.271 -        lists_of_c_list = [ [] for x in runtime.players ]
   7.272 -        for partial_share_content in partial_share_contents:
   7.273 -            for j in xrange(0, num_players):
   7.274 -                # TODO: This is probably not the fastes way to generate
   7.275 -                # the betas.
   7.276 -                beta = random.randint(0, u_bound)
   7.277 -                # TODO: Outcommented until mod paillier works for negative numbers.
   7.278 -                # if rand.choice([True, False]):
   7.279 -                #    beta = -beta
   7.280 -                enc_beta = paillier.encrypt(beta, player_id=j + 1)
   7.281 -                c_j = partial_share_content.enc_shares[j]
   7.282 -                n2 = paillier.get_modulus_square(j + 1)
   7.283 -                c = (pow(c_j, alpha, n2) * enc_beta) % n2
   7.284 -                lists_of_c_list[j].append(c)
   7.285 -                lists_of_mac_keys[j].append(field(beta))
   7.286 -
   7.287 -        received_cs = _send(runtime, lists_of_c_list, deserialize=eval)
   7.288 -
   7.289 -        def finish_sharing(recevied_cs, partial_share_contents, lists_of_mac_keys, result_shares):
   7.290 -            shares = []               
   7.291 -            for inx in xrange(0, len(partial_share_contents)):
   7.292 -                mac_keys = []
   7.293 -                decrypted_cs = []
   7.294 -                for c_list, mkeys in zip(recevied_cs,
   7.295 -                                         lists_of_mac_keys):
   7.296 -                    decrypted_cs.append(field(paillier.decrypt(c_list[inx])))
   7.297 -                    mac_keys.append(mkeys[inx])
   7.298 -                partial_share = partial_share_contents[inx]
   7.299 -                mac_key_list = BeDOZaKeyList(alpha, mac_keys)
   7.300 -
   7.301 -                mac_msg_list = BeDOZaMACList(decrypted_cs)
   7.302 -                result_shares[inx].callback(BeDOZaShareContents(partial_share.value,
   7.303 -                                                                mac_key_list,
   7.304 -                                                                mac_msg_list))
   7.305 -            return shares
   7.306 -
   7.307 -        runtime.schedule_callback(received_cs, finish_sharing, partial_share_contents, lists_of_mac_keys, result_shares)
   7.308 -        return received_cs
   7.309 -
   7.310 -    result_shares = [Share(runtime, field) for x in xrange(len(partial_shares))]
   7.311 -    runtime.schedule_callback(gatherResults(partial_shares),
   7.312 -                              do_add_macs,
   7.313 -                              result_shares)
   7.314 -    return result_shares
   7.315 -
   7.316 -
   7.317 -class TripleGenerator(object):
   7.318 -
   7.319 -    def __init__(self, runtime, p, random):
   7.320 -        assert p > 1
   7.321 -        self.random = random
   7.322 -        # TODO: Generate Paillier cipher with N_i sufficiently larger than p
   7.323 -        self.runtime = runtime
   7.324 -        self.p = p
   7.325 -        self.Zp = GF(p)
   7.326 -        self.k = self._bit_length_of(p)
   7.327 -        self.u_bound = 2**(4 * self.k)
   7.328 -
   7.329 -        paillier_random = Random(self.random.getrandbits(128))
   7.330 -        alpha_random = Random(self.random.getrandbits(128))
   7.331 -        self.paillier = ModifiedPaillier(runtime, paillier_random)
   7.332 -        
   7.333 -        # Debug output.
   7.334 -        #print "n_%d**2:%d" % (runtime.id, self.paillier.pubkey['n_square'])
   7.335 -        #print "n_%d:%d" % (runtime.id, self.paillier.pubkey['n'])
   7.336 -        #print "n_%d bitlength: %d" % (runtime.id, self._bit_length_of(self.paillier.pubkey['n']))
   7.337 -
   7.338 -        #self.Zp = GF(p)
   7.339 -        #self.Zn2 = GF(self.paillier.pubkey['n_square'])
   7.340 -        #self.alpha = self.Zp(self.random.randint(0, p - 1))
   7.341 -        self.alpha = alpha_random.randint(0, p - 1)
   7.342 -        self.n2 = runtime.players[runtime.id].pubkey['n_square']
   7.343 -
   7.344 -    def _bit_length_of(self, i):
   7.345 -        bit_length = 0
   7.346 -        while i:
   7.347 -            i >>= 1
   7.348 -            bit_length += 1
   7.349 -        return bit_length
   7.350 -
   7.351 -    def generate_triples(self, n):
   7.352 -        """Generates and returns a set of n triples.
   7.353 -        
   7.354 -        Data sent over the network is packaged in large hunks in order
   7.355 -        to optimize. TODO: Explain better.
   7.356 -
   7.357 -        TODO: This method needs to have enough RAM to represent all n
   7.358 -        triples in memory at the same time. Is there a nice way to
   7.359 -        stream this, e.g. by using Python generators?
   7.360 -        """
   7.361 -
   7.362 -        self.runtime.increment_pc()
   7.363 -        
   7.364 -        def check(v, a, b, c):
   7.365 -            if v.value != 0:
   7.366 -                raise Exception("TripleTest failed - The two triples were inconsistent.")
   7.367 -            return (a, b, c)
   7.368 -        
   7.369 -        def compute_value(r, a, b, c, x, y, z):
   7.370 -            l = self.runtime._cmul(r, x, self.Zp)
   7.371 -            m = self.runtime._cmul(r, y, self.Zp)
   7.372 -            k = self.runtime._cmul(r*r, z, self.Zp)
   7.373 -            v = c - self.runtime._basic_multiplication(a, b, l, m, k)
   7.374 -            v = self.runtime.open(v)
   7.375 -            v.addCallback(check, a, b, c)
   7.376 -            return v
   7.377 -
   7.378 -        gen = ShareGenerator(self.Zp, self.runtime, self.random, self.paillier, self.u_bound, self.alpha)
   7.379 -        
   7.380 -        random_shares = gen.generate_random_shares(n)
   7.381 -
   7.382 -        results = [Deferred() for _ in xrange(n)]
   7.383 -        
   7.384 -        triples = self._generate_passive_triples(2 * n)
   7.385 -
   7.386 -        for inx in xrange(n):
   7.387 -            a = triples[inx]
   7.388 -            b = triples[inx + 2 * n]
   7.389 -            c = triples[inx + 4 * n]
   7.390 -            x = triples[inx + n]
   7.391 -            y = triples[inx + 3 * n]
   7.392 -            z = triples[inx + 5 * n]
   7.393 -            r = self.runtime.open(random_shares[inx])
   7.394 -            self.runtime.schedule_callback(r, compute_value, a, b, c, x, y, z)
   7.395 -            r.chainDeferred(results[inx])
   7.396 -        return results
   7.397 -          
   7.398 -        # TODO: Do some ZK stuff.
   7.399 -
   7.400 -    def _generate_passive_triples(self, n):
   7.401 -        """Generates and returns a list of 3n shares corresponding to
   7.402 -        n passive tuples. The first n are the a's, then comes n b's
   7.403 -        followed by n c's.
   7.404 -        
   7.405 -        Consistency is only guaranteed if all players follow the protool.
   7.406 -        """
   7.407 -
   7.408 -        self.runtime.increment_pc()
   7.409 -        
   7.410 -        gen = PartialShareGenerator(self.Zp, self.runtime, self.random, self.paillier)
   7.411 -        partial_shares = []
   7.412 -        for _ in xrange(2 * n):
   7.413 -             partial_shares.append(gen.generate_share(self.random.randint(0, self.Zp.modulus - 1)))
   7.414 -
   7.415 -
   7.416 -        partial_shares_c = self._full_mul(partial_shares[0:n], partial_shares[n:2*n])
   7.417 -
   7.418 -        full_shares = add_macs(self.runtime, self.Zp, self.u_bound, self.alpha, self.random, self.paillier, partial_shares + partial_shares_c)
   7.419 -
   7.420 -        return full_shares  
   7.421 -
   7.422 -        # for player i:
   7.423 -        #     receive c from player i and set 
   7.424 -        #         m^i=Decrypt(c)
   7.425 -    
   7.426 -    def _mul(self, inx, jnx, ais=None, cjs=None):
   7.427 -        """Multiply each of the field elements in *ais* with the
   7.428 -        corresponding encrypted elements in *cjs*.
   7.429 -        
   7.430 -        Returns a deferred which will yield a list of PartialShareContents.
   7.431 -        """
   7.432 -        CKIND = 1
   7.433 -        DiKIND = 2
   7.434 -        DjKIND = 3
   7.435 -        
   7.436 -        self.runtime.increment_pc()
   7.437 -
   7.438 -        pc = tuple(self.runtime.program_counter)
   7.439 -
   7.440 -        deferreds = []
   7.441 -        zis = []
   7.442 -        if self.runtime.id == inx:
   7.443 -            Nj_square = self.paillier.get_modulus_square(jnx)
   7.444 -            cs = []
   7.445 -            dis = []
   7.446 -            for ai, cj in zip(ais, cjs):
   7.447 -                u = rand.randint(0, self.u_bound)
   7.448 -                Ej_u = self.paillier.encrypt(u, jnx)
   7.449 -                cs.append( (pow(cj, ai.value, Nj_square) * Ej_u) % Nj_square )
   7.450 -                zi = self.Zp(-u)
   7.451 -                zis.append(zi)
   7.452 -                dis.append(self.paillier.encrypt(zi.value, inx))
   7.453 -            self.runtime.protocols[jnx].sendData(pc, CKIND, str(cs))
   7.454 -
   7.455 -            for player_id in self.runtime.players:
   7.456 -                self.runtime.protocols[player_id].sendData(pc, DiKIND, str(dis))
   7.457 -
   7.458 -        if self.runtime.id == jnx:
   7.459 -            cs = Deferred()
   7.460 -            self.runtime._expect_data(inx, CKIND, cs)
   7.461 -            def decrypt(cs, pc, zis):
   7.462 -                zjs = []
   7.463 -                djs = []
   7.464 -                for c in eval(cs):
   7.465 -                    t = self.paillier.decrypt(c)
   7.466 -                    zj = self.Zp(t)
   7.467 -                    zjs.append(zj)
   7.468 -                    djs.append(self.paillier.encrypt(zj.value, jnx))
   7.469 -                for player_id in self.runtime.players:
   7.470 -                    self.runtime.protocols[player_id].sendData(pc, DjKIND, str(djs))
   7.471 -                if not zis == []:
   7.472 -                    return [x + y for x, y in zip(zis, zjs)]
   7.473 -                else:
   7.474 -                    return zjs 
   7.475 -            cs.addCallback(decrypt, pc, zis)
   7.476 -            deferreds.append(cs)
   7.477 -        else:
   7.478 -            zis_deferred = Deferred()
   7.479 -            zis_deferred.callback(zis)
   7.480 -            deferreds.append(zis_deferred)
   7.481 -
   7.482 -        dis = Deferred()
   7.483 -        self.runtime._expect_data(inx, DiKIND, dis)
   7.484 -        djs = Deferred()
   7.485 -        self.runtime._expect_data(jnx, DjKIND, djs)
   7.486 -
   7.487 -        deferreds.append(dis)
   7.488 -        deferreds.append(djs)
   7.489 -        r = gatherResults(deferreds)
   7.490 -        def wrap((values, dis, djs), inx, jnx):
   7.491 -            dis = eval(dis)
   7.492 -            djs = eval(djs)
   7.493 -            n_square_i = self.paillier.get_modulus_square(inx)
   7.494 -            n_square_j = self.paillier.get_modulus_square(jnx)
   7.495 -            N_squared_list = [self.paillier.get_modulus_square(player_id) for player_id in self.runtime.players]
   7.496 -            ps = []
   7.497 -            for v, di, dj in itertools.izip_longest(values, dis, djs, fillvalue=self.Zp(0)):
   7.498 -                value = v 
   7.499 -                enc_shares = len(self.runtime.players) * [1]
   7.500 -                enc_shares[inx - 1] = (enc_shares[inx - 1] * di) % n_square_i
   7.501 -                enc_shares[jnx - 1] = (enc_shares[jnx - 1] * dj) % n_square_j
   7.502 -                ps.append(PartialShareContents(value, enc_shares, N_squared_list))
   7.503 -            return ps
   7.504 -        r.addCallback(wrap, inx, jnx)
   7.505 -        return r
   7.506 -
   7.507 -    def _full_mul(self, a, b):
   7.508 -        """Multiply each of the PartialShares in the list *a* with the
   7.509 -        corresponding PartialShare in the list *b*.
   7.510 -        
   7.511 -        Returns a deferred which will yield a list of PartialShares.
   7.512 -        """
   7.513 -        self.runtime.increment_pc()
   7.514 -        
   7.515 -        def do_full_mul(shares, result_shares):
   7.516 -            """Share content belonging to ai, bi are at:
   7.517 -            shares[i], shares[len(shares) + i].
   7.518 -            """
   7.519 -            deferreds = []
   7.520 -            len_shares = len(shares)
   7.521 -            a_values = [s.value for s in shares[0:len_shares/2]]
   7.522 -            b_enc_shares = []
   7.523 -            for inx in self.runtime.players:              
   7.524 -                b_enc_shares.append([s.enc_shares[inx - 1] for s in shares[len_shares/2:]])
   7.525 -            for inx in xrange(0, len(self.runtime.players)):
   7.526 -                for jnx in xrange(0, len(self.runtime.players)):
   7.527 -                    deferreds.append(self._mul(inx + 1,
   7.528 -                                               jnx + 1,
   7.529 -                                               a_values,
   7.530 -                                               b_enc_shares[jnx]))
   7.531 -                        
   7.532 -            def compute_shares(partialShareContents, len_shares, result_shares):
   7.533 -                num_players = len(self.runtime.players)
   7.534 -                pcs = len(partialShareContents[0]) * [None]
   7.535 -                for ps in partialShareContents:
   7.536 -                    for inx in xrange(0, len(ps)):
   7.537 -                        if pcs[inx] == None:
   7.538 -                            pcs[inx] = ps[inx]
   7.539 -                        else:
   7.540 -                            pcs[inx] += ps[inx]
   7.541 -                for p, s in zip(pcs, result_shares):
   7.542 -                    s.callback(p)
   7.543 -                return None
   7.544 -            d = gatherResults(deferreds)
   7.545 -            d.addCallback(compute_shares, len_shares, result_shares)
   7.546 -            return d
   7.547 -        result_shares = [Share(self.runtime, self.Zp) for x in a]
   7.548 -        self.runtime.schedule_callback(gatherResults(a + b),
   7.549 -                                       do_full_mul,
   7.550 -                                       result_shares)
   7.551 -        return result_shares
   7.552 -
   7.553 -
   7.554 -# TODO: Represent all numbers by GF objects, Zp, Zn, etc.
   7.555 -# E.g. paillier encrypt should return Zn^2 elms and decrypt should
   7.556 -# return Zp elements.
     8.1 --- a/viff/test/test_bedoza_runtime.py	Fri Jul 23 11:18:04 2010 +0200
     8.2 +++ b/viff/test/test_bedoza_runtime.py	Fri Jul 23 13:17:48 2010 +0200
     8.3 @@ -22,7 +22,9 @@
     8.4  from viff.test.util import RuntimeTestCase, protocol
     8.5  from viff.runtime import gather_shares, Share
     8.6  from viff.config import generate_configs
     8.7 -from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaShareContents, BeDOZaKeyList, BeDOZaMACList
     8.8 +from viff.bedoza.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaShareContents
     8.9 +from viff.bedoza.keylist import BeDOZaKeyList
    8.10 +from viff.bedoza.maclist import BeDOZaMACList
    8.11  from viff.field import FieldElement, GF
    8.12  from viff.util import rand
    8.13  
     9.1 --- a/viff/test/test_bedoza_triple.py	Fri Jul 23 11:18:04 2010 +0200
     9.2 +++ b/viff/test/test_bedoza_triple.py	Fri Jul 23 13:17:48 2010 +0200
     9.3 @@ -29,10 +29,11 @@
     9.4  from viff.constants import TEXT
     9.5  from viff.runtime import gather_shares, Share
     9.6  from viff.config import generate_configs
     9.7 -from viff.bedoza import BeDOZaRuntime, BeDOZaShare, BeDOZaKeyList
     9.8  
     9.9 -from viff.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier, PartialShareGenerator, ShareGenerator
    9.10 -from viff.bedoza_triple import _send, _convolute, _convolute_gf_elm, add_macs
    9.11 +from viff.bedoza.bedoza import BeDOZaRuntime, BeDOZaShare
    9.12 +from viff.bedoza.keylist import BeDOZaKeyList
    9.13 +from viff.bedoza.bedoza_triple import TripleGenerator, PartialShare, PartialShareContents, ModifiedPaillier, PartialShareGenerator, ShareGenerator
    9.14 +from viff.bedoza.bedoza_triple import _send, _convolute, _convolute_gf_elm, add_macs
    9.15  
    9.16  from viff.field import FieldElement, GF
    9.17  from viff.config import generate_configs