Hi VIFF'ers
I think I have found a bug in the Shamir code
In the following function:
def share(secret, threshold, num_players):
assert threshold >= 0 and threshold < num_players, "Threshold out of range"
coef = [secret]
for j in range(threshold):
# TODO: introduce a random() method in FieldElements so that
# this wont have to be a long when we are sharing a
# GMPIntegerFieldElement.
coef.append(rand.randint(0, long(secret.modulus)-1))
shares = []
for i in range(1, num_players+1):
# Instead of calculating s_i as
#
# s_i = s + a_1 x_i + a_2 x_i^2 + ... + a_t x_i^t
#
# we avoid the exponentiations by calculating s_i by
#
# s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
#
# This is a little faster, even for small n and t.
cur_point = secret.field(i)
cur_share = coef[threshold]
# Go backwards from threshold-1 down to 0
for j in range(threshold-1, -1, -1):
cur_share = coef[j] + cur_share * cur_point
shares.append((cur_point, cur_share))
return shares
The bug is this line:
cur_point = secret.field(i)
If the number of player exceed the size of the field then the function returns
the wrong id (cur_point)?
Anybody see anything wrong in this patch:
+++ b/viff/viff/passive.py
@@ -542,10 +542,10 @@
shares = shamir.share(field(number), threshold,
self.num_players)
for other_id, share in shares:
- if other_id.value == self.id:
+ if other_id == self.id:
results.append(Share(self, share.field, share))
else:
- self.protocols[other_id.value].sendShare(pc, share)
+ self.protocols[other_id].sendShare(pc, share)
else:
results.append(self._expect_share(peer_id, field))
diff --git a/viff/viff/shamir.py b/viff/viff/shamir.py
--- a/viff/viff/shamir.py
+++ b/viff/viff/shamir.py
@@ -72,7 +72,7 @@
# s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
#
# This is a little faster, even for small n and t.
- cur_point = secret.field(i)
+ cur_point = i
cur_share = coef[threshold]
# Go backwards from threshold-1 down to 0
for j in range(threshold-1, -1, -1):
____________________________________________________
Janus Dam Nielsen
Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY
THE ALEXANDRA INSTITUTE LTD.
T +45 40 83 09 10
E janus.niel...@alexandra.dk
W alexandra.dk
See our blog about security at blog.sikkerhed.alexandra.dk
____________________________________________________
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
