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 wrap: on
line diff
--- a/apps/benchmark.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/apps/benchmark.py	Wed Mar 19 21:50:38 2008 +0100
@@ -62,7 +62,8 @@
 from twisted.internet import reactor
 
 from viff.field import GF
-from viff.runtime import Runtime, Toft07Runtime, create_runtime, gather_shares
+from viff.runtime import Runtime, Toft05Runtime, Toft07Runtime, \
+     create_runtime, gather_shares
 from viff.config import load_config
 from viff.util import find_prime
 
@@ -195,7 +196,7 @@
     runtime_class = Runtime
 elif options.operation == "comp":
     operation = operator.ge
-    runtime_class = Runtime
+    runtime_class = Toft05Runtime
 elif options.operation == "compII":
     operation = operator.ge
     runtime_class = Toft07Runtime
--- a/apps/compare.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/apps/compare.py	Wed Mar 19 21:50:38 2008 +0100
@@ -26,7 +26,7 @@
 from twisted.internet.defer import gatherResults
 
 from viff.field import GF, GF256
-from viff.runtime import create_runtime
+from viff.runtime import create_runtime, Toft05Runtime
 from viff.config import load_config
 from viff.util import dprint
 
@@ -67,7 +67,7 @@
     results = gatherResults(bits)
     results.addCallback(lambda _: rt.shutdown())
 
-pre_runtime = create_runtime(id, players, 1)
+pre_runtime = create_runtime(id, players, 1, runtime_class=Toft05Runtime)
 pre_runtime.addCallback(protocol)
 
 reactor.run()
--- a/apps/int-bit-conversion.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/apps/int-bit-conversion.py	Wed Mar 19 21:50:38 2008 +0100
@@ -24,7 +24,7 @@
 from twisted.internet import reactor
 
 from viff.field import GF, GF256
-from viff.runtime import create_runtime
+from viff.runtime import create_runtime, Toft05Runtime
 from viff.config import load_config
 
 id, players = load_config(sys.argv[1])
@@ -62,7 +62,8 @@
 
     rt.wait_for(a_b, b_b, c_b, x_b, y_b, z_b)
 
-pre_runtime = create_runtime(id, players, (len(players) -1)//2)
+pre_runtime = create_runtime(id, players, (len(players) -1)//2,
+                             runtime_class=Toft05Runtime)
 pre_runtime.addCallback(protocol)
 
 reactor.run()
--- a/apps/millionaires.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/apps/millionaires.py	Wed Mar 19 21:50:38 2008 +0100
@@ -37,7 +37,7 @@
 from twisted.internet import reactor
 
 from viff.field import GF
-from viff.runtime import Runtime, create_runtime, gather_shares
+from viff.runtime import Runtime, Toft05Runtime, create_runtime, gather_shares
 from viff.config import load_config
 from viff.util import rand, find_prime
 
@@ -142,7 +142,7 @@
     id, players = load_config(args[0])
 
 # Create a deferred Runtime and ask it to run our protocol when ready.
-pre_runtime = create_runtime(id, players, 1, options)
+pre_runtime = create_runtime(id, players, 1, options, Toft05Runtime)
 pre_runtime.addCallback(Protocol)
 
 # Start the Twisted event loop.
--- a/viff/runtime.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/viff/runtime.py	Wed Mar 19 21:50:38 2008 +0100
@@ -854,112 +854,6 @@
             return results
 
     @increment_pc
-    def convert_bit_share(self, share, dst_field):
-        """Convert a 0/1 share into dst_field."""
-        bit = rand.randint(0, 1)
-        dst_shares = self.prss_share(self.players, dst_field, bit)
-        src_shares = self.prss_share(self.players, share.field, bit)
-
-        # TODO: Using a parallel reduce below seems to be slower than
-        # using the built-in reduce.
-
-        # We open tmp and convert the value into a field element from
-        # the dst_field.
-        tmp = self.open(reduce(self.xor, src_shares, share))
-        tmp.addCallback(lambda i: dst_field(i.value))
-        # Must update field on Share when we change the field of the
-        # the value within
-        tmp.field = dst_field
-
-        return reduce(self.xor, dst_shares, tmp)
-
-    @increment_pc
-    def greater_than_equal(self, share_a, share_b):
-        """Compute share_a >= share_b.
-
-        Both arguments must be from the field given. The result is a
-        GF256 share.
-        """
-        field = getattr(share_a, "field", getattr(share_b, "field", None))
-        if not isinstance(share_a, Share):
-            share_a = Share(self, field, share_a)
-        if not isinstance(share_b, Share):
-            share_b = Share(self, field, share_b)
-
-        l = self.options.bit_length
-        m = l + self.options.security_parameter
-        t = m + 1
-
-        # Preprocessing begin
-
-        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
-        assert self.num_players + 2 < 2**l
-
-        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
-        # We must use int_bits without adding callbacks to the bits --
-        # having int_b wait on them ensures this.
-
-        def bits_to_int(bits):
-            """Converts a list of bits to an integer."""
-            return sum([2**i * b for i, b in enumerate(bits)])
-
-        int_b = gather_shares(int_bits)
-        int_b.addCallback(bits_to_int)
-
-        # TODO: this changes int_bits! It should be okay since
-        # int_bits is not used any further, but still...
-        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
-        # Preprocessing done
-
-        a = share_a - share_b + 2**l
-        T = self.open(2**t - int_b + a)
-
-        result = gather_shares([T] + bit_bits)
-        self.callback(result, self._finish_greater_than_equal, l)
-        return result
-
-    @increment_pc
-    def _finish_greater_than_equal(self, results, l):
-        """Finish the calculation."""
-        T = results[0]
-        bit_bits = results[1:]
-
-        vec = [(GF256(0), GF256(0))]
-
-        # Calculate the vector, using only the first l bits
-        for i, bi in enumerate(bit_bits[:l]):
-            Ti = GF256(T.bit(i))
-            ci = Share(self, GF256, bi ^ Ti)
-            vec.append((ci, Ti))
-
-        # Reduce using the diamond operator. We want to do as much
-        # as possible in parallel while being careful not to
-        # switch the order of elements since the diamond operator
-        # is non-commutative.
-        while len(vec) > 1:
-            tmp = []
-            while len(vec) > 1:
-                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
-            if len(vec) == 1:
-                tmp.append(vec[0])
-            vec = tmp
-
-        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
-
-    @increment_pc
-    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
-        """The "diamond-operator".
-
-        Defined by
-
-        (x, X) `diamond` (0, Y) = (0, Y)
-        (x, X) `diamond` (1, Y) = (x, X)
-        """
-        top = top_a * top_b
-        bot = top_b * (bot_a ^ bot_b) ^ bot_b
-        return (top, bot)
-
-    @increment_pc
     def _broadcast(self, sender, message=None):
         """Perform a Bracha broadcast.
 
@@ -1148,6 +1042,121 @@
         return result
 
 
+class ComparisonToft05Mixin:
+    """Comparison by Tomas Toft, 2005."""
+
+    @increment_pc
+    def convert_bit_share(self, share, dst_field):
+        """Convert a 0/1 share into dst_field."""
+        bit = rand.randint(0, 1)
+        dst_shares = self.prss_share(self.players, dst_field, bit)
+        src_shares = self.prss_share(self.players, share.field, bit)
+
+        # TODO: Using a parallel reduce below seems to be slower than
+        # using the built-in reduce.
+
+        # We open tmp and convert the value into a field element from
+        # the dst_field.
+        tmp = self.open(reduce(self.xor, src_shares, share))
+        tmp.addCallback(lambda i: dst_field(i.value))
+        # Must update field on Share when we change the field of the
+        # the value within
+        tmp.field = dst_field
+
+        return reduce(self.xor, dst_shares, tmp)
+
+    @increment_pc
+    def greater_than_equal(self, share_a, share_b):
+        """Compute share_a >= share_b.
+
+        Both arguments must be from the field given. The result is a
+        GF256 share.
+        """
+        field = getattr(share_a, "field", getattr(share_b, "field", None))
+        if not isinstance(share_a, Share):
+            share_a = Share(self, field, share_a)
+        if not isinstance(share_b, Share):
+            share_b = Share(self, field, share_b)
+
+        l = self.options.bit_length
+        m = l + self.options.security_parameter
+        t = m + 1
+
+        # Preprocessing begin
+
+        assert 2**(l+1) + 2**t < field.modulus, "2^(l+1) + 2^t < p must hold"
+        assert self.num_players + 2 < 2**l
+
+        int_bits = [self.prss_share_random(field, True) for _ in range(m)]
+        # We must use int_bits without adding callbacks to the bits --
+        # having int_b wait on them ensures this.
+
+        def bits_to_int(bits):
+            """Converts a list of bits to an integer."""
+            return sum([2**i * b for i, b in enumerate(bits)])
+
+        int_b = gather_shares(int_bits)
+        int_b.addCallback(bits_to_int)
+
+        # TODO: this changes int_bits! It should be okay since
+        # int_bits is not used any further, but still...
+        bit_bits = [self.convert_bit_share(b, GF256) for b in int_bits]
+        # Preprocessing done
+
+        a = share_a - share_b + 2**l
+        T = self.open(2**t - int_b + a)
+
+        result = gather_shares([T] + bit_bits)
+        self.callback(result, self._finish_greater_than_equal, l)
+        return result
+
+    @increment_pc
+    def _finish_greater_than_equal(self, results, l):
+        """Finish the calculation."""
+        T = results[0]
+        bit_bits = results[1:]
+
+        vec = [(GF256(0), GF256(0))]
+
+        # Calculate the vector, using only the first l bits
+        for i, bi in enumerate(bit_bits[:l]):
+            Ti = GF256(T.bit(i))
+            ci = Share(self, GF256, bi ^ Ti)
+            vec.append((ci, Ti))
+
+        # Reduce using the diamond operator. We want to do as much
+        # as possible in parallel while being careful not to
+        # switch the order of elements since the diamond operator
+        # is non-commutative.
+        while len(vec) > 1:
+            tmp = []
+            while len(vec) > 1:
+                tmp.append(self._diamond(vec.pop(0), vec.pop(0)))
+            if len(vec) == 1:
+                tmp.append(vec[0])
+            vec = tmp
+
+        return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
+
+    @increment_pc
+    def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
+        """The "diamond-operator".
+
+        Defined by
+
+        (x, X) `diamond` (0, Y) = (0, Y)
+        (x, X) `diamond` (1, Y) = (x, X)
+        """
+        top = top_a * top_b
+        bot = top_b * (bot_a ^ bot_b) ^ bot_b
+        return (top, bot)
+
+
+class Toft05Runtime(ComparisonToft05Mixin, Runtime):
+    """Default mix of L{ComparisonToft05Mixin} and L{Runtime}."""
+    pass
+
+
 class ComparisonToft07Mixin:
 
     """Efficient comparison by Tomas Toft 2007.
--- a/viff/test/test_runtime.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/viff/test/test_runtime.py	Wed Mar 19 21:50:38 2008 +0100
@@ -32,7 +32,7 @@
 from twisted.internet.defer import gatherResults
 
 from viff.field import GF256
-from viff.runtime import Share
+from viff.runtime import Share, Toft05Runtime
 
 from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
 
@@ -129,6 +129,10 @@
 
         return gatherResults([opened_a, opened_b, opened_c])
 
+
+class ConvertBitShareTest(RuntimeTestCase):
+    runtime_class = Toft05Runtime
+
     @protocol
     def test_convert_bit_share(self, runtime):
         """Test conversion 0/1 element conversion from Zp to GF256."""
--- a/viff/test/test_runtime_comp.py	Wed Mar 19 21:50:24 2008 +0100
+++ b/viff/test/test_runtime_comp.py	Wed Mar 19 21:50:38 2008 +0100
@@ -21,19 +21,23 @@
 
 import operator
 
-from viff.runtime import Toft07Runtime
+from viff.runtime import Toft05Runtime, Toft07Runtime
 from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
 
 class GreaterThanTest(BinaryOperatorTestCase, RuntimeTestCase):
+    runtime_class = Toft05Runtime
     operator = operator.gt
 
 class GreaterThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):
+    runtime_class = Toft05Runtime
     operator = operator.ge
 
 class LessThanTest(BinaryOperatorTestCase, RuntimeTestCase):
+    runtime_class = Toft05Runtime
     operator = operator.lt
 
 class LessThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):
+    runtime_class = Toft05Runtime
     operator = operator.le
 
 class Toft07GreaterThanEqualTest(BinaryOperatorTestCase, RuntimeTestCase):