Hi folks,
Just wanted to say that the bug is not really a bug, in the following
sense:
For the Shamir based protocol to be secure, the field size MUST be
bigger than
than the number of players. If this is not the case, either a player
would be assigned
the point 0, or two players would be assigned the same point. In
either case,
the protocol is insecure. So that line of code is fine, provided the
runtime
checks that the field or fields you use are large enough and refuses to
run if not. If this check is not done, that's where the bug is
instead :-)
regards, Ivan
On 21/04/2010, at 14.42, Janus Dam Nielsen wrote:
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
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
