viff

changeset 1037:d47b8da68a23

More realistic fake field elements. Arithmetic on the elements now always return p-1 instead of 1. This makes the elements use more RAM and gives a more realistic communication complexity. Thanks to Peter Schwabe for noticing the problem.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 05 Dec 2008 11:13:29 +0100
parents f7d1f7cd3dda
children ab4a8125d1d8
files apps/benchmark.py viff/field.py
diffstat 2 files changed, 50 insertions(+), 44 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Sun Nov 30 23:13:26 2008 +0100
     1.2 +++ b/apps/benchmark.py	Fri Dec 05 11:13:29 2008 +0100
     1.3 @@ -62,7 +62,7 @@
     1.4  
     1.5  from twisted.internet import reactor
     1.6  
     1.7 -from viff.field import GF, GF256, FakeFieldElement
     1.8 +from viff.field import GF, GF256, FakeGF
     1.9  from viff.runtime import BasicRuntime, create_runtime, gather_shares, \
    1.10      make_runtime_class
    1.11  from viff.passive import PassiveRuntime
    1.12 @@ -139,11 +139,12 @@
    1.13      parser.error("threshold out of range")
    1.14  
    1.15  if options.fake:
    1.16 -    Zp = FakeFieldElement
    1.17      print "Using fake field elements"
    1.18 -else:
    1.19 -    Zp = GF(find_prime(options.modulus))
    1.20 -    print "Using real field elements (%d bit modulus)" % log(Zp.modulus, 2)
    1.21 +    GF = FakeGF
    1.22 +
    1.23 +Zp = GF(find_prime(options.modulus))
    1.24 +print "Using field elements (%d bit modulus)" % log(Zp.modulus, 2)
    1.25 +
    1.26  count = options.count
    1.27  print "I am player %d, will %s %d numbers" % (id, options.operation, count)
    1.28  
     2.1 --- a/viff/field.py	Sun Nov 30 23:13:26 2008 +0100
     2.2 +++ b/viff/field.py	Fri Dec 05 11:13:29 2008 +0100
     2.3 @@ -514,56 +514,61 @@
     2.4      _field_cache[modulus] = GFElement
     2.5      return GFElement
     2.6  
     2.7 -class FakeFieldElement(FieldElement):
     2.8 -    """Fake field which does no computations.
     2.9 +def FakeGF(modulus):
    2.10 +    """Construct a fake field."""
    2.11  
    2.12 -    This class should only be used in benchmarking. It works like any
    2.13 -    other :class:`FieldElement` except that all computations will give
    2.14 -    ``1`` as the result:
    2.15 +    # Return value of all operations on FakeFieldElements. We choose
    2.16 +    # this value to maximize the communication complexity.
    2.17 +    return_value = modulus - 1
    2.18  
    2.19 -    >>> a = FakeFieldElement(123)
    2.20 -    >>> b = FakeFieldElement(234)
    2.21 -    >>> a + b
    2.22 -    {{1}}
    2.23 -    >>> a * b
    2.24 -    {{1}}
    2.25 -    >>> a.bit(100)
    2.26 -    1
    2.27 -    >>> a.sqrt()
    2.28 -    {{1}}
    2.29 -    """
    2.30 +    class FakeFieldElement(FieldElement):
    2.31 +        """Fake field which does no computations.
    2.32  
    2.33 -    def __init__(self, value):
    2.34 -        """Create a fake field element.
    2.35 +        This class should only be used in benchmarking. It works like any
    2.36 +        other :class:`FieldElement` except that all computations will give
    2.37 +        ``-1`` as the result:
    2.38  
    2.39 -        The element will store *value* in order to take up a realistic
    2.40 -        amount of RAM, but any further computation will yield the
    2.41 -        value ``1``.
    2.42 +        >>> F = FakeGF(1031)
    2.43 +        >>> a = F(123)
    2.44 +        >>> b = F(234)
    2.45 +        >>> a + b
    2.46 +        {{1030}}
    2.47 +        >>> a * b
    2.48 +        {{1030}}
    2.49 +        >>> a.sqrt()
    2.50 +        {{1030}}
    2.51 +        >>> a.bit(100)
    2.52 +        1
    2.53          """
    2.54 -        self.value = value
    2.55  
    2.56 -    # Binary operations.
    2.57 -    __add__ = __radd__ = __sub__ = __rsub__ \
    2.58 -        = __mul__ = __rmul__ = __div__ = __rdiv__ \
    2.59 -        = __truediv__ = __rtruediv__ = __floordiv__ = __rfloordiv__ \
    2.60 -        = __pow__ = __neg__ \
    2.61 -        = lambda self, other: FakeFieldElement(1)
    2.62 +        def __init__(self, value):
    2.63 +            """Create a fake field element.
    2.64  
    2.65 -    # Unary operations.
    2.66 -    __invert__ = sqrt = lambda self: FakeFieldElement(1)
    2.67 +            The element will store *value* in order to take up a realistic
    2.68 +            amount of RAM, but any further computation will yield the
    2.69 +            value ``-1``.
    2.70 +            """
    2.71 +            self.value = value
    2.72  
    2.73 -    # Bit extraction. We pretend that the number is *very* big.
    2.74 -    bit = lambda self, index: 1
    2.75 +        # Binary operations.
    2.76 +        __add__ = __radd__ = __sub__ = __rsub__ \
    2.77 +            = __mul__ = __rmul__ = __div__ = __rdiv__ \
    2.78 +            = __truediv__ = __rtruediv__ = __floordiv__ = __rfloordiv__ \
    2.79 +            = __pow__ = __neg__ \
    2.80 +            = lambda self, other: FakeFieldElement(return_value)
    2.81  
    2.82 -    # Fake field elements are printed with double curly brackets.
    2.83 -    __repr__ = __str__ = lambda self: "{{%d}}" % self.value
    2.84 +        # Unary operations.
    2.85 +        __invert__ = sqrt = lambda self: FakeFieldElement(return_value)
    2.86  
    2.87 -FakeFieldElement.field = FakeFieldElement
    2.88 -# Fix the modulus to a fairly large number -- this is used in various
    2.89 -# places when protocols want to generate a random element from the
    2.90 -# interval {0, 1, ..., modulus-1}.
    2.91 -FakeFieldElement.modulus = 987654321
    2.92 +        # Bit extraction. We pretend that the number is *very* big.
    2.93 +        bit = lambda self, index: 1
    2.94  
    2.95 +        # Fake field elements are printed with double curly brackets.
    2.96 +        __repr__ = __str__ = lambda self: "{{%d}}" % self.value
    2.97 +
    2.98 +    FakeFieldElement.field = FakeFieldElement
    2.99 +    FakeFieldElement.modulus = modulus
   2.100 +    return FakeFieldElement
   2.101  
   2.102  if __name__ == "__main__":
   2.103      import doctest    #pragma NO COVER