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
