"Sigurd Torkel Meldgaard" <[EMAIL PROTECTED]> writes:
Hi Sigurd,
Great work, please see my comments below.
> Another equality test mixin, can be used as drop-in replacement for
> the other one I made, and faster too!
>
> Added faster (for 65 bits moduli) equality protocol.
>
> This one is much simpler than the probabilistic one, and in informal
> tests much faster (3.4 times in benchmark with default settings),
> because it is deterministic, so we only need to test once.
Woohuu, that sounds very cool!
> There is a benchmark operation (feq) for it in apps.benchmark.
Nice.
> Also gave it testcases (just reusing those for the probabilistic
> protocol).
>
> diff -r 252f375f8e91 apps/benchmark.py
> --- a/apps/benchmark.py Wed Oct 08 14:16:40 2008 +0200
> +++ b/apps/benchmark.py Wed Oct 08 14:19:53 2008 +0200
> @@ -67,7 +67,7 @@
> from viff.active import BasicActiveRuntime, \
> TriplesHyperinvertibleMatricesMixin, TriplesPRSSMixin
> from viff.comparison import ComparisonToft05Mixin, ComparisonToft07Mixin
> -from viff.equality import ProbabilisticEqualityMixin
> +from viff.equality import ProbabilisticEqualityMixin, FermatEqualityMixin
> from viff.paillier import PaillierRuntime
> from viff.config import load_config
> from viff.util import find_prime, rand
> @@ -91,7 +91,7 @@
> print "*" * 6
>
>
> -operations = ["mul", "compToft05", "compToft07", "eq"]
> +operations = ["mul", "compToft05", "compToft07", "peq", "feq"]
>
> parser = OptionParser()
> parser.add_option("-m", "--modulus",
> @@ -280,9 +280,12 @@
> elif options.operation == "compToft07":
> operation = operator.ge
> mixins.append(ComparisonToft07Mixin)
> - elif options.operation == "eq":
> + elif options.operation == "peq":
> operation = operator.eq
> mixins.append(ProbabilisticEqualityMixin)
> + elif options.operation == "feq":
> + operation = operator.eq
> + mixins.append(FermatEqualityMixin)
>
> print "Using the base runtime: %s." % base_runtime_class
> print "With the following mixins:"
> diff -r 252f375f8e91 viff/equality.py
> --- a/viff/equality.py Wed Oct 08 14:16:40 2008 +0200
> +++ b/viff/equality.py Wed Oct 08 14:19:53 2008 +0200
> @@ -21,6 +21,29 @@
> """
>
> from viff.runtime import increment_pc
> +
> +class FermatEqualityMixin:
> + def equal(self, x, y):
> + """
> + Returns a share of 1 if `x == y mod p` and 0 otherwise.
I think you should use double back-quotes: ``x == y mod p`` around
code for it to be formatted correctly with Sphinx. You can test is
with
./run.py sphinx dist
after installing Sphinx.
> + Assumes the modulus *p* is a prime.
> +
> + Theory:
> + Fermat: for *p* prime, `x != p mod p`
> + `x ** (p - 1) == 1 mod p`
> + `0 ** (p - 1) mod p == 0`"""
The final """ should go on a line by itself, maybe after an empty line
since old Emacs versions it doesn't know better when you do M-q :-)
> + if isinstance(x, int):
> + if isinstance(y, int):
> + if x == y:
> + return 1
> + else:
> + return 0
> + field = y.field
> + else:
> + field = x.field
> + return 1 - square_and_multiply(x - y, x.field.modulus - 1)
> +
>
> class ProbabilisticEqualityMixin:
> """This class implements probabilistic constant-round secure
> @@ -83,6 +106,31 @@
>
> return x[0]
>
> +def square_and_multiply(x, expt):
> + """Exponentiation by the well-known square-and-multiply algorithm.
> +
> + *x* is a share or another numeric type closed over \* and \+.
Do you have to escape the plus?
> + *expt* is an integraln type implementing bitshift.
"integral"? What about renaming the variable to "exponent"?
> + >>> square_and_multiply(3, 3)
> + 27
> + >>> square_and_multiply(33, 5)
> + 39135393
> + >>> from viff.field import GF
> + >>> square_and_multiply(GF(59)(4),58)
> + {1}
> + >>> square_and_multiply(100, 0)
> + 1
> + """
> + result = 1
> + while expt > 0:
> + if expt % 2:
> + result = result * x
> + x = x * x
> + expt = expt // 2
> + return result
> +
> def legendre_mod_p(a):
> """Return the legendre symbol ``legendre(a, p)`` where *p* is the
> order of the field of *a*.
> diff -r 252f375f8e91 viff/test/test_runtime_equal.py
> --- a/viff/test/test_runtime_equal.py Wed Oct 08 14:16:40 2008 +0200
> +++ b/viff/test/test_runtime_equal.py Wed Oct 08 14:19:53 2008 +0200
> @@ -20,7 +20,7 @@
>
> import operator
>
> -from viff.equality import ProbabilisticEqualityMixin
> +from viff.equality import ProbabilisticEqualityMixin, FermatEqualityMixin
> from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase
> from viff.runtime import Runtime
>
> @@ -28,7 +28,12 @@
> __doctests__ = ['viff.equality']
>
>
> -class EqualRuntime(Runtime, ProbabilisticEqualityMixin):
> +class FermatEqualRuntime(Runtime, FermatEqualityMixin):
> + """A runtime with the equality mixin."""
> + pass
> +
> +
> +class ProbabilisticEqualRuntime(Runtime, ProbabilisticEqualityMixin):
> """A runtime with the equality mixin."""
> pass
>
> @@ -39,15 +44,16 @@
> # Arbitrarily chosen.
> a = 12442
> b = 91243
> - runtime_class = EqualRuntime
> + runtime_class = ProbabilisticEqualRuntime
> operator = operator.eq
>
>
> -class ProbabilisticEqualityTestEqual(BinaryOperatorTestCase,
> RuntimeTestCase):
> +class ProbabilisticEqualityTestEqual(BinaryOperatorTestCase,
> + RuntimeTestCase):
> """Testing the equality with *a* and *b* equal."""
> a = 4023
> b = 4023
> - runtime_class = EqualRuntime
> + runtime_class = ProbabilisticEqualRuntime
> operator = operator.eq
>
>
> @@ -56,7 +62,7 @@
> """Testing ``a == b`` where ``b = a + 1``."""
> a = 0
> b = 1
> - runtime_class = EqualRuntime
> + runtime_class = ProbabilisticEqualRuntime
> operator = operator.eq
>
>
> @@ -65,5 +71,42 @@
> """Testing ``a == b`` where ``a = b + 1``."""
> a = 1
> b = 0
> - runtime_class = EqualRuntime
> + runtime_class = ProbabilisticEqualRuntime
> operator = operator.eq
> +
> +
> +class FermatEqualityTestDifferent(BinaryOperatorTestCase,
> + RuntimeTestCase):
> + """Testing the equality with *a* and *b* different."""
> + # Arbitrarily chosen.
> + a = 12442
> + b = 91243
> + runtime_class = FermatEqualRuntime
> + operator = operator.eq
> +
> +
> +class FermatEqualityTestEqual(BinaryOperatorTestCase,
> + RuntimeTestCase):
> + """Testing the equality with *a* and *b* equal."""
> + a = 4023
> + b = 4023
> + runtime_class = FermatEqualRuntime
> + operator = operator.eq
> +
> +
> +class FermatEqualityTestDiff1_1(BinaryOperatorTestCase,
> + RuntimeTestCase):
> + """Testing ``a == b`` where ``b = a + 1``."""
> + a = 0
> + b = 1
> + runtime_class = FermatEqualRuntime
> + operator = operator.eq
> +
> +
> +class FermatEqualityTestDiff1_2(BinaryOperatorTestCase,
> + RuntimeTestCase):
> + """Testing ``a == b`` where ``a = b + 1``."""
> + a = 1
> + b = 0
> + runtime_class = FermatEqualRuntime
> + operator = operator.eq
--
Martin Geisler
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
_______________________________________________
viff-patches mailing list
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
