/rev/591451fd23dc
changeset: 1246:591451fd23dc
user: Marcel Keller <[email protected]>
date: Thu Sep 17 14:35:26 2009 +0200
summary: Optimize PRSS multiplication triples preprocessing.
This is done by using only one PRF call for several shares.
diffstat:
viff/active.py | 31 +++++++++++++++++--------------
viff/passive.py | 19 ++++++++++---------
viff/prss.py | 41 ++++++++++++++++++++++++++---------------
viff/test/test_runtime_prss.py | 6 +++---
viff/test/test_util.py | 2 +-
5 files changed, 57 insertions(+), 42 deletions(-)
diffs (211 lines):
diff -r be9c8eb7b4d0 -r 591451fd23dc viff/active.py
--- a/viff/active.py Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/active.py Thu Sep 17 14:35:26 2009 +0200
@@ -428,32 +428,35 @@
@increment_pc
@preprocess("generate_triples")
def get_triple(self, field):
- count, result = self.generate_triples(field)
+ count, result = self.generate_triples(field, quantity=1)
result.addCallback(lambda triples: triples[0])
return result
@increment_pc
- def generate_triples(self, field):
- """Generate a multiplication triple using PRSS.
+ def generate_triples(self, field, quantity=20):
+ """Generate *quantity* multiplication triples using PRSS.
These are random numbers *a*, *b*, and *c* such that ``c =
ab``. This function can be used in pre-processing.
- Returns a tuple with the number of triples generated (1) and a
+ Returns a tuple with the number of triples generated and a
Deferred which will yield a singleton-list with a 3-tuple.
"""
- a_t = self.prss_share_random(field)
- b_t = self.prss_share_random(field)
- r_t, r_2t = self.prss_double_share(field)
+ a_t = self.prss_share_random_multi(field, quantity)
+ b_t = self.prss_share_random_multi(field, quantity)
+ r_t, r_2t = self.prss_double_share(field, quantity)
+ c_t = [0] * quantity
- # Multiply a and b without resharing.
- c_2t = gather_shares([a_t, b_t])
- c_2t.addCallback(lambda (a, b): a * b)
+ for i in range(quantity):
+ # Multiply a and b without resharing.
+ c_2t = gather_shares([a_t[i], b_t[i]])
+ c_2t.addCallback(lambda (a, b): a * b)
- d_2t = c_2t - r_2t
- d = self.open(d_2t, threshold=2*self.threshold)
- c_t = r_t + d
- return 1, succeed([(a_t, b_t, c_t)])
+ d_2t = c_2t - r_2t[i]
+ d = self.open(d_2t, threshold=2*self.threshold)
+ c_t[i] = r_t[i] + d
+
+ return quantity, succeed(zip(a_t, b_t, c_t))
class BasicActiveRuntime(PassiveRuntime):
diff -r be9c8eb7b4d0 -r 591451fd23dc viff/passive.py
--- a/viff/passive.py Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/passive.py Thu Sep 17 14:35:26 2009 +0200
@@ -375,8 +375,9 @@
return [Share(self, field, share) for share in shares]
@increment_pc
- def prss_share_zero(self, field):
- """Generate shares of the zero element from the field given.
+ def prss_share_zero(self, field, quantity):
+ """Generate *quantity* shares of the zero element from the
+ field given.
Communication cost: none.
"""
@@ -384,19 +385,19 @@
prss_key = tuple(self.program_counter)
prfs = self.players[self.id].prfs(field.modulus)
zero_share = prss_zero(self.num_players, self.threshold, self.id,
- field, prfs, prss_key)
- return Share(self, field, zero_share)
+ field, prfs, prss_key, quantity)
+ return [Share(self, field, zero_share[i]) for i in range(quantity)]
@increment_pc
- def prss_double_share(self, field):
- """Make a double-sharing using PRSS.
+ def prss_double_share(self, field, quantity):
+ """Make *quantity* double-sharings using PRSS.
The pair of shares will have degree t and 2t where t is the
default threshold for the runtime.
"""
- r_t = self.prss_share_random(field)
- z_2t = self.prss_share_zero(field)
- return (r_t, r_t + z_2t)
+ r_t = self.prss_share_random_multi(field, quantity)
+ z_2t = self.prss_share_zero(field, quantity)
+ return (r_t, [r_t[i] + z_2t[i] for i in range(quantity)])
@increment_pc
def prss_share_bit_double(self, field):
diff -r be9c8eb7b4d0 -r 591451fd23dc viff/prss.py
--- a/viff/prss.py Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/prss.py Thu Sep 17 14:35:26 2009 +0200
@@ -169,21 +169,21 @@
return (convert_replicated_shamir(n, j, field, rep_shares),
convert_replicated_shamir(n, j, GF256, lsb_shares))
-...@fake(lambda n, t, j, field, prfs, key: field(0))
-def prss_zero(n, t, j, field, prfs, key):
- """Return a pseudo-random secret zero-sharing of degree 2t.
+...@fake(lambda n, t, j, field, prfs, key, quantity: [field(0)] * quantity)
+def prss_zero(n, t, j, field, prfs, key, quantity):
+ """Return *quantity* pseudo-random secret zero-sharings of degree 2t.
>>> from field import GF
>>> Zp = GF(23)
>>> prfs = {frozenset([1,2]): PRF("a", 7),
... frozenset([1,3]): PRF("b", 7),
... frozenset([2,3]): PRF("c", 7)}
- >>> prss_zero(3, 1, 1, Zp, prfs, "key")
- {16}
- >>> prss_zero(3, 1, 2, Zp, prfs, "key")
- {13}
- >>> prss_zero(3, 1, 3, Zp, prfs, "key")
- {14}
+ >>> prss_zero(3, 1, 1, Zp, prfs, "key", 1)
+ [{16}]
+ >>> prss_zero(3, 1, 2, Zp, prfs, "key", 1)
+ [{13}]
+ >>> prss_zero(3, 1, 3, Zp, prfs, "key", 1)
+ [{14}]
If we recombine 2t + 1 = 3 shares we can verify that this is
indeed a zero-sharing:
@@ -200,12 +200,19 @@
# We then proceed with the zero-sharing. The first part is like in
# a normal PRSS.
- result = 0
+ result = [0] * quantity
all = frozenset(range(1, n+1))
+ modulus = field.modulus
+
for subset, shares in rep_shares:
- points = [(field(x), 0) for x in all-subset]
- points.append((0, 1))
- f_in_j = shamir.recombine(points, j)
+ try:
+ f_in_j = _f_in_j_cache[(field, n, j, subset)]
+ except KeyError:
+ points = [(field(x), 0) for x in all-subset]
+ points.append((0, 1))
+ f_in_j = shamir.recombine(points, j)
+ _f_in_j_cache[(field, n, j, subset)] = f_in_j
+
# Unlike a normal PRSS we have an inner sum where we use a
# degree 2t polynomial g_i which we choose as
#
@@ -214,9 +221,13 @@
# since we already have the degree t polynomial f at hand. The
# g_i are all linearly independent as required by the protocol
# and can thus be used for the zero-sharing.
- for i, share in shares:
+ for i, packed_share in shares:
g_i_in_j = f_in_j * j**i
- result += share * g_i_in_j
+
+ for k in range(quantity):
+ result[k] += (packed_share % modulus) * g_i_in_j
+ packed_share /= modulus
+
return result
def generate_subsets(orig_set, size):
diff -r be9c8eb7b4d0 -r 591451fd23dc viff/test/test_runtime_prss.py
--- a/viff/test/test_runtime_prss.py Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/test/test_runtime_prss.py Thu Sep 17 14:35:26 2009 +0200
@@ -130,7 +130,7 @@
@protocol
def test_prss_share_zero_bit(self, runtime):
"""Tests the sharing of a zero GF256 element using PRSS."""
- a = runtime.prss_share_zero(GF256)
+ a = runtime.prss_share_zero(GF256, 1)[0]
self.assert_type(a, Share)
opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -140,7 +140,7 @@
@protocol
def test_prss_share_zero_int(self, runtime):
"""Tests the sharing of a zero Zp element using PRSS."""
- a = runtime.prss_share_zero(self.Zp)
+ a = runtime.prss_share_zero(self.Zp, 1)[0]
self.assert_type(a, Share)
opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -150,7 +150,7 @@
@protocol
def test_prss_double_share(self, runtime):
"""Test double-sharing of random numbers using PRSS."""
- r_t, r_2t = runtime.prss_double_share(self.Zp)
+ r_t, r_2t = zip(*runtime.prss_double_share(self.Zp, 1))[0]
self.assert_type(r_t, Share)
self.assertEquals(r_t.field, self.Zp)
diff -r be9c8eb7b4d0 -r 591451fd23dc viff/test/test_util.py
--- a/viff/test/test_util.py Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/test/test_util.py Thu Sep 17 14:35:26 2009 +0200
@@ -70,7 +70,7 @@
self.assertEquals(bit, GF256(1))
def test_prss_zero(self):
- share = prss.prss_zero(None, None, None, self.field, None, None)
+ share = prss.prss_zero(None, None, None, self.field, None, None, 1)[0]
self.assertEquals(share, self.field(0))
_______________________________________________
viff-commits mailing list
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-commits-viff.dk
