viff

changeset 584:c355c6ffdb0a

Move comparison protocols to their own file.
author Martin Geisler <mg@daimi.au.dk>
date Wed, 19 Mar 2008 22:25:11 +0100
parents 0fa8b538aca8
children 98f8862f2c44
files apps/benchmark.py apps/compare.py apps/int-bit-conversion.py apps/millionaires.py apps/online-comparison-benchmark.py viff/comparison.py viff/runtime.py viff/test/test_runtime.py viff/test/test_runtime_comp.py
diffstat 9 files changed, 355 insertions(+), 324 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Wed Mar 19 21:58:23 2008 +0100
     1.2 +++ b/apps/benchmark.py	Wed Mar 19 22:25:11 2008 +0100
     1.3 @@ -62,8 +62,8 @@
     1.4  from twisted.internet import reactor
     1.5  
     1.6  from viff.field import GF
     1.7 -from viff.runtime import Runtime, Toft05Runtime, Toft07Runtime, \
     1.8 -     create_runtime, gather_shares
     1.9 +from viff.runtime import Runtime, create_runtime, gather_shares
    1.10 +from viff.comparison import Toft05Runtime, Toft07Runtime
    1.11  from viff.config import load_config
    1.12  from viff.util import find_prime
    1.13  
     2.1 --- a/apps/compare.py	Wed Mar 19 21:58:23 2008 +0100
     2.2 +++ b/apps/compare.py	Wed Mar 19 22:25:11 2008 +0100
     2.3 @@ -26,7 +26,8 @@
     2.4  from twisted.internet.defer import gatherResults
     2.5  
     2.6  from viff.field import GF, GF256
     2.7 -from viff.runtime import create_runtime, Toft05Runtime
     2.8 +from viff.runtime import create_runtime
     2.9 +from viff.comparison import Toft05Runtime
    2.10  from viff.config import load_config
    2.11  from viff.util import dprint
    2.12  
     3.1 --- a/apps/int-bit-conversion.py	Wed Mar 19 21:58:23 2008 +0100
     3.2 +++ b/apps/int-bit-conversion.py	Wed Mar 19 22:25:11 2008 +0100
     3.3 @@ -24,7 +24,8 @@
     3.4  from twisted.internet import reactor
     3.5  
     3.6  from viff.field import GF, GF256
     3.7 -from viff.runtime import create_runtime, Toft05Runtime
     3.8 +from viff.runtime import create_runtime
     3.9 +from viff.comparison import Toft05Runtime
    3.10  from viff.config import load_config
    3.11  
    3.12  id, players = load_config(sys.argv[1])
     4.1 --- a/apps/millionaires.py	Wed Mar 19 21:58:23 2008 +0100
     4.2 +++ b/apps/millionaires.py	Wed Mar 19 22:25:11 2008 +0100
     4.3 @@ -37,7 +37,8 @@
     4.4  from twisted.internet import reactor
     4.5  
     4.6  from viff.field import GF
     4.7 -from viff.runtime import Runtime, Toft05Runtime, create_runtime, gather_shares
     4.8 +from viff.runtime import Runtime, create_runtime, gather_shares
     4.9 +from viff.comparison import Toft05Runtime
    4.10  from viff.config import load_config
    4.11  from viff.util import rand, find_prime
    4.12  
     5.1 --- a/apps/online-comparison-benchmark.py	Wed Mar 19 21:58:23 2008 +0100
     5.2 +++ b/apps/online-comparison-benchmark.py	Wed Mar 19 22:25:11 2008 +0100
     5.3 @@ -30,7 +30,8 @@
     5.4  #defer.setDebugging(True)
     5.5  
     5.6  from viff.field import GF
     5.7 -from viff.runtime import Runtime, Toft07Runtime, create_runtime
     5.8 +from viff.runtime import Runtime, create_runtime
     5.9 +from viff.comparison import Toft07Runtime
    5.10  from viff.config import load_config
    5.11  from viff.util import rand, find_prime
    5.12  
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/viff/comparison.py	Wed Mar 19 22:25:11 2008 +0100
     6.3 @@ -0,0 +1,342 @@
     6.4 +# Copyright 2008 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 General Public License as published by
    6.10 +# the Free Software Foundation; either version 2 of the License, or
    6.11 +# (at your option) any later version.
    6.12 +#
    6.13 +# VIFF is distributed in the hope that it will be useful, but
    6.14 +# WITHOUT ANY WARRANTY; without even the implied warranty of
    6.15 +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    6.16 +# General Public License for more details.
    6.17 +#
    6.18 +# You should have received a copy of the GNU General Public License
    6.19 +# along with VIFF in the file COPYING; if not, write to the Free
    6.20 +# Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
    6.21 +# 02110-1301 USA
    6.22 +
    6.23 +"""Comparison protocols.
    6.24 +
    6.25 +The mixin classes defined here provide a C{greater_than_equal} method
    6.26 +to the L{Runtime} they are mixed with.
    6.27 +
    6.28 +"""
    6.29 +
    6.30 +from viff.util import rand
    6.31 +from viff.runtime import Runtime, Share, gather_shares, increment_pc
    6.32 +from viff.field import GF256, FieldElement
    6.33 +
    6.34 +class ComparisonToft05Mixin:
    6.35 +    """Comparison by Tomas Toft, 2005."""
    6.36 +
    6.37 +    @increment_pc
    6.38 +    def convert_bit_share(self, share, dst_field):
    6.39 +        """Convert a 0/1 share into dst_field."""
    6.40 +        bit = rand.randint(0, 1)
    6.41 +        dst_shares = self.prss_share(self.players, dst_field, bit)
    6.42 +        src_shares = self.prss_share(self.players, share.field, bit)
    6.43 +
    6.44 +        # TODO: Using a parallel reduce below seems to be slower than
    6.45 +        # using the built-in reduce.
    6.46 +
    6.47 +        # We open tmp and convert the value into a field element from
    6.48 +        # the dst_field.
    6.49 +        tmp = self.open(reduce(self.xor, src_shares, share))
    6.50 +        tmp.addCallback(lambda i: dst_field(i.value))
    6.51 +        # Must update field on Share when we change the field of the
    6.52 +        # the value within
    6.53 +        tmp.field = dst_field
    6.54 +
    6.55 +        return reduce(self.xor, dst_shares, tmp)
    6.56 +
    6.57 +    @increment_pc
    6.58 +    def greater_than_equal(self, share_a, share_b):
    6.59 +        """Compute share_a >= share_b.
    6.60 +
    6.61 +        Both arguments must be from the field given. The result is a
    6.62 +        GF256 share.
    6.63 +        """
    6.64 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
    6.65 +        if not isinstance(share_a, Share):
    6.66 +            share_a = Share(self, field, share_a)
    6.67 +        if not isinstance(share_b, Share):
    6.68 +            share_b = Share(self, field, share_b)
    6.69 +
    6.70 +        l = self.options.bit_length
    6.71 +        m = l + self.options.security_parameter
    6.72 +        t = m + 1
    6.73 +
    6.74 +        # Preprocessing begin
    6.75 +
    6.76 +        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
    6.77 +        assert self.num_players + 2 < 2**l
    6.78 +
    6.79 +        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
    6.80 +        # We must use int_bits without adding callbacks to the bits --
    6.81 +        # having int_b wait on them ensures this.
    6.82 +
    6.83 +        def bits_to_int(bits):
    6.84 +            """Converts a list of bits to an integer."""
    6.85 +            return sum([2**i * b for i, b in enumerate(bits)])
    6.86 +
    6.87 +        int_b = gather_shares(int_bits)
    6.88 +        int_b.addCallback(bits_to_int)
    6.89 +
    6.90 +        # TODO: this changes int_bits! It should be okay since
    6.91 +        # int_bits is not used any further, but still...
    6.92 +        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
    6.93 +        # Preprocessing done
    6.94 +
    6.95 +        a = share_a - share_b + 2**l
    6.96 +        T = self.open(2**t - int_b + a)
    6.97 +
    6.98 +        result = gather_shares([T] + bit_bits)
    6.99 +        self.callback(result, self._finish_greater_than_equal, l)
   6.100 +        return result
   6.101 +
   6.102 +    @increment_pc
   6.103 +    def _finish_greater_than_equal(self, results, l):
   6.104 +        """Finish the calculation."""
   6.105 +        T = results[0]
   6.106 +        bit_bits = results[1:]
   6.107 +
   6.108 +        vec = [(GF256(0), GF256(0))]
   6.109 +
   6.110 +        # Calculate the vector, using only the first l bits
   6.111 +        for i, bi in enumerate(bit_bits[:l]):
   6.112 +            Ti = GF256(T.bit(i))
   6.113 +            ci = Share(self, GF256, bi ^ Ti)
   6.114 +            vec.append((ci, Ti))
   6.115 +
   6.116 +        # Reduce using the diamond operator. We want to do as much
   6.117 +        # as possible in parallel while being careful not to
   6.118 +        # switch the order of elements since the diamond operator
   6.119 +        # is non-commutative.
   6.120 +        while len(vec) > 1:
   6.121 +            tmp = []
   6.122 +            while len(vec) > 1:
   6.123 +                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
   6.124 +            if len(vec) == 1:
   6.125 +                tmp.append(vec[0])
   6.126 +            vec = tmp
   6.127 +
   6.128 +        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
   6.129 +
   6.130 +    @increment_pc
   6.131 +    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
   6.132 +        """The "diamond-operator".
   6.133 +
   6.134 +        Defined by
   6.135 +
   6.136 +        (x, X) `diamond` (0, Y) = (0, Y)
   6.137 +        (x, X) `diamond` (1, Y) = (x, X)
   6.138 +        """
   6.139 +        top = top_a * top_b
   6.140 +        bot = top_b * (bot_a ^ bot_b) ^ bot_b
   6.141 +        return (top, bot)
   6.142 +
   6.143 +class Toft05Runtime(ComparisonToft05Mixin, Runtime):
   6.144 +    """Default mix of L{ComparisonToft05Mixin} and L{Runtime}."""
   6.145 +    pass
   6.146 +
   6.147 +
   6.148 +class ComparisonToft07Mixin:
   6.149 +
   6.150 +    """Efficient comparison by Tomas Toft 2007.
   6.151 +
   6.152 +    This mixin provides a C{greater_than} method which can compare Zp
   6.153 +    field elements and gives a secret result shared over Zp.
   6.154 +    """
   6.155 +
   6.156 +    @increment_pc
   6.157 +    def convert_bit_share(self, share, dst_field):
   6.158 +        """Convert a 0/1 share into dst_field."""
   6.159 +
   6.160 +        def log(x):
   6.161 +            # TODO: Don't do log like this...
   6.162 +            result = 0
   6.163 +            while x > 1:
   6.164 +                result += 1
   6.165 +                x //= 2
   6.166 +            return result+1 # Error for powers of two...
   6.167 +
   6.168 +        l = self.options.security_parameter + log(dst_field.modulus)
   6.169 +        # TODO assert field sizes are OK...
   6.170 +
   6.171 +        this_mask = rand.randint(0, (2**l) -1)
   6.172 +
   6.173 +        # Share large random values in the big field and reduced ones
   6.174 +        # in the small...
   6.175 +        src_shares = self.prss_share(self.players, share.field, this_mask)
   6.176 +        dst_shares = self.prss_share(self.players, dst_field, this_mask)
   6.177 +
   6.178 +        tmp = reduce(self.add, src_shares, share)
   6.179 +
   6.180 +        # We open tmp and convert the value into a field element from
   6.181 +        # the dst_field.
   6.182 +        tmp = self.open(tmp)
   6.183 +
   6.184 +        tmp.addCallback(lambda i: dst_field(i.value))
   6.185 +        # Must update field on Share when we change the field of the
   6.186 +        # the value within
   6.187 +        tmp.field = dst_field
   6.188 +
   6.189 +        full_mask = reduce(self.add, dst_shares)
   6.190 +        return tmp - full_mask
   6.191 +    
   6.192 +    @increment_pc
   6.193 +    def greater_than_equal_preproc(self, field, smallField=None):
   6.194 +        """Preprocessing for greater_than_equal."""
   6.195 +        if smallField is None:
   6.196 +            smallField = field
   6.197 +
   6.198 +        # Need an extra bit to avoid troubles with equal inputs
   6.199 +        l = self.options.bit_length + 1
   6.200 +        k = self.options.security_parameter
   6.201 +
   6.202 +        # TODO: verify asserts are correct...
   6.203 +        assert field.modulus > 2**(l+2) + 2**(l+k), "Field too small"
   6.204 +        assert smallField.modulus > 3 + 3*l, "smallField too small"
   6.205 +
   6.206 +        # TODO: do not generate all bits, only $l$ of them
   6.207 +        # could perhaps do PRSS over smaller subset?
   6.208 +        r_bitsField = [self.prss_share_random(field, True) for _ in range(l+k)]
   6.209 +
   6.210 +        # TODO: compute r_full from r_modl and top bits, not from scratch
   6.211 +        r_full = 0
   6.212 +        for i, b in enumerate(r_bitsField):
   6.213 +            r_full = r_full + b * 2**i
   6.214 +
   6.215 +        r_bitsField = r_bitsField[:l]
   6.216 +        r_modl = 0
   6.217 +        for i, b in enumerate(r_bitsField):
   6.218 +            r_modl = r_modl + b * 2**i
   6.219 +
   6.220 +        # Transfer bits to smallField
   6.221 +        if field is smallField:
   6.222 +            r_bits = r_bitsField
   6.223 +        else:
   6.224 +            r_bits = [self.convert_bit_share(bit, smallField) \
   6.225 +                      for bit in r_bitsField]
   6.226 +
   6.227 +        s_bit = self.prss_share_random(field, binary=True)
   6.228 +
   6.229 +        s_bitSmallField = self.convert_bit_share(s_bit, smallField)
   6.230 +        s_sign = 1 + s_bitSmallField * -2
   6.231 +
   6.232 +        # m: uniformly random -- should be non-zero, however, this
   6.233 +        # happens with negligible probability
   6.234 +        # TODO: small field, no longer negligible probability of zero -- update
   6.235 +        mask = self.prss_share_random(smallField, False)
   6.236 +        #mask_2 = self.prss_share_random(smallField, False)
   6.237 +        #mask_OK = self.open(mask * mask_2)
   6.238 +        #dprint("Mask_OK: %s", mask_OK)
   6.239 +
   6.240 +        return field, smallField, s_bit, s_sign, mask, r_full, r_modl, r_bits
   6.241 +
   6.242 +        ##################################################
   6.243 +        # Preprocessing done
   6.244 +        ##################################################
   6.245 +
   6.246 +    @increment_pc
   6.247 +    def greater_than_equal_online(self, share_a, share_b, preproc, field):
   6.248 +        """Compute share_a >= share_b.
   6.249 +        Result is shared.
   6.250 +        """
   6.251 +        # increment l as a, b are increased
   6.252 +        l = self.options.bit_length + 1
   6.253 +        # a = 2a+1; b= 2b // ensures inputs not equal
   6.254 +        share_a = 2 * share_a + 1
   6.255 +        share_b = 2 * share_b
   6.256 +
   6.257 +        ##################################################
   6.258 +        # Unpack preprocessing
   6.259 +        ##################################################
   6.260 +        #TODO: assert fields are the same...
   6.261 +        field, smallField, s_bit, s_sign, mask, r_full, r_modl, r_bits = preproc
   6.262 +        assert l == len(r_bits), "preprocessing does not match " \
   6.263 +            "online parameters"
   6.264 +
   6.265 +        ##################################################
   6.266 +        # Begin online computation
   6.267 +        ##################################################
   6.268 +        # c = 2**l + a - b + r
   6.269 +        z = share_a - share_b + 2**l
   6.270 +        c = self.open(r_full + z)
   6.271 +
   6.272 +        self.callback(c, self._finish_greater_than_equal,
   6.273 +                      field, smallField, s_bit, s_sign, mask,
   6.274 +                      r_modl, r_bits, z)
   6.275 +        return c
   6.276 +
   6.277 +    @increment_pc
   6.278 +    def _finish_greater_than_equal(self, c, field, smallField, s_bit, s_sign,
   6.279 +                               mask, r_modl, r_bits, z):
   6.280 +        """Finish the calculation."""
   6.281 +        # increment l as a, b are increased
   6.282 +        l = self.options.bit_length + 1
   6.283 +        c_bits = [smallField(c.bit(i)) for i in range(l)]
   6.284 +
   6.285 +        sumXORs = [0]*l
   6.286 +        # sumXORs[i] = sumXORs[i+1] + r_bits[i+1] + c_(i+1)
   6.287 +        #                           - 2*r_bits[i+1]*c_(i+1)
   6.288 +        for i in range(l-2, -1, -1):
   6.289 +            # sumXORs[i] = \sum_{j=i+1}^{l-1} r_j\oplus c_j
   6.290 +            sumXORs[i] = sumXORs[i+1] + (r_bits[i+1] ^ c_bits[i+1])
   6.291 +        E_tilde = []
   6.292 +        for i in range(len(r_bits)):
   6.293 +            ## s + rBit[i] - cBit[i] + 3 * sumXors[i];
   6.294 +            e_i = s_sign + (r_bits[i] - c_bits[i])
   6.295 +            e_i = e_i + 3 * sumXORs[i]
   6.296 +            E_tilde.append(e_i)
   6.297 +        E_tilde.append(mask) # Hack: will mult e_i and mask...
   6.298 +
   6.299 +        while len(E_tilde) > 1:
   6.300 +            # TODO: pop() ought to be preferred? No: it takes the
   6.301 +            # just appended and thus works linearly... try with
   6.302 +            # two lists instead, pop(0) is quadratic if it moves
   6.303 +            # elements.
   6.304 +            E_tilde.append(E_tilde.pop(0) * E_tilde.pop(0))
   6.305 +
   6.306 +        E_tilde[0] = self.open(E_tilde[0])
   6.307 +        E_tilde[0].addCallback(lambda bit: field(bit.value != 0))
   6.308 +        non_zero = E_tilde[0]
   6.309 +
   6.310 +        # UF == underflow
   6.311 +        UF = non_zero ^ s_bit
   6.312 +
   6.313 +        # conclude the computation -- compute final bit and map to 0/1
   6.314 +        # return  2^(-l) * (z - (c%2**l - r%2**l + UF*2**l))
   6.315 +        #
   6.316 +        c_mod2l = c.value % 2**l
   6.317 +        result = (c_mod2l - r_modl) + UF * 2**l
   6.318 +        return (z - result) * ~field(2**l)
   6.319 +    # END _finish_greater_than
   6.320 +
   6.321 +    @increment_pc
   6.322 +    def greater_than_equal(self, share_a, share_b):
   6.323 +        """Compute share_a >= share_b.
   6.324 +
   6.325 +        Both arguments must be of type field. The result is a
   6.326 +        field share.
   6.327 +        """
   6.328 +        # TODO: Make all input-taking methods do coercion like this.
   6.329 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   6.330 +        if not isinstance(share_a, Share):
   6.331 +            if not isinstance(share_a, FieldElement):
   6.332 +                share_a = field(share_a)
   6.333 +            share_a = Share(self, field, share_a)
   6.334 +        if not isinstance(share_b, Share):
   6.335 +            if not isinstance(share_b, FieldElement):
   6.336 +                share_b = field(share_b)
   6.337 +            share_b = Share(self, field, share_b)
   6.338 +
   6.339 +        preproc = self.greater_than_equal_preproc(field)
   6.340 +        return self.greater_than_equal_online(share_a, share_b, preproc,
   6.341 +                                              field)
   6.342 +
   6.343 +class Toft07Runtime(ComparisonToft07Mixin, Runtime):
   6.344 +    """Default mix of L{ComparisonToft07Mixin} and L{Runtime}."""
   6.345 +    pass
     7.1 --- a/viff/runtime.py	Wed Mar 19 21:58:23 2008 +0100
     7.2 +++ b/viff/runtime.py	Wed Mar 19 22:25:11 2008 +0100
     7.3 @@ -1054,322 +1054,6 @@
     7.4          return result
     7.5  
     7.6  
     7.7 -class ComparisonToft05Mixin:
     7.8 -    """Comparison by Tomas Toft, 2005."""
     7.9 -
    7.10 -    @increment_pc
    7.11 -    def convert_bit_share(self, share, dst_field):
    7.12 -        """Convert a 0/1 share into dst_field."""
    7.13 -        bit = rand.randint(0, 1)
    7.14 -        dst_shares = self.prss_share(self.players, dst_field, bit)
    7.15 -        src_shares = self.prss_share(self.players, share.field, bit)
    7.16 -
    7.17 -        # TODO: Using a parallel reduce below seems to be slower than
    7.18 -        # using the built-in reduce.
    7.19 -
    7.20 -        # We open tmp and convert the value into a field element from
    7.21 -        # the dst_field.
    7.22 -        tmp = self.open(reduce(self.xor, src_shares, share))
    7.23 -        tmp.addCallback(lambda i: dst_field(i.value))
    7.24 -        # Must update field on Share when we change the field of the
    7.25 -        # the value within
    7.26 -        tmp.field = dst_field
    7.27 -
    7.28 -        return reduce(self.xor, dst_shares, tmp)
    7.29 -
    7.30 -    @increment_pc
    7.31 -    def greater_than_equal(self, share_a, share_b):
    7.32 -        """Compute share_a >= share_b.
    7.33 -
    7.34 -        Both arguments must be from the field given. The result is a
    7.35 -        GF256 share.
    7.36 -        """
    7.37 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
    7.38 -        if not isinstance(share_a, Share):
    7.39 -            share_a = Share(self, field, share_a)
    7.40 -        if not isinstance(share_b, Share):
    7.41 -            share_b = Share(self, field, share_b)
    7.42 -
    7.43 -        l = self.options.bit_length
    7.44 -        m = l + self.options.security_parameter
    7.45 -        t = m + 1
    7.46 -
    7.47 -        # Preprocessing begin
    7.48 -
    7.49 -        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
    7.50 -        assert self.num_players + 2 < 2**l
    7.51 -
    7.52 -        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
    7.53 -        # We must use int_bits without adding callbacks to the bits --
    7.54 -        # having int_b wait on them ensures this.
    7.55 -
    7.56 -        def bits_to_int(bits):
    7.57 -            """Converts a list of bits to an integer."""
    7.58 -            return sum([2**i * b for i, b in enumerate(bits)])
    7.59 -
    7.60 -        int_b = gather_shares(int_bits)
    7.61 -        int_b.addCallback(bits_to_int)
    7.62 -
    7.63 -        # TODO: this changes int_bits! It should be okay since
    7.64 -        # int_bits is not used any further, but still...
    7.65 -        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
    7.66 -        # Preprocessing done
    7.67 -
    7.68 -        a = share_a - share_b + 2**l
    7.69 -        T = self.open(2**t - int_b + a)
    7.70 -
    7.71 -        result = gather_shares([T] + bit_bits)
    7.72 -        self.callback(result, self._finish_greater_than_equal, l)
    7.73 -        return result
    7.74 -
    7.75 -    @increment_pc
    7.76 -    def _finish_greater_than_equal(self, results, l):
    7.77 -        """Finish the calculation."""
    7.78 -        T = results[0]
    7.79 -        bit_bits = results[1:]
    7.80 -
    7.81 -        vec = [(GF256(0), GF256(0))]
    7.82 -
    7.83 -        # Calculate the vector, using only the first l bits
    7.84 -        for i, bi in enumerate(bit_bits[:l]):
    7.85 -            Ti = GF256(T.bit(i))
    7.86 -            ci = Share(self, GF256, bi ^ Ti)
    7.87 -            vec.append((ci, Ti))
    7.88 -
    7.89 -        # Reduce using the diamond operator. We want to do as much
    7.90 -        # as possible in parallel while being careful not to
    7.91 -        # switch the order of elements since the diamond operator
    7.92 -        # is non-commutative.
    7.93 -        while len(vec) > 1:
    7.94 -            tmp = []
    7.95 -            while len(vec) > 1:
    7.96 -                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
    7.97 -            if len(vec) == 1:
    7.98 -                tmp.append(vec[0])
    7.99 -            vec = tmp
   7.100 -
   7.101 -        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
   7.102 -
   7.103 -    @increment_pc
   7.104 -    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
   7.105 -        """The "diamond-operator".
   7.106 -
   7.107 -        Defined by
   7.108 -
   7.109 -        (x, X) `diamond` (0, Y) = (0, Y)
   7.110 -        (x, X) `diamond` (1, Y) = (x, X)
   7.111 -        """
   7.112 -        top = top_a * top_b
   7.113 -        bot = top_b * (bot_a ^ bot_b) ^ bot_b
   7.114 -        return (top, bot)
   7.115 -
   7.116 -
   7.117 -class Toft05Runtime(ComparisonToft05Mixin, Runtime):
   7.118 -    """Default mix of L{ComparisonToft05Mixin} and L{Runtime}."""
   7.119 -    pass
   7.120 -
   7.121 -
   7.122 -class ComparisonToft07Mixin:
   7.123 -
   7.124 -    """Efficient comparison by Tomas Toft 2007.
   7.125 -
   7.126 -    This mixin provides a C{greater_than} method which can compare Zp
   7.127 -    field elements and gives a secret result shared over Zp.
   7.128 -    """
   7.129 -
   7.130 -    @increment_pc
   7.131 -    def convert_bit_share(self, share, dst_field):
   7.132 -        """Convert a 0/1 share into dst_field."""
   7.133 -
   7.134 -        def log(x):
   7.135 -            # TODO: Don't do log like this...
   7.136 -            result = 0
   7.137 -            while x > 1:
   7.138 -                result += 1
   7.139 -                x //= 2
   7.140 -            return result+1 # Error for powers of two...
   7.141 -
   7.142 -        l = self.options.security_parameter + log(dst_field.modulus)
   7.143 -        # TODO assert field sizes are OK...
   7.144 -
   7.145 -        this_mask = rand.randint(0, (2**l) -1)
   7.146 -
   7.147 -        # Share large random values in the big field and reduced ones
   7.148 -        # in the small...
   7.149 -        src_shares = self.prss_share(self.players, share.field, this_mask)
   7.150 -        dst_shares = self.prss_share(self.players, dst_field, this_mask)
   7.151 -
   7.152 -        tmp = reduce(self.add, src_shares, share)
   7.153 -
   7.154 -        # We open tmp and convert the value into a field element from
   7.155 -        # the dst_field.
   7.156 -        tmp = self.open(tmp)
   7.157 -
   7.158 -        tmp.addCallback(lambda i: dst_field(i.value))
   7.159 -        # Must update field on Share when we change the field of the
   7.160 -        # the value within
   7.161 -        tmp.field = dst_field
   7.162 -
   7.163 -        full_mask = reduce(self.add, dst_shares)
   7.164 -        return tmp - full_mask
   7.165 -    
   7.166 -    @increment_pc
   7.167 -    def greater_than_equal_preproc(self, field, smallField=None):
   7.168 -        """Preprocessing for greater_than_equal."""
   7.169 -        if smallField is None:
   7.170 -            smallField = field
   7.171 -
   7.172 -        # Need an extra bit to avoid troubles with equal inputs
   7.173 -        l = self.options.bit_length + 1
   7.174 -        k = self.options.security_parameter
   7.175 -
   7.176 -        # TODO: verify asserts are correct...
   7.177 -        assert field.modulus > 2**(l+2) + 2**(l+k), "Field too small"
   7.178 -        assert smallField.modulus > 3 + 3*l, "smallField too small"
   7.179 -
   7.180 -        # TODO: do not generate all bits, only $l$ of them
   7.181 -        # could perhaps do PRSS over smaller subset?
   7.182 -        r_bitsField = [self.prss_share_random(field, True) for _ in range(l+k)]
   7.183 -
   7.184 -        # TODO: compute r_full from r_modl and top bits, not from scratch
   7.185 -        r_full = 0
   7.186 -        for i, b in enumerate(r_bitsField):
   7.187 -            r_full = r_full + b * 2**i
   7.188 -
   7.189 -        r_bitsField = r_bitsField[:l]
   7.190 -        r_modl = 0
   7.191 -        for i, b in enumerate(r_bitsField):
   7.192 -            r_modl = r_modl + b * 2**i
   7.193 -
   7.194 -        # Transfer bits to smallField
   7.195 -        if field is smallField:
   7.196 -            r_bits = r_bitsField
   7.197 -        else:
   7.198 -            r_bits = [self.convert_bit_share(bit, smallField) \
   7.199 -                      for bit in r_bitsField]
   7.200 -
   7.201 -        s_bit = self.prss_share_random(field, binary=True)
   7.202 -
   7.203 -        s_bitSmallField = self.convert_bit_share(s_bit, smallField)
   7.204 -        s_sign = 1 + s_bitSmallField * -2
   7.205 -
   7.206 -        # m: uniformly random -- should be non-zero, however, this
   7.207 -        # happens with negligible probability
   7.208 -        # TODO: small field, no longer negligible probability of zero -- update
   7.209 -        mask = self.prss_share_random(smallField, False)
   7.210 -        #mask_2 = self.prss_share_random(smallField, False)
   7.211 -        #mask_OK = self.open(mask * mask_2)
   7.212 -        #dprint("Mask_OK: %s", mask_OK)
   7.213 -
   7.214 -        return field, smallField, s_bit, s_sign, mask, r_full, r_modl, r_bits
   7.215 -
   7.216 -        ##################################################
   7.217 -        # Preprocessing done
   7.218 -        ##################################################
   7.219 -
   7.220 -    @increment_pc
   7.221 -    def greater_than_equal_online(self, share_a, share_b, preproc, field):
   7.222 -        """Compute share_a >= share_b.
   7.223 -        Result is shared.
   7.224 -        """
   7.225 -        # increment l as a, b are increased
   7.226 -        l = self.options.bit_length + 1
   7.227 -        # a = 2a+1; b= 2b // ensures inputs not equal
   7.228 -        share_a = 2 * share_a + 1
   7.229 -        share_b = 2 * share_b
   7.230 -
   7.231 -        ##################################################
   7.232 -        # Unpack preprocessing
   7.233 -        ##################################################
   7.234 -        #TODO: assert fields are the same...
   7.235 -        field, smallField, s_bit, s_sign, mask, r_full, r_modl, r_bits = preproc
   7.236 -        assert l == len(r_bits), "preprocessing does not match " \
   7.237 -            "online parameters"
   7.238 -
   7.239 -        ##################################################
   7.240 -        # Begin online computation
   7.241 -        ##################################################
   7.242 -        # c = 2**l + a - b + r
   7.243 -        z = share_a - share_b + 2**l
   7.244 -        c = self.open(r_full + z)
   7.245 -
   7.246 -        self.callback(c, self._finish_greater_than_equal,
   7.247 -                      field, smallField, s_bit, s_sign, mask,
   7.248 -                      r_modl, r_bits, z)
   7.249 -        return c
   7.250 -
   7.251 -    @increment_pc
   7.252 -    def _finish_greater_than_equal(self, c, field, smallField, s_bit, s_sign,
   7.253 -                               mask, r_modl, r_bits, z):
   7.254 -        """Finish the calculation."""
   7.255 -        # increment l as a, b are increased
   7.256 -        l = self.options.bit_length + 1
   7.257 -        c_bits = [smallField(c.bit(i)) for i in range(l)]
   7.258 -
   7.259 -        sumXORs = [0]*l
   7.260 -        # sumXORs[i] = sumXORs[i+1] + r_bits[i+1] + c_(i+1)
   7.261 -        #                           - 2*r_bits[i+1]*c_(i+1)
   7.262 -        for i in range(l-2, -1, -1):
   7.263 -            # sumXORs[i] = \sum_{j=i+1}^{l-1} r_j\oplus c_j
   7.264 -            sumXORs[i] = sumXORs[i+1] + (r_bits[i+1] ^ c_bits[i+1])
   7.265 -        E_tilde = []
   7.266 -        for i in range(len(r_bits)):
   7.267 -            ## s + rBit[i] - cBit[i] + 3 * sumXors[i];
   7.268 -            e_i = s_sign + (r_bits[i] - c_bits[i])
   7.269 -            e_i = e_i + 3 * sumXORs[i]
   7.270 -            E_tilde.append(e_i)
   7.271 -        E_tilde.append(mask) # Hack: will mult e_i and mask...
   7.272 -
   7.273 -        while len(E_tilde) > 1:
   7.274 -            # TODO: pop() ought to be preferred? No: it takes the
   7.275 -            # just appended and thus works linearly... try with
   7.276 -            # two lists instead, pop(0) is quadratic if it moves
   7.277 -            # elements.
   7.278 -            E_tilde.append(E_tilde.pop(0) * E_tilde.pop(0))
   7.279 -
   7.280 -        E_tilde[0] = self.open(E_tilde[0])
   7.281 -        E_tilde[0].addCallback(lambda bit: field(bit.value != 0))
   7.282 -        non_zero = E_tilde[0]
   7.283 -
   7.284 -        # UF == underflow
   7.285 -        UF = non_zero ^ s_bit
   7.286 -
   7.287 -        # conclude the computation -- compute final bit and map to 0/1
   7.288 -        # return  2^(-l) * (z - (c%2**l - r%2**l + UF*2**l))
   7.289 -        #
   7.290 -        c_mod2l = c.value % 2**l
   7.291 -        result = (c_mod2l - r_modl) + UF * 2**l
   7.292 -        return (z - result) * ~field(2**l)
   7.293 -    # END _finish_greater_than
   7.294 -
   7.295 -    @increment_pc
   7.296 -    def greater_than_equal(self, share_a, share_b):
   7.297 -        """Compute share_a >= share_b.
   7.298 -
   7.299 -        Both arguments must be of type field. The result is a
   7.300 -        field share.
   7.301 -        """
   7.302 -        # TODO: Make all input-taking methods do coercion like this.
   7.303 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
   7.304 -        if not isinstance(share_a, Share):
   7.305 -            if not isinstance(share_a, FieldElement):
   7.306 -                share_a = field(share_a)
   7.307 -            share_a = Share(self, field, share_a)
   7.308 -        if not isinstance(share_b, Share):
   7.309 -            if not isinstance(share_b, FieldElement):
   7.310 -                share_b = field(share_b)
   7.311 -            share_b = Share(self, field, share_b)
   7.312 -
   7.313 -        preproc = self.greater_than_equal_preproc(field)
   7.314 -        return self.greater_than_equal_online(share_a, share_b, preproc,
   7.315 -                                              field)
   7.316 -
   7.317 -
   7.318 -class Toft07Runtime(ComparisonToft07Mixin, Runtime):
   7.319 -    """Default mix of L{ComparisonToft07Mixin} and L{Runtime}."""
   7.320 -    pass
   7.321 -
   7.322 -
   7.323  def create_runtime(id, players, threshold, options=None, runtime_class=Runtime):
   7.324      """Create a L{Runtime} and connect to the other players.
   7.325  
     8.1 --- a/viff/test/test_runtime.py	Wed Mar 19 21:58:23 2008 +0100
     8.2 +++ b/viff/test/test_runtime.py	Wed Mar 19 22:25:11 2008 +0100
     8.3 @@ -32,7 +32,8 @@
     8.4  from twisted.internet.defer import gatherResults
     8.5  
     8.6  from viff.field import GF256
     8.7 -from viff.runtime import Share, Toft05Runtime
     8.8 +from viff.runtime import Share
     8.9 +from viff.comparison import Toft05Runtime
    8.10  
    8.11  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
    8.12  
     9.1 --- a/viff/test/test_runtime_comp.py	Wed Mar 19 21:58:23 2008 +0100
     9.2 +++ b/viff/test/test_runtime_comp.py	Wed Mar 19 22:25:11 2008 +0100
     9.3 @@ -21,7 +21,7 @@
     9.4  
     9.5  import operator
     9.6  
     9.7 -from viff.runtime import Toft05Runtime, Toft07Runtime
     9.8 +from viff.comparison import Toft05Runtime, Toft07Runtime
     9.9  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
    9.10  
    9.11  class Toft05GreaterThanTest(BinaryOperatorTestCase, RuntimeTestCase):