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