Thanks for the answers. I had a suspicion that I was missing something. Maybe we should make the check that Ivan suggested. I am not sure, where it would be appropriate to do it?
On 21/04/2010, at 14.54, Ivan Damgård wrote: > 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 > ____________________________________________________ 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
