viff

changeset 580:046931571b8a

Move greater_than_equal to ComparisonToft05Mixin.
author Martin Geisler <mg@daimi.au.dk>
date Wed, 19 Mar 2008 21:50:38 +0100
parents c21799aac54d
children 75e42c1c7c74
files apps/benchmark.py apps/compare.py apps/int-bit-conversion.py apps/millionaires.py viff/runtime.py viff/test/test_runtime.py viff/test/test_runtime_comp.py
diffstat 7 files changed, 135 insertions(+), 116 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Wed Mar 19 21:50:24 2008 +0100
     1.2 +++ b/apps/benchmark.py	Wed Mar 19 21:50:38 2008 +0100
     1.3 @@ -62,7 +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, Toft07Runtime, create_runtime, gather_shares
     1.8 +from viff.runtime import Runtime, Toft05Runtime, Toft07Runtime, \
     1.9 +     create_runtime, gather_shares
    1.10  from viff.config import load_config
    1.11  from viff.util import find_prime
    1.12  
    1.13 @@ -195,7 +196,7 @@
    1.14      runtime_class = Runtime
    1.15  elif options.operation == "comp":
    1.16      operation = operator.ge
    1.17 -    runtime_class = Runtime
    1.18 +    runtime_class = Toft05Runtime
    1.19  elif options.operation == "compII":
    1.20      operation = operator.ge
    1.21      runtime_class = Toft07Runtime
     2.1 --- a/apps/compare.py	Wed Mar 19 21:50:24 2008 +0100
     2.2 +++ b/apps/compare.py	Wed Mar 19 21:50:38 2008 +0100
     2.3 @@ -26,7 +26,7 @@
     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
     2.8 +from viff.runtime import create_runtime, Toft05Runtime
     2.9  from viff.config import load_config
    2.10  from viff.util import dprint
    2.11  
    2.12 @@ -67,7 +67,7 @@
    2.13      results = gatherResults(bits)
    2.14      results.addCallback(lambda _: rt.shutdown())
    2.15  
    2.16 -pre_runtime = create_runtime(id, players, 1)
    2.17 +pre_runtime = create_runtime(id, players, 1, runtime_class=Toft05Runtime)
    2.18  pre_runtime.addCallback(protocol)
    2.19  
    2.20  reactor.run()
     3.1 --- a/apps/int-bit-conversion.py	Wed Mar 19 21:50:24 2008 +0100
     3.2 +++ b/apps/int-bit-conversion.py	Wed Mar 19 21:50:38 2008 +0100
     3.3 @@ -24,7 +24,7 @@
     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
     3.8 +from viff.runtime import create_runtime, Toft05Runtime
     3.9  from viff.config import load_config
    3.10  
    3.11  id, players = load_config(sys.argv[1])
    3.12 @@ -62,7 +62,8 @@
    3.13  
    3.14      rt.wait_for(a_b, b_b, c_b, x_b, y_b, z_b)
    3.15  
    3.16 -pre_runtime = create_runtime(id, players, (len(players) -1)//2)
    3.17 +pre_runtime = create_runtime(id, players, (len(players) -1)//2,
    3.18 +                             runtime_class=Toft05Runtime)
    3.19  pre_runtime.addCallback(protocol)
    3.20  
    3.21  reactor.run()
     4.1 --- a/apps/millionaires.py	Wed Mar 19 21:50:24 2008 +0100
     4.2 +++ b/apps/millionaires.py	Wed Mar 19 21:50:38 2008 +0100
     4.3 @@ -37,7 +37,7 @@
     4.4  from twisted.internet import reactor
     4.5  
     4.6  from viff.field import GF
     4.7 -from viff.runtime import Runtime, create_runtime, gather_shares
     4.8 +from viff.runtime import Runtime, Toft05Runtime, create_runtime, gather_shares
     4.9  from viff.config import load_config
    4.10  from viff.util import rand, find_prime
    4.11  
    4.12 @@ -142,7 +142,7 @@
    4.13      id, players = load_config(args[0])
    4.14  
    4.15  # Create a deferred Runtime and ask it to run our protocol when ready.
    4.16 -pre_runtime = create_runtime(id, players, 1, options)
    4.17 +pre_runtime = create_runtime(id, players, 1, options, Toft05Runtime)
    4.18  pre_runtime.addCallback(Protocol)
    4.19  
    4.20  # Start the Twisted event loop.
     5.1 --- a/viff/runtime.py	Wed Mar 19 21:50:24 2008 +0100
     5.2 +++ b/viff/runtime.py	Wed Mar 19 21:50:38 2008 +0100
     5.3 @@ -854,112 +854,6 @@
     5.4              return results
     5.5  
     5.6      @increment_pc
     5.7 -    def convert_bit_share(self, share, dst_field):
     5.8 -        """Convert a 0/1 share into dst_field."""
     5.9 -        bit = rand.randint(0, 1)
    5.10 -        dst_shares = self.prss_share(self.players, dst_field, bit)
    5.11 -        src_shares = self.prss_share(self.players, share.field, bit)
    5.12 -
    5.13 -        # TODO: Using a parallel reduce below seems to be slower than
    5.14 -        # using the built-in reduce.
    5.15 -
    5.16 -        # We open tmp and convert the value into a field element from
    5.17 -        # the dst_field.
    5.18 -        tmp = self.open(reduce(self.xor, src_shares, share))
    5.19 -        tmp.addCallback(lambda i: dst_field(i.value))
    5.20 -        # Must update field on Share when we change the field of the
    5.21 -        # the value within
    5.22 -        tmp.field = dst_field
    5.23 -
    5.24 -        return reduce(self.xor, dst_shares, tmp)
    5.25 -
    5.26 -    @increment_pc
    5.27 -    def greater_than_equal(self, share_a, share_b):
    5.28 -        """Compute share_a >= share_b.
    5.29 -
    5.30 -        Both arguments must be from the field given. The result is a
    5.31 -        GF256 share.
    5.32 -        """
    5.33 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
    5.34 -        if not isinstance(share_a, Share):
    5.35 -            share_a = Share(self, field, share_a)
    5.36 -        if not isinstance(share_b, Share):
    5.37 -            share_b = Share(self, field, share_b)
    5.38 -
    5.39 -        l = self.options.bit_length
    5.40 -        m = l + self.options.security_parameter
    5.41 -        t = m + 1
    5.42 -
    5.43 -        # Preprocessing begin
    5.44 -
    5.45 -        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
    5.46 -        assert self.num_players + 2 < 2**l
    5.47 -
    5.48 -        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
    5.49 -        # We must use int_bits without adding callbacks to the bits --
    5.50 -        # having int_b wait on them ensures this.
    5.51 -
    5.52 -        def bits_to_int(bits):
    5.53 -            """Converts a list of bits to an integer."""
    5.54 -            return sum([2**i * b for i, b in enumerate(bits)])
    5.55 -
    5.56 -        int_b = gather_shares(int_bits)
    5.57 -        int_b.addCallback(bits_to_int)
    5.58 -
    5.59 -        # TODO: this changes int_bits! It should be okay since
    5.60 -        # int_bits is not used any further, but still...
    5.61 -        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
    5.62 -        # Preprocessing done
    5.63 -
    5.64 -        a = share_a - share_b + 2**l
    5.65 -        T = self.open(2**t - int_b + a)
    5.66 -
    5.67 -        result = gather_shares([T] + bit_bits)
    5.68 -        self.callback(result, self._finish_greater_than_equal, l)
    5.69 -        return result
    5.70 -
    5.71 -    @increment_pc
    5.72 -    def _finish_greater_than_equal(self, results, l):
    5.73 -        """Finish the calculation."""
    5.74 -        T = results[0]
    5.75 -        bit_bits = results[1:]
    5.76 -
    5.77 -        vec = [(GF256(0), GF256(0))]
    5.78 -
    5.79 -        # Calculate the vector, using only the first l bits
    5.80 -        for i, bi in enumerate(bit_bits[:l]):
    5.81 -            Ti = GF256(T.bit(i))
    5.82 -            ci = Share(self, GF256, bi ^ Ti)
    5.83 -            vec.append((ci, Ti))
    5.84 -
    5.85 -        # Reduce using the diamond operator. We want to do as much
    5.86 -        # as possible in parallel while being careful not to
    5.87 -        # switch the order of elements since the diamond operator
    5.88 -        # is non-commutative.
    5.89 -        while len(vec) > 1:
    5.90 -            tmp = []
    5.91 -            while len(vec) > 1:
    5.92 -                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
    5.93 -            if len(vec) == 1:
    5.94 -                tmp.append(vec[0])
    5.95 -            vec = tmp
    5.96 -
    5.97 -        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
    5.98 -
    5.99 -    @increment_pc
   5.100 -    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
   5.101 -        """The "diamond-operator".
   5.102 -
   5.103 -        Defined by
   5.104 -
   5.105 -        (x, X) `diamond` (0, Y) = (0, Y)
   5.106 -        (x, X) `diamond` (1, Y) = (x, X)
   5.107 -        """
   5.108 -        top = top_a * top_b
   5.109 -        bot = top_b * (bot_a ^ bot_b) ^ bot_b
   5.110 -        return (top, bot)
   5.111 -
   5.112 -    @increment_pc
   5.113      def _broadcast(self, sender, message=None):
   5.114          """Perform a Bracha broadcast.
   5.115  
   5.116 @@ -1148,6 +1042,121 @@
   5.117          return result
   5.118  
   5.119  
   5.120 +class ComparisonToft05Mixin:
   5.121 +    """Comparison by Tomas Toft, 2005."""
   5.122 +
   5.123 +    @increment_pc
   5.124 +    def convert_bit_share(self, share, dst_field):
   5.125 +        """Convert a 0/1 share into dst_field."""
   5.126 +        bit = rand.randint(0, 1)
   5.127 +        dst_shares = self.prss_share(self.players, dst_field, bit)
   5.128 +        src_shares = self.prss_share(self.players, share.field, bit)
   5.129 +
   5.130 +        # TODO: Using a parallel reduce below seems to be slower than
   5.131 +        # using the built-in reduce.
   5.132 +
   5.133 +        # We open tmp and convert the value into a field element from
   5.134 +        # the dst_field.
   5.135 +        tmp = self.open(reduce(self.xor, src_shares, share))
   5.136 +        tmp.addCallback(lambda i: dst_field(i.value))
   5.137 +        # Must update field on Share when we change the field of the
   5.138 +        # the value within
   5.139 +        tmp.field = dst_field
   5.140 +
   5.141 +        return reduce(self.xor, dst_shares, tmp)
   5.142 +
   5.143 +    @increment_pc
   5.144 +    def greater_than_equal(self, share_a, share_b):
   5.145 +        """Compute share_a >= share_b.
   5.146 +
   5.147 +        Both arguments must be from the field given. The result is a
   5.148 +        GF256 share.
   5.149 +        """
   5.150 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.151 +        if not isinstance(share_a, Share):
   5.152 +            share_a = Share(self, field, share_a)
   5.153 +        if not isinstance(share_b, Share):
   5.154 +            share_b = Share(self, field, share_b)
   5.155 +
   5.156 +        l = self.options.bit_length
   5.157 +        m = l + self.options.security_parameter
   5.158 +        t = m + 1
   5.159 +
   5.160 +        # Preprocessing begin
   5.161 +
   5.162 +        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
   5.163 +        assert self.num_players + 2 < 2**l
   5.164 +
   5.165 +        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
   5.166 +        # We must use int_bits without adding callbacks to the bits --
   5.167 +        # having int_b wait on them ensures this.
   5.168 +
   5.169 +        def bits_to_int(bits):
   5.170 +            """Converts a list of bits to an integer."""
   5.171 +            return sum([2**i * b for i, b in enumerate(bits)])
   5.172 +
   5.173 +        int_b = gather_shares(int_bits)
   5.174 +        int_b.addCallback(bits_to_int)
   5.175 +
   5.176 +        # TODO: this changes int_bits! It should be okay since
   5.177 +        # int_bits is not used any further, but still...
   5.178 +        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
   5.179 +        # Preprocessing done
   5.180 +
   5.181 +        a = share_a - share_b + 2**l
   5.182 +        T = self.open(2**t - int_b + a)
   5.183 +
   5.184 +        result = gather_shares([T] + bit_bits)
   5.185 +        self.callback(result, self._finish_greater_than_equal, l)
   5.186 +        return result
   5.187 +
   5.188 +    @increment_pc
   5.189 +    def _finish_greater_than_equal(self, results, l):
   5.190 +        """Finish the calculation."""
   5.191 +        T = results[0]
   5.192 +        bit_bits = results[1:]
   5.193 +
   5.194 +        vec = [(GF256(0), GF256(0))]
   5.195 +
   5.196 +        # Calculate the vector, using only the first l bits
   5.197 +        for i, bi in enumerate(bit_bits[:l]):
   5.198 +            Ti = GF256(T.bit(i))
   5.199 +            ci = Share(self, GF256, bi ^ Ti)
   5.200 +            vec.append((ci, Ti))
   5.201 +
   5.202 +        # Reduce using the diamond operator. We want to do as much
   5.203 +        # as possible in parallel while being careful not to
   5.204 +        # switch the order of elements since the diamond operator
   5.205 +        # is non-commutative.
   5.206 +        while len(vec) > 1:
   5.207 +            tmp = []
   5.208 +            while len(vec) > 1:
   5.209 +                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
   5.210 +            if len(vec) == 1:
   5.211 +                tmp.append(vec[0])
   5.212 +            vec = tmp
   5.213 +
   5.214 +        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
   5.215 +
   5.216 +    @increment_pc
   5.217 +    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
   5.218 +        """The "diamond-operator".
   5.219 +
   5.220 +        Defined by
   5.221 +
   5.222 +        (x, X) `diamond` (0, Y) = (0, Y)
   5.223 +        (x, X) `diamond` (1, Y) = (x, X)
   5.224 +        """
   5.225 +        top = top_a * top_b
   5.226 +        bot = top_b * (bot_a ^ bot_b) ^ bot_b
   5.227 +        return (top, bot)
   5.228 +
   5.229 +
   5.230 +class Toft05Runtime(ComparisonToft05Mixin, Runtime):
   5.231 +    """Default mix of L{ComparisonToft05Mixin} and L{Runtime}."""
   5.232 +    pass
   5.233 +
   5.234 +
   5.235  class ComparisonToft07Mixin:
   5.236  
   5.237      """Efficient comparison by Tomas Toft 2007.
     6.1 --- a/viff/test/test_runtime.py	Wed Mar 19 21:50:24 2008 +0100
     6.2 +++ b/viff/test/test_runtime.py	Wed Mar 19 21:50:38 2008 +0100
     6.3 @@ -32,7 +32,7 @@
     6.4  from twisted.internet.defer import gatherResults
     6.5  
     6.6  from viff.field import GF256
     6.7 -from viff.runtime import Share
     6.8 +from viff.runtime import Share, Toft05Runtime
     6.9  
    6.10  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
    6.11  
    6.12 @@ -129,6 +129,10 @@
    6.13  
    6.14          return gatherResults([opened_a, opened_b, opened_c])
    6.15  
    6.16 +
    6.17 +class ConvertBitShareTest(RuntimeTestCase):
    6.18 +    runtime_class = Toft05Runtime
    6.19 +
    6.20      @protocol
    6.21      def test_convert_bit_share(self, runtime):
    6.22          """Test conversion 0/1 element conversion from Zp to GF256."""
     7.1 --- a/viff/test/test_runtime_comp.py	Wed Mar 19 21:50:24 2008 +0100
     7.2 +++ b/viff/test/test_runtime_comp.py	Wed Mar 19 21:50:38 2008 +0100
     7.3 @@ -21,19 +21,23 @@
     7.4  
     7.5  import operator
     7.6  
     7.7 -from viff.runtime import Toft07Runtime
     7.8 +from viff.runtime import Toft05Runtime, Toft07Runtime
     7.9  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
    7.10  
    7.11  class GreaterThanTest(BinaryOperatorTestCase, RuntimeTestCase):
    7.12 +    runtime_class = Toft05Runtime
    7.13      operator = operator.gt
    7.14  
    7.15  class GreaterThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):
    7.16 +    runtime_class = Toft05Runtime
    7.17      operator = operator.ge
    7.18  
    7.19  class LessThanTest(BinaryOperatorTestCase, RuntimeTestCase):
    7.20 +    runtime_class = Toft05Runtime
    7.21      operator = operator.lt
    7.22  
    7.23  class LessThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):
    7.24 +    runtime_class = Toft05Runtime
    7.25      operator = operator.le
    7.26  
    7.27  class Toft07GreaterThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):