Fermat equality test

[Sigurd Torkel Meldgaard]

Another equality test mixin, can be used as drop-in replacement for
the other one I made, and faster too!

[Martin Geisler]

"Sigurd Torkel Meldgaard" <***@daimi.au.dk> writes:

Hi Sigurd,

Great work, please see my comments below.

Post by Sigurd Torkel Meldgaard
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!

Post by Sigurd Torkel Meldgaard
There is a benchmark operation (feq) for it in apps.benchmark.

Nice.

Post by Sigurd Torkel Meldgaard
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 @@
operation = operator.ge
mixins.append(ComparisonToft07Mixin)
operation = operator.eq
mixins.append(ProbabilisticEqualityMixin)
+ 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
+
+ """
+ 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.

Post by Sigurd Torkel Meldgaard
+ Assumes the modulus *p* is a prime.
+
+ 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 :-)

Post by Sigurd Torkel Meldgaard
+ return 1
+ return 0
+ field = y.field
+ field = x.field
+ return 1 - square_and_multiply(x - y, x.field.modulus - 1)
+
"""This class implements probabilistic constant-round secure
@@ -83,6 +106,31 @@
return x[0]
+ """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?

Post by Sigurd Torkel Meldgaard
+ *expt* is an integraln type implementing bitshift.

"integral"? What about renaming the variable to "exponent"?

Post by Sigurd Torkel Meldgaard
+ >>> 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
+ result = result * x
+ x = x * x
+ expt = expt // 2
+ return result
+
"""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']
+ """A runtime with the equality mixin."""
+ pass
+
+
"""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,
"""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,
+ """Testing the equality with *a* and *b* different."""
+ # Arbitrarily chosen.
+ a = 12442
+ b = 91243
+ runtime_class = FermatEqualRuntime
+ operator = operator.eq
+
+
+class FermatEqualityTestEqual(BinaryOperatorTestCase,
+ """Testing the equality with *a* and *b* equal."""
+ a = 4023
+ b = 4023
+ runtime_class = FermatEqualRuntime
+ operator = operator.eq
+
+
+class FermatEqualityTestDiff1_1(BinaryOperatorTestCase,
+ """Testing ``a == b`` where ``b = a + 1``."""
+ a = 0
+ b = 1
+ runtime_class = FermatEqualRuntime
+ operator = operator.eq
+
+
+class FermatEqualityTestDiff1_2(BinaryOperatorTestCase,
+ """Testing ``a == b`` where ``a = b + 1``."""
+ a = 1
+ b = 0
+ runtime_class = FermatEqualRuntime
+ operator = operator.eq