viff

changeset 1006:68b96c32e06e

Renamed Runtime to PassiveRuntime. I also moved it from viff.runtime to a new viff.passive module.
author Martin Geisler <mg@daimi.au.dk>
date Wed, 29 Oct 2008 15:54:15 +0100
parents 8b46d76bdc75
children 00e057006d2a
files apps/benchmark.py apps/millionaires.py viff/active.py viff/comparison.py viff/passive.py viff/runtime.py viff/test/test_runtime_equal.py viff/test/util.py
diffstat 8 files changed, 447 insertions(+), 406 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Mon Oct 27 09:38:46 2008 +0100
     1.2 +++ b/apps/benchmark.py	Wed Oct 29 15:54:15 2008 +0100
     1.3 @@ -62,8 +62,9 @@
     1.4  from twisted.internet import reactor
     1.5  
     1.6  from viff.field import GF, GF256
     1.7 -from viff.runtime import Runtime, create_runtime, gather_shares, \
     1.8 +from viff.runtime import BasicRuntime, create_runtime, gather_shares, \
     1.9      make_runtime_class
    1.10 +from viff.passive import PassiveRuntime
    1.11  from viff.active import BasicActiveRuntime, \
    1.12      TriplesHyperinvertibleMatricesMixin, TriplesPRSSMixin
    1.13  from viff.comparison import ComparisonToft05Mixin, ComparisonToft07Mixin
    1.14 @@ -122,7 +123,7 @@
    1.15                      operation=operations[0], parallel=True)
    1.16  
    1.17  # Add standard VIFF options.
    1.18 -Runtime.add_options(parser)
    1.19 +BasicRuntime.add_options(parser)
    1.20  
    1.21  (options, args) = parser.parse_args()
    1.22  
    1.23 @@ -277,7 +278,7 @@
    1.24          else:
    1.25              mixins.append(TriplesHyperinvertibleMatricesMixin)
    1.26      else:
    1.27 -        base_runtime_class = Runtime
    1.28 +        base_runtime_class = PassiveRuntime
    1.29  
    1.30      if options.operation == "mul":
    1.31          operation = operator.mul
     2.1 --- a/apps/millionaires.py	Mon Oct 27 09:38:46 2008 +0100
     2.2 +++ b/apps/millionaires.py	Wed Oct 29 15:54:15 2008 +0100
     2.3 @@ -35,7 +35,7 @@
     2.4  from twisted.internet import reactor
     2.5  
     2.6  from viff.field import GF
     2.7 -from viff.runtime import Runtime, create_runtime, gather_shares
     2.8 +from viff.runtime import create_runtime, gather_shares
     2.9  from viff.comparison import Toft05Runtime
    2.10  from viff.config import load_config
    2.11  from viff.util import rand, find_prime
    2.12 @@ -138,7 +138,7 @@
    2.13  
    2.14  # Parse command line arguments.
    2.15  parser = OptionParser()
    2.16 -Runtime.add_options(parser)
    2.17 +Toft05Runtime.add_options(parser)
    2.18  options, args = parser.parse_args()
    2.19  
    2.20  if len(args) == 0:
     3.1 --- a/viff/active.py	Mon Oct 27 09:38:46 2008 +0100
     3.2 +++ b/viff/active.py	Wed Oct 29 15:54:15 2008 +0100
     3.3 @@ -26,7 +26,8 @@
     3.4  from viff import shamir
     3.5  from viff.util import rand
     3.6  from viff.matrix import Matrix, hyper
     3.7 -from viff.runtime import Runtime, Share, increment_pc, preprocess, gather_shares
     3.8 +from viff.passive import PassiveRuntime
     3.9 +from viff.runtime import Share, increment_pc, preprocess, gather_shares
    3.10  
    3.11  
    3.12  class BrachaBroadcastMixin:
    3.13 @@ -443,7 +444,7 @@
    3.14          return 1, succeed([(a_t, b_t, c_t)])
    3.15  
    3.16  
    3.17 -class BasicActiveRuntime(Runtime):
    3.18 +class BasicActiveRuntime(PassiveRuntime):
    3.19      """Basic runtime secure against active adversaries.
    3.20  
    3.21      This class depends on either
     4.1 --- a/viff/comparison.py	Mon Oct 27 09:38:46 2008 +0100
     4.2 +++ b/viff/comparison.py	Wed Oct 29 15:54:15 2008 +0100
     4.3 @@ -25,7 +25,8 @@
     4.4  import math
     4.5  
     4.6  from viff.util import rand, profile
     4.7 -from viff.runtime import Runtime, Share, gather_shares, increment_pc
     4.8 +from viff.runtime import Share, gather_shares, increment_pc
     4.9 +from viff.passive import PassiveRuntime
    4.10  from viff.active import ActiveRuntime
    4.11  from viff.field import GF256, FieldElement
    4.12  
    4.13 @@ -141,7 +142,7 @@
    4.14          return (top, bot)
    4.15  
    4.16  
    4.17 -class Toft05Runtime(ComparisonToft05Mixin, Runtime):
    4.18 +class Toft05Runtime(ComparisonToft05Mixin, PassiveRuntime):
    4.19      """Default mix of :class:`ComparisonToft05Mixin` and
    4.20      :class:`Runtime <viff.runtime.Runtime>`."""
    4.21      pass
    4.22 @@ -338,7 +339,7 @@
    4.23                                                field)
    4.24  
    4.25  
    4.26 -class Toft07Runtime(ComparisonToft07Mixin, Runtime):
    4.27 +class Toft07Runtime(ComparisonToft07Mixin, PassiveRuntime):
    4.28      """Default mix of :class:`ComparisonToft07Mixin` and
    4.29      :class:`Runtime <viff.runtime.Runtime>`.
    4.30      """
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/viff/passive.py	Wed Oct 29 15:54:15 2008 +0100
     5.3 @@ -0,0 +1,413 @@
     5.4 +# Copyright 2008 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 +"""Passively secure VIFF runtime."""
    5.22 +
    5.23 +from viff import shamir
    5.24 +from viff.runtime import BasicRuntime, increment_pc, Share, ShareList, gather_shares
    5.25 +from viff.prss import prss, prss_lsb, prss_zero
    5.26 +from viff.field import GF256, FieldElement
    5.27 +from viff.util import rand, profile
    5.28 +
    5.29 +
    5.30 +class PassiveRuntime(BasicRuntime):
    5.31 +    """The VIFF runtime.
    5.32 +
    5.33 +    The runtime is used for sharing values (:meth:`shamir_share` or
    5.34 +    :meth:`prss_share`) into :class:`Share` object and opening such
    5.35 +    shares (:meth:`open`) again. Calculations on shares is normally
    5.36 +    done through overloaded arithmetic operations, but it is also
    5.37 +    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
    5.38 +    prefers.
    5.39 +
    5.40 +    Each player in the protocol uses a :class:`Runtime` object. To
    5.41 +    create an instance and connect it correctly with the other
    5.42 +    players, please use the :func:`create_runtime` function instead of
    5.43 +    instantiating a Runtime directly. The :func:`create_runtime`
    5.44 +    function will take care of setting up network connections and
    5.45 +    return a :class:`Deferred` which triggers with the
    5.46 +    :class:`Runtime` object when it is ready.
    5.47 +    """
    5.48 +
    5.49 +    def __init__(self, player, threshold, options=None):
    5.50 +        """Initialize runtime."""
    5.51 +        BasicRuntime.__init__(self, player, threshold, options)
    5.52 +
    5.53 +    @increment_pc
    5.54 +    def open(self, share, receivers=None, threshold=None):
    5.55 +        """Open a secret sharing.
    5.56 +
    5.57 +        The *receivers* are the players that will eventually obtain
    5.58 +        the opened result. The default is to let everybody know the
    5.59 +        result. By default the :attr:`threshold` + 1 shares are
    5.60 +        reconstructed, but *threshold* can be used to override this.
    5.61 +
    5.62 +        Communication cost: every player sends one share to each
    5.63 +        receiving player.
    5.64 +        """
    5.65 +        assert isinstance(share, Share)
    5.66 +        # all players receive result by default
    5.67 +        if receivers is None:
    5.68 +            receivers = self.players.keys()
    5.69 +        if threshold is None:
    5.70 +            threshold = self.threshold
    5.71 +
    5.72 +        def filter_good_shares(results):
    5.73 +            # Filter results, which is a list of (success, share)
    5.74 +            # pairs.
    5.75 +            return [result[1] for result in results
    5.76 +                    if result is not None and result[0]][:threshold+1]
    5.77 +
    5.78 +        def recombine(shares):
    5.79 +            assert len(shares) > threshold
    5.80 +            result = ShareList(shares, threshold+1)
    5.81 +            result.addCallback(filter_good_shares)
    5.82 +            result.addCallback(shamir.recombine)
    5.83 +            return result
    5.84 +
    5.85 +        def exchange(share):
    5.86 +            # Send share to all receivers.
    5.87 +            for peer_id in receivers:
    5.88 +                if peer_id != self.id:
    5.89 +                    pc = tuple(self.program_counter)
    5.90 +                    self.protocols[peer_id].sendShare(pc, share)
    5.91 +            # Receive and recombine shares if this player is a receiver.
    5.92 +            if self.id in receivers:
    5.93 +                deferreds = []
    5.94 +                for peer_id in self.players:
    5.95 +                    if peer_id == self.id:
    5.96 +                        d = Share(self, share.field, (share.field(peer_id), share))
    5.97 +                    else:
    5.98 +                        d = self._expect_share(peer_id, share.field)
    5.99 +                        self.schedule_callback(d, lambda s, peer_id: (s.field(peer_id), s), peer_id)
   5.100 +                    deferreds.append(d)
   5.101 +                return recombine(deferreds)
   5.102 +
   5.103 +        result = share.clone()
   5.104 +        self.schedule_callback(result, exchange)
   5.105 +        if self.id in receivers:
   5.106 +            return result
   5.107 +
   5.108 +    @profile
   5.109 +    def add(self, share_a, share_b):
   5.110 +        """Addition of shares.
   5.111 +
   5.112 +        Communication cost: none.
   5.113 +        """
   5.114 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.115 +        if not isinstance(share_a, Share):
   5.116 +            share_a = Share(self, field, share_a)
   5.117 +        if not isinstance(share_b, Share):
   5.118 +            share_b = Share(self, field, share_b)
   5.119 +
   5.120 +        result = gather_shares([share_a, share_b])
   5.121 +        result.addCallback(lambda (a, b): a + b)
   5.122 +        return result
   5.123 +
   5.124 +    def sub(self, share_a, share_b):
   5.125 +        """Subtraction of shares.
   5.126 +
   5.127 +        Communication cost: none.
   5.128 +        """
   5.129 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.130 +        if not isinstance(share_a, Share):
   5.131 +            share_a = Share(self, field, share_a)
   5.132 +        if not isinstance(share_b, Share):
   5.133 +            share_b = Share(self, field, share_b)
   5.134 +
   5.135 +        result = gather_shares([share_a, share_b])
   5.136 +        result.addCallback(lambda (a, b): a - b)
   5.137 +        return result
   5.138 +
   5.139 +    @profile
   5.140 +    @increment_pc
   5.141 +    def mul(self, share_a, share_b):
   5.142 +        """Multiplication of shares.
   5.143 +
   5.144 +        Communication cost: 1 Shamir sharing.
   5.145 +        """
   5.146 +        assert isinstance(share_a, Share) or isinstance(share_b, Share), \
   5.147 +            "At least one of share_a and share_b must be a Share."
   5.148 +
   5.149 +        if not isinstance(share_a, Share):
   5.150 +            # Then share_b must be a Share => local multiplication. We
   5.151 +            # clone first to avoid changing share_b.
   5.152 +            result = share_b.clone()
   5.153 +            result.addCallback(lambda b: share_a * b)
   5.154 +            return result
   5.155 +        if not isinstance(share_b, Share):
   5.156 +            # Likewise when share_b is a constant.
   5.157 +            result = share_a.clone()
   5.158 +            result.addCallback(lambda a: a * share_b)
   5.159 +            return result
   5.160 +
   5.161 +        # At this point both share_a and share_b must be Share
   5.162 +        # objects. So we wait on them, multiply and reshare.
   5.163 +
   5.164 +        def share_recombine(number):
   5.165 +            shares = shamir.share(number, self.threshold, self.num_players)
   5.166 +
   5.167 +            exchanged_shares = []
   5.168 +            for peer_id, share in shares:
   5.169 +                d = self._exchange_shares(peer_id.value, share)
   5.170 +                d.addCallback(lambda share, peer_id: (peer_id, share), peer_id)
   5.171 +                exchanged_shares.append(d)
   5.172 +
   5.173 +            # Recombine the first 2t+1 shares.
   5.174 +            result = gather_shares(exchanged_shares[:2*self.threshold+1])
   5.175 +            result.addCallback(shamir.recombine)
   5.176 +            return result
   5.177 +
   5.178 +        result = gather_shares([share_a, share_b])
   5.179 +        result.addCallback(lambda (a, b): a * b)
   5.180 +        self.schedule_callback(result, share_recombine)
   5.181 +        return result
   5.182 +
   5.183 +    @increment_pc
   5.184 +    def xor(self, share_a, share_b):
   5.185 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.186 +        if not isinstance(share_a, Share):
   5.187 +            if not isinstance(share_a, FieldElement):
   5.188 +                share_a = field(share_a)
   5.189 +            share_a = Share(self, field, share_a)
   5.190 +        if not isinstance(share_b, Share):
   5.191 +            if not isinstance(share_b, FieldElement):
   5.192 +                share_b = field(share_b)
   5.193 +            share_b = Share(self, field, share_b)
   5.194 +
   5.195 +        if field is GF256:
   5.196 +            return share_a + share_b
   5.197 +        else:
   5.198 +            return share_a + share_b - 2 * share_a * share_b
   5.199 +
   5.200 +    @increment_pc
   5.201 +    def prss_share(self, inputters, field, element=None):
   5.202 +        """Creates pseudo-random secret sharings.
   5.203 +
   5.204 +        This protocol creates a secret sharing for each player in the
   5.205 +        subset of players specified in *inputters*. Each inputter
   5.206 +        provides an integer. The result is a list of shares, one for
   5.207 +        each inputter.
   5.208 +
   5.209 +        The protocol uses the pseudo-random secret sharing technique
   5.210 +        described in the paper "Share Conversion, Pseudorandom
   5.211 +        Secret-Sharing and Applications to Secure Computation" by
   5.212 +        Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC
   5.213 +        2005, LNCS 3378. `Download
   5.214 +        <http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps>`__
   5.215 +
   5.216 +        Communication cost: Each inputter does one broadcast.
   5.217 +        """
   5.218 +        # Verifying parameters.
   5.219 +        if element is None:
   5.220 +            assert self.id not in inputters, "No element given."
   5.221 +        else:
   5.222 +            assert self.id in inputters, \
   5.223 +                "Element given, but we are not sharing?"
   5.224 +
   5.225 +        n = self.num_players
   5.226 +
   5.227 +        # Key used for PRSS.
   5.228 +        key = tuple(self.program_counter)
   5.229 +
   5.230 +        # The shares for which we have all the keys.
   5.231 +        all_shares = []
   5.232 +
   5.233 +        # Shares we calculate from doing PRSS with the other players.
   5.234 +        tmp_shares = {}
   5.235 +
   5.236 +        prfs = self.players[self.id].dealer_prfs(field.modulus)
   5.237 +
   5.238 +        # Compute and broadcast correction value.
   5.239 +        if self.id in inputters:
   5.240 +            for player in self.players:
   5.241 +                share = prss(n, player, field, prfs[self.id], key)
   5.242 +                all_shares.append((field(player), share))
   5.243 +            shared = shamir.recombine(all_shares[:self.threshold+1])
   5.244 +            correction = element - shared
   5.245 +            # if this player is inputter then broadcast correction value
   5.246 +            # TODO: more efficient broadcast?
   5.247 +            pc = tuple(self.program_counter)
   5.248 +            for peer_id in self.players:
   5.249 +                if self.id != peer_id:
   5.250 +                    self.protocols[peer_id].sendShare(pc, correction)
   5.251 +
   5.252 +        # Receive correction value from inputters and compute share.
   5.253 +        result = []
   5.254 +        for player in inputters:
   5.255 +            tmp_shares[player] = prss(n, self.id, field, prfs[player], key)
   5.256 +            if player == self.id:
   5.257 +                d = Share(self, field, correction)
   5.258 +            else:
   5.259 +                d = self._expect_share(player, field)
   5.260 +            d.addCallback(lambda c, s: s + c, tmp_shares[player])
   5.261 +            result.append(d)
   5.262 +
   5.263 +        # Unpack a singleton list.
   5.264 +        if len(result) == 1:
   5.265 +            return result[0]
   5.266 +        else:
   5.267 +            return result
   5.268 +
   5.269 +    @increment_pc
   5.270 +    def prss_share_random(self, field, binary=False):
   5.271 +        """Generate shares of a uniformly random element from the field given.
   5.272 +
   5.273 +        If binary is True, a 0/1 element is generated. No player
   5.274 +        learns the value of the element.
   5.275 +
   5.276 +        Communication cost: none if binary=False, 1 open otherwise.
   5.277 +        """
   5.278 +        if field is GF256 and binary:
   5.279 +            modulus = 2
   5.280 +        else:
   5.281 +            modulus = field.modulus
   5.282 +
   5.283 +        # Key used for PRSS.
   5.284 +        prss_key = tuple(self.program_counter)
   5.285 +        prfs = self.players[self.id].prfs(modulus)
   5.286 +        share = prss(self.num_players, self.id, field, prfs, prss_key)
   5.287 +
   5.288 +        if field is GF256 or not binary:
   5.289 +            return Share(self, field, share)
   5.290 +
   5.291 +        # Open the square and compute a square-root
   5.292 +        result = self.open(Share(self, field, share*share),
   5.293 +                           threshold=2*self.threshold)
   5.294 +
   5.295 +        def finish(square, share, binary):
   5.296 +            if square == 0:
   5.297 +                # We were unlucky, try again...
   5.298 +                return self.prss_share_random(field, binary)
   5.299 +            else:
   5.300 +                # We can finish the calculation
   5.301 +                root = square.sqrt()
   5.302 +                # When the root is computed, we divide the share and
   5.303 +                # convert the resulting -1/1 share into a 0/1 share.
   5.304 +                return Share(self, field, (share/root + 1) / 2)
   5.305 +
   5.306 +        self.schedule_callback(result, finish, share, binary)
   5.307 +        return result
   5.308 +
   5.309 +    @increment_pc
   5.310 +    def prss_share_zero(self, field):
   5.311 +        """Generate shares of the zero element from the field given.
   5.312 +
   5.313 +        Communication cost: none.
   5.314 +        """
   5.315 +        # Key used for PRSS.
   5.316 +        prss_key = tuple(self.program_counter)
   5.317 +        prfs = self.players[self.id].prfs(field.modulus)
   5.318 +        zero_share = prss_zero(self.num_players, self.threshold, self.id,
   5.319 +                               field, prfs, prss_key)
   5.320 +        return Share(self, field, zero_share)
   5.321 +
   5.322 +    @increment_pc
   5.323 +    def prss_double_share(self, field):
   5.324 +        """Make a double-sharing using PRSS.
   5.325 +
   5.326 +        The pair of shares will have degree t and 2t where t is the
   5.327 +        default threshold for the runtime.
   5.328 +        """
   5.329 +        r_t = self.prss_share_random(field)
   5.330 +        z_2t = self.prss_share_zero(field)
   5.331 +        return (r_t, r_t + z_2t)
   5.332 +
   5.333 +    @increment_pc
   5.334 +    def prss_share_bit_double(self, field):
   5.335 +        """Share a random bit over *field* and GF256.
   5.336 +
   5.337 +        The protocol is described in "Efficient Conversion of
   5.338 +        Secret-shared Values Between Different Fields" by Ivan Damgård
   5.339 +        and Rune Thorbek available as `Cryptology ePrint Archive,
   5.340 +        Report 2008/221 <http://eprint.iacr.org/2008/221>`__.
   5.341 +        """
   5.342 +        n = self.num_players
   5.343 +        k = self.options.security_parameter
   5.344 +        prfs = self.players[self.id].prfs(2**k)
   5.345 +        prss_key = tuple(self.program_counter)
   5.346 +
   5.347 +        b_p = self.prss_share_random(field, binary=True)
   5.348 +        r_p, r_lsb = prss_lsb(n, self.id, field, prfs, prss_key)
   5.349 +
   5.350 +        b = self.open(b_p + r_p)
   5.351 +        # Extract least significant bit and change field to GF256.
   5.352 +        b.addCallback(lambda i: GF256(i.value & 1))
   5.353 +        b.field = GF256
   5.354 +
   5.355 +        # Use r_lsb to flip b as needed.
   5.356 +        return (b_p, b ^ r_lsb)
   5.357 +
   5.358 +    @increment_pc
   5.359 +    def prss_shamir_share_bit_double(self, field):
   5.360 +        """Shamir share a random bit over *field* and GF256."""
   5.361 +        n = self.num_players
   5.362 +        k = self.options.security_parameter
   5.363 +        prfs = self.players[self.id].prfs(2**k)
   5.364 +        prss_key = tuple(self.program_counter)
   5.365 +        inputters = range(1, self.num_players + 1)
   5.366 +
   5.367 +        ri = rand.randint(0, 2**k - 1)
   5.368 +        ri_p = self.shamir_share(inputters, field, ri)
   5.369 +        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
   5.370 +
   5.371 +        r_p = reduce(self.add, ri_p)
   5.372 +        r_lsb = reduce(self.add, ri_lsb)
   5.373 +
   5.374 +        b_p = self.prss_share_random(field, binary=True)
   5.375 +        b = self.open(b_p + r_p)
   5.376 +        # Extract least significant bit and change field to GF256.
   5.377 +        b.addCallback(lambda i: GF256(i.value & 1))
   5.378 +        b.field = GF256
   5.379 +
   5.380 +        # Use r_lsb to flip b as needed.
   5.381 +        return (b_p, b ^ r_lsb)
   5.382 +
   5.383 +    @increment_pc
   5.384 +    def shamir_share(self, inputters, field, number=None, threshold=None):
   5.385 +        """Secret share *number* over *field* using Shamir's method.
   5.386 +
   5.387 +        The number is shared using polynomial of degree *threshold*
   5.388 +        (defaults to :attr:`threshold`). Returns a list of shares
   5.389 +        unless there is only one inputter in which case the
   5.390 +        share is returned directly.
   5.391 +
   5.392 +        Communication cost: n elements transmitted.
   5.393 +        """
   5.394 +        assert number is None or self.id in inputters
   5.395 +        if threshold is None:
   5.396 +            threshold = self.threshold
   5.397 +
   5.398 +        results = []
   5.399 +        for peer_id in inputters:
   5.400 +            if peer_id == self.id:
   5.401 +                pc = tuple(self.program_counter)
   5.402 +                shares = shamir.share(field(number), threshold,
   5.403 +                                      self.num_players)
   5.404 +                for other_id, share in shares:
   5.405 +                    if other_id.value == self.id:
   5.406 +                        results.append(Share(self, share.field, share))
   5.407 +                    else:
   5.408 +                        self.protocols[other_id.value].sendShare(pc, share)
   5.409 +            else:
   5.410 +                results.append(self._expect_share(peer_id, field))
   5.411 +
   5.412 +        # Unpack a singleton list.
   5.413 +        if len(results) == 1:
   5.414 +            return results[0]
   5.415 +        else:
   5.416 +            return results
     6.1 --- a/viff/runtime.py	Mon Oct 27 09:38:46 2008 +0100
     6.2 +++ b/viff/runtime.py	Wed Oct 29 15:54:15 2008 +0100
     6.3 @@ -671,399 +671,17 @@
     6.4              wait_list.append(ready)
     6.5          return DeferredList(wait_list)
     6.6  
     6.7 -class Runtime(BasicRuntime):
     6.8 -    """The VIFF runtime.
     6.9  
    6.10 -    The runtime is used for sharing values (:meth:`shamir_share` or
    6.11 -    :meth:`prss_share`) into :class:`Share` object and opening such
    6.12 -    shares (:meth:`open`) again. Calculations on shares is normally
    6.13 -    done through overloaded arithmetic operations, but it is also
    6.14 -    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
    6.15 -    prefers.
    6.16 -
    6.17 -    Each player in the protocol uses a :class:`Runtime` object. To
    6.18 -    create an instance and connect it correctly with the other
    6.19 -    players, please use the :func:`create_runtime` function instead of
    6.20 -    instantiating a Runtime directly. The :func:`create_runtime`
    6.21 -    function will take care of setting up network connections and
    6.22 -    return a :class:`Deferred` which triggers with the
    6.23 -    :class:`Runtime` object when it is ready.
    6.24 +def make_runtime_class(runtime_class=None, mixins=None):
    6.25 +    """Creates a new runtime class with *runtime_class* as a base
    6.26 +    class mixing in the *mixins*. By default
    6.27 +    :class:`viff.passive.PassiveRuntime` will be used.
    6.28      """
    6.29 -
    6.30 -    def __init__(self, player, threshold, options=None):
    6.31 -        """Initialize runtime."""
    6.32 -        BasicRuntime.__init__(self, player, threshold, options)
    6.33 -
    6.34 -    @increment_pc
    6.35 -    def open(self, share, receivers=None, threshold=None):
    6.36 -        """Open a secret sharing.
    6.37 -
    6.38 -        The *receivers* are the players that will eventually obtain
    6.39 -        the opened result. The default is to let everybody know the
    6.40 -        result. By default the :attr:`threshold` + 1 shares are
    6.41 -        reconstructed, but *threshold* can be used to override this.
    6.42 -
    6.43 -        Communication cost: every player sends one share to each
    6.44 -        receiving player.
    6.45 -        """
    6.46 -        assert isinstance(share, Share)
    6.47 -        # all players receive result by default
    6.48 -        if receivers is None:
    6.49 -            receivers = self.players.keys()
    6.50 -        if threshold is None:
    6.51 -            threshold = self.threshold
    6.52 -
    6.53 -        def filter_good_shares(results):
    6.54 -            # Filter results, which is a list of (success, share)
    6.55 -            # pairs.
    6.56 -            return [result[1] for result in results
    6.57 -                    if result is not None and result[0]][:threshold+1]
    6.58 -
    6.59 -        def recombine(shares):
    6.60 -            assert len(shares) > threshold
    6.61 -            result = ShareList(shares, threshold+1)
    6.62 -            result.addCallback(filter_good_shares)
    6.63 -            result.addCallback(shamir.recombine)
    6.64 -            return result
    6.65 -
    6.66 -        def exchange(share):
    6.67 -            # Send share to all receivers.
    6.68 -            for peer_id in receivers:
    6.69 -                if peer_id != self.id:
    6.70 -                    pc = tuple(self.program_counter)
    6.71 -                    self.protocols[peer_id].sendShare(pc, share)
    6.72 -            # Receive and recombine shares if this player is a receiver.
    6.73 -            if self.id in receivers:
    6.74 -                deferreds = []
    6.75 -                for peer_id in self.players:
    6.76 -                    if peer_id == self.id:
    6.77 -                        d = Share(self, share.field, (share.field(peer_id), share))
    6.78 -                    else:
    6.79 -                        d = self._expect_share(peer_id, share.field)
    6.80 -                        self.schedule_callback(d, lambda s, peer_id: (s.field(peer_id), s), peer_id)
    6.81 -                    deferreds.append(d)
    6.82 -                return recombine(deferreds)
    6.83 -
    6.84 -        result = share.clone()
    6.85 -        self.schedule_callback(result, exchange)
    6.86 -        if self.id in receivers:
    6.87 -            return result
    6.88 -
    6.89 -    @profile
    6.90 -    def add(self, share_a, share_b):
    6.91 -        """Addition of shares.
    6.92 -
    6.93 -        Communication cost: none.
    6.94 -        """
    6.95 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
    6.96 -        if not isinstance(share_a, Share):
    6.97 -            share_a = Share(self, field, share_a)
    6.98 -        if not isinstance(share_b, Share):
    6.99 -            share_b = Share(self, field, share_b)
   6.100 -
   6.101 -        result = gather_shares([share_a, share_b])
   6.102 -        result.addCallback(lambda (a, b): a + b)
   6.103 -        return result
   6.104 -
   6.105 -    def sub(self, share_a, share_b):
   6.106 -        """Subtraction of shares.
   6.107 -
   6.108 -        Communication cost: none.
   6.109 -        """
   6.110 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
   6.111 -        if not isinstance(share_a, Share):
   6.112 -            share_a = Share(self, field, share_a)
   6.113 -        if not isinstance(share_b, Share):
   6.114 -            share_b = Share(self, field, share_b)
   6.115 -
   6.116 -        result = gather_shares([share_a, share_b])
   6.117 -        result.addCallback(lambda (a, b): a - b)
   6.118 -        return result
   6.119 -
   6.120 -    @profile
   6.121 -    @increment_pc
   6.122 -    def mul(self, share_a, share_b):
   6.123 -        """Multiplication of shares.
   6.124 -
   6.125 -        Communication cost: 1 Shamir sharing.
   6.126 -        """
   6.127 -        assert isinstance(share_a, Share) or isinstance(share_b, Share), \
   6.128 -            "At least one of share_a and share_b must be a Share."
   6.129 -
   6.130 -        if not isinstance(share_a, Share):
   6.131 -            # Then share_b must be a Share => local multiplication. We
   6.132 -            # clone first to avoid changing share_b.
   6.133 -            result = share_b.clone()
   6.134 -            result.addCallback(lambda b: share_a * b)
   6.135 -            return result
   6.136 -        if not isinstance(share_b, Share):
   6.137 -            # Likewise when share_b is a constant.
   6.138 -            result = share_a.clone()
   6.139 -            result.addCallback(lambda a: a * share_b)
   6.140 -            return result
   6.141 -
   6.142 -        # At this point both share_a and share_b must be Share
   6.143 -        # objects. So we wait on them, multiply and reshare.
   6.144 -
   6.145 -        def share_recombine(number):
   6.146 -            shares = shamir.share(number, self.threshold, self.num_players)
   6.147 -
   6.148 -            exchanged_shares = []
   6.149 -            for peer_id, share in shares:
   6.150 -                d = self._exchange_shares(peer_id.value, share)
   6.151 -                d.addCallback(lambda share, peer_id: (peer_id, share), peer_id)
   6.152 -                exchanged_shares.append(d)
   6.153 -
   6.154 -            # Recombine the first 2t+1 shares.
   6.155 -            result = gather_shares(exchanged_shares[:2*self.threshold+1])
   6.156 -            result.addCallback(shamir.recombine)
   6.157 -            return result
   6.158 -
   6.159 -        result = gather_shares([share_a, share_b])
   6.160 -        result.addCallback(lambda (a, b): a * b)
   6.161 -        self.schedule_callback(result, share_recombine)
   6.162 -        return result
   6.163 -
   6.164 -    @increment_pc
   6.165 -    def xor(self, share_a, share_b):
   6.166 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
   6.167 -        if not isinstance(share_a, Share):
   6.168 -            if not isinstance(share_a, FieldElement):
   6.169 -                share_a = field(share_a)
   6.170 -            share_a = Share(self, field, share_a)
   6.171 -        if not isinstance(share_b, Share):
   6.172 -            if not isinstance(share_b, FieldElement):
   6.173 -                share_b = field(share_b)
   6.174 -            share_b = Share(self, field, share_b)
   6.175 -
   6.176 -        if field is GF256:
   6.177 -            return share_a + share_b
   6.178 -        else:
   6.179 -            return share_a + share_b - 2 * share_a * share_b
   6.180 -
   6.181 -    @increment_pc
   6.182 -    def prss_share(self, inputters, field, element=None):
   6.183 -        """Creates pseudo-random secret sharings.
   6.184 -
   6.185 -        This protocol creates a secret sharing for each player in the
   6.186 -        subset of players specified in *inputters*. Each inputter
   6.187 -        provides an integer. The result is a list of shares, one for
   6.188 -        each inputter.
   6.189 -
   6.190 -        The protocol uses the pseudo-random secret sharing technique
   6.191 -        described in the paper "Share Conversion, Pseudorandom
   6.192 -        Secret-Sharing and Applications to Secure Computation" by
   6.193 -        Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC
   6.194 -        2005, LNCS 3378. `Download
   6.195 -        <http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps>`__
   6.196 -
   6.197 -        Communication cost: Each inputter does one broadcast.
   6.198 -        """
   6.199 -        # Verifying parameters.
   6.200 -        if element is None:
   6.201 -            assert self.id not in inputters, "No element given."
   6.202 -        else:
   6.203 -            assert self.id in inputters, \
   6.204 -                "Element given, but we are not sharing?"
   6.205 -
   6.206 -        n = self.num_players
   6.207 -
   6.208 -        # Key used for PRSS.
   6.209 -        key = tuple(self.program_counter)
   6.210 -
   6.211 -        # The shares for which we have all the keys.
   6.212 -        all_shares = []
   6.213 -
   6.214 -        # Shares we calculate from doing PRSS with the other players.
   6.215 -        tmp_shares = {}
   6.216 -
   6.217 -        prfs = self.players[self.id].dealer_prfs(field.modulus)
   6.218 -
   6.219 -        # Compute and broadcast correction value.
   6.220 -        if self.id in inputters:
   6.221 -            for player in self.players:
   6.222 -                share = prss(n, player, field, prfs[self.id], key)
   6.223 -                all_shares.append((field(player), share))
   6.224 -            shared = shamir.recombine(all_shares[:self.threshold+1])
   6.225 -            correction = element - shared
   6.226 -            # if this player is inputter then broadcast correction value
   6.227 -            # TODO: more efficient broadcast?
   6.228 -            pc = tuple(self.program_counter)
   6.229 -            for peer_id in self.players:
   6.230 -                if self.id != peer_id:
   6.231 -                    self.protocols[peer_id].sendShare(pc, correction)
   6.232 -
   6.233 -        # Receive correction value from inputters and compute share.
   6.234 -        result = []
   6.235 -        for player in inputters:
   6.236 -            tmp_shares[player] = prss(n, self.id, field, prfs[player], key)
   6.237 -            if player == self.id:
   6.238 -                d = Share(self, field, correction)
   6.239 -            else:
   6.240 -                d = self._expect_share(player, field)
   6.241 -            d.addCallback(lambda c, s: s + c, tmp_shares[player])
   6.242 -            result.append(d)
   6.243 -
   6.244 -        # Unpack a singleton list.
   6.245 -        if len(result) == 1:
   6.246 -            return result[0]
   6.247 -        else:
   6.248 -            return result
   6.249 -
   6.250 -    @increment_pc
   6.251 -    def prss_share_random(self, field, binary=False):
   6.252 -        """Generate shares of a uniformly random element from the field given.
   6.253 -
   6.254 -        If binary is True, a 0/1 element is generated. No player
   6.255 -        learns the value of the element.
   6.256 -
   6.257 -        Communication cost: none if binary=False, 1 open otherwise.
   6.258 -        """
   6.259 -        if field is GF256 and binary:
   6.260 -            modulus = 2
   6.261 -        else:
   6.262 -            modulus = field.modulus
   6.263 -
   6.264 -        # Key used for PRSS.
   6.265 -        prss_key = tuple(self.program_counter)
   6.266 -        prfs = self.players[self.id].prfs(modulus)
   6.267 -        share = prss(self.num_players, self.id, field, prfs, prss_key)
   6.268 -
   6.269 -        if field is GF256 or not binary:
   6.270 -            return Share(self, field, share)
   6.271 -
   6.272 -        # Open the square and compute a square-root
   6.273 -        result = self.open(Share(self, field, share*share),
   6.274 -                           threshold=2*self.threshold)
   6.275 -
   6.276 -        def finish(square, share, binary):
   6.277 -            if square == 0:
   6.278 -                # We were unlucky, try again...
   6.279 -                return self.prss_share_random(field, binary)
   6.280 -            else:
   6.281 -                # We can finish the calculation
   6.282 -                root = square.sqrt()
   6.283 -                # When the root is computed, we divide the share and
   6.284 -                # convert the resulting -1/1 share into a 0/1 share.
   6.285 -                return Share(self, field, (share/root + 1) / 2)
   6.286 -
   6.287 -        self.schedule_callback(result, finish, share, binary)
   6.288 -        return result
   6.289 -
   6.290 -    @increment_pc
   6.291 -    def prss_share_zero(self, field):
   6.292 -        """Generate shares of the zero element from the field given.
   6.293 -
   6.294 -        Communication cost: none.
   6.295 -        """
   6.296 -        # Key used for PRSS.
   6.297 -        prss_key = tuple(self.program_counter)
   6.298 -        prfs = self.players[self.id].prfs(field.modulus)
   6.299 -        zero_share = prss_zero(self.num_players, self.threshold, self.id,
   6.300 -                               field, prfs, prss_key)
   6.301 -        return Share(self, field, zero_share)
   6.302 -
   6.303 -    @increment_pc
   6.304 -    def prss_double_share(self, field):
   6.305 -        """Make a double-sharing using PRSS.
   6.306 -
   6.307 -        The pair of shares will have degree t and 2t where t is the
   6.308 -        default threshold for the runtime.
   6.309 -        """
   6.310 -        r_t = self.prss_share_random(field)
   6.311 -        z_2t = self.prss_share_zero(field)
   6.312 -        return (r_t, r_t + z_2t)
   6.313 -
   6.314 -    @increment_pc
   6.315 -    def prss_share_bit_double(self, field):
   6.316 -        """Share a random bit over *field* and GF256.
   6.317 -
   6.318 -        The protocol is described in "Efficient Conversion of
   6.319 -        Secret-shared Values Between Different Fields" by Ivan Damgård
   6.320 -        and Rune Thorbek available as `Cryptology ePrint Archive,
   6.321 -        Report 2008/221 <http://eprint.iacr.org/2008/221>`__.
   6.322 -        """
   6.323 -        n = self.num_players
   6.324 -        k = self.options.security_parameter
   6.325 -        prfs = self.players[self.id].prfs(2**k)
   6.326 -        prss_key = tuple(self.program_counter)
   6.327 -
   6.328 -        b_p = self.prss_share_random(field, binary=True)
   6.329 -        r_p, r_lsb = prss_lsb(n, self.id, field, prfs, prss_key)
   6.330 -
   6.331 -        b = self.open(b_p + r_p)
   6.332 -        # Extract least significant bit and change field to GF256.
   6.333 -        b.addCallback(lambda i: GF256(i.value & 1))
   6.334 -        b.field = GF256
   6.335 -
   6.336 -        # Use r_lsb to flip b as needed.
   6.337 -        return (b_p, b ^ r_lsb)
   6.338 -
   6.339 -    @increment_pc
   6.340 -    def prss_shamir_share_bit_double(self, field):
   6.341 -        """Shamir share a random bit over *field* and GF256."""
   6.342 -        n = self.num_players
   6.343 -        k = self.options.security_parameter
   6.344 -        prfs = self.players[self.id].prfs(2**k)
   6.345 -        prss_key = tuple(self.program_counter)
   6.346 -        inputters = range(1, self.num_players + 1)
   6.347 -
   6.348 -        ri = rand.randint(0, 2**k - 1)
   6.349 -        ri_p = self.shamir_share(inputters, field, ri)
   6.350 -        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
   6.351 -
   6.352 -        r_p = reduce(self.add, ri_p)
   6.353 -        r_lsb = reduce(self.add, ri_lsb)
   6.354 -
   6.355 -        b_p = self.prss_share_random(field, binary=True)
   6.356 -        b = self.open(b_p + r_p)
   6.357 -        # Extract least significant bit and change field to GF256.
   6.358 -        b.addCallback(lambda i: GF256(i.value & 1))
   6.359 -        b.field = GF256
   6.360 -
   6.361 -        # Use r_lsb to flip b as needed.
   6.362 -        return (b_p, b ^ r_lsb)
   6.363 -
   6.364 -    @increment_pc
   6.365 -    def shamir_share(self, inputters, field, number=None, threshold=None):
   6.366 -        """Secret share *number* over *field* using Shamir's method.
   6.367 -
   6.368 -        The number is shared using polynomial of degree *threshold*
   6.369 -        (defaults to :attr:`threshold`). Returns a list of shares
   6.370 -        unless there is only one inputter in which case the
   6.371 -        share is returned directly.
   6.372 -
   6.373 -        Communication cost: n elements transmitted.
   6.374 -        """
   6.375 -        assert number is None or self.id in inputters
   6.376 -        if threshold is None:
   6.377 -            threshold = self.threshold
   6.378 -
   6.379 -        results = []
   6.380 -        for peer_id in inputters:
   6.381 -            if peer_id == self.id:
   6.382 -                pc = tuple(self.program_counter)
   6.383 -                shares = shamir.share(field(number), threshold,
   6.384 -                                      self.num_players)
   6.385 -                for other_id, share in shares:
   6.386 -                    if other_id.value == self.id:
   6.387 -                        results.append(Share(self, share.field, share))
   6.388 -                    else:
   6.389 -                        self.protocols[other_id.value].sendShare(pc, share)
   6.390 -            else:
   6.391 -                results.append(self._expect_share(peer_id, field))
   6.392 -
   6.393 -        # Unpack a singleton list.
   6.394 -        if len(results) == 1:
   6.395 -            return results[0]
   6.396 -        else:
   6.397 -            return results
   6.398 -
   6.399 -
   6.400 -def make_runtime_class(runtime_class=Runtime, mixins=None):
   6.401 -    """Creates a new runtime class with *runtime_class* as a base
   6.402 -    class mixing in the *mixins*.
   6.403 -    """
   6.404 +    if runtime_class is None:
   6.405 +        # The import is put here because of circular depencencies
   6.406 +        # between viff.runtime and viff.passive.
   6.407 +        from viff.passive import PassiveRuntime
   6.408 +        runtime_class = PassiveRuntime
   6.409      if mixins is None:
   6.410          return runtime_class
   6.411      else:
   6.412 @@ -1073,7 +691,7 @@
   6.413          bases = (runtime_class,) + tuple(mixins) + (object,)
   6.414          return type("ExtendedRuntime", bases, {})
   6.415  
   6.416 -def create_runtime(id, players, threshold, options=None, runtime_class=Runtime):
   6.417 +def create_runtime(id, players, threshold, options=None, runtime_class=None):
   6.418      """Create a :class:`Runtime` and connect to the other players.
   6.419  
   6.420      This function should be used in normal programs instead of
   6.421 @@ -1104,6 +722,12 @@
   6.422      Please see the example applications for more examples.
   6.423  
   6.424      """
   6.425 +    if runtime_class is None:
   6.426 +        # The import is put here because of circular depencencies
   6.427 +        # between viff.runtime and viff.passive.
   6.428 +        from viff.passive import PassiveRuntime
   6.429 +        runtime_class = PassiveRuntime
   6.430 +
   6.431      if options and options.profile:
   6.432          # To collect profiling information we monkey patch reactor.run
   6.433          # to do the collecting. It would be nicer to simply start the
     7.1 --- a/viff/test/test_runtime_equal.py	Mon Oct 27 09:38:46 2008 +0100
     7.2 +++ b/viff/test/test_runtime_equal.py	Wed Oct 29 15:54:15 2008 +0100
     7.3 @@ -22,13 +22,13 @@
     7.4  
     7.5  from viff.equality import ProbabilisticEqualityMixin
     7.6  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
     7.7 -from viff.runtime import Runtime
     7.8 +from viff.passive import PassiveRuntime
     7.9  
    7.10  #: Declare doctests for Trial.
    7.11  __doctests__ = ['viff.equality']
    7.12  
    7.13  
    7.14 -class EqualRuntime(Runtime, ProbabilisticEqualityMixin):
    7.15 +class EqualRuntime(PassiveRuntime, ProbabilisticEqualityMixin):
    7.16      """A runtime with the equality mixin."""
    7.17      pass
    7.18  
     8.1 --- a/viff/test/util.py	Mon Oct 27 09:38:46 2008 +0100
     8.2 +++ b/viff/test/util.py	Wed Oct 29 15:54:15 2008 +0100
     8.3 @@ -20,7 +20,8 @@
     8.4  from twisted.internet.defer import Deferred, gatherResults, maybeDeferred
     8.5  from twisted.trial.unittest import TestCase
     8.6  
     8.7 -from viff.runtime import Runtime, Share, ShareExchanger, ShareExchangerFactory
     8.8 +from viff.passive import PassiveRuntime
     8.9 +from viff.runtime import Share, ShareExchanger, ShareExchangerFactory
    8.10  from viff.field import GF
    8.11  from viff.config import generate_configs, load_config
    8.12  from viff.util import rand
    8.13 @@ -91,7 +92,7 @@
    8.14      #: Shamir sharing threshold.
    8.15      threshold = 1
    8.16      #: Default Runtime class to instantiate.
    8.17 -    runtime_class = Runtime
    8.18 +    runtime_class = PassiveRuntime
    8.19  
    8.20      #: A dictionary mapping player ids to pseudorandom generators.
    8.21      #: