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

Reply via email to