Re: [viff-devel] FW: Bug in ViFF
Hi all Today, Sebastiaan and I have been doing some serious thinking and looking into the VIFF code, and we feel convinced that we've found the bug. The problem lies entirely in the multiplication protocol. In Runtime.mul, products of shares are computed and shared. Then secure Lagrange interpolation runs to "reconstruct" the original sharing. With an odd number of players, $n$, and threshold $t = (n-1)/2$ a contribution is needed from all parties. But if the threshold is lower or there are more parties, then "reconstruction" doesn't require all shares. VIFF uses this to optimize the protocol, using only the first $2t+1$ shares received. This doesn't work for the multiplication protocol: Unless shares from the /same/ parties are used, there will be a mismatch. Say we have players 1,2,3,4 and a threshold of 1. Each $i$ shares their product with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then the polynomial is P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x) Another could use 2,3,4, thus interpolating P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x) Clearly this is not the same computation! Thus, the parties end up with inconsistent shares -- they have points on different polynomials. To solve the problem, the players must agree on which shares are used. A simple solution is to require all shares present. Alternatively (for the passive case) we could say that only the first $2t+1$ parties share the products of their shares. This basically eliminates any need for any of the other parties. Regards, Tomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
[EMAIL PROTECTED] writes: > Hi all > > > Today, Sebastiaan and I have been doing some serious thinking and > looking into the VIFF code, and we feel convinced that we've found the > bug. Great work, thanks to both of you for solving the mystery! I guess this bug is sufficiently grave that we should do a 0.7.1 release to fix it. So let me know if you've found other weird things... > The problem lies entirely in the multiplication protocol. In > Runtime.mul, products of shares are computed and shared. Then secure > Lagrange interpolation runs to "reconstruct" the original sharing. > > With an odd number of players, $n$, and threshold $t = (n-1)/2$ a > contribution is needed from all parties. But if the threshold is lower > or there are more parties, then "reconstruction" doesn't require all > shares. VIFF uses this to optimize the protocol, using only the first > $2t+1$ shares received. > > This doesn't work for the multiplication protocol: Unless shares from > the /same/ parties are used, there will be a mismatch. Say we have > players 1,2,3,4 and a threshold of 1. Each $i$ shares their product > with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then > the polynomial is > > P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x) > > Another could use 2,3,4, thus interpolating > > P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x) > > Clearly this is not the same computation! Thus, the parties end up > with inconsistent shares -- they have points on different polynomials. > > To solve the problem, the players must agree on which shares are used. > A simple solution is to require all shares present. Alternatively (for > the passive case) we could say that only the first $2t+1$ parties > share the products of their shares. This basically eliminates any need > for any of the other parties. That would be a good idea, also for performance. I suggest that we use a round-robin system where we determine the perticipating subset based on the current program counter. So far I have a failing unit test which clearly shows the bug, I'll try and fix it now. -- Martin Geisler pgpFQx5rzicnb.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Martin Geisler <[EMAIL PROTECTED]> writes: > That would be a good idea, also for performance. I suggest that we use > a round-robin system where we determine the perticipating subset based > on the current program counter. Code for this would look like this: diff --git a/viff/runtime.py b/viff/runtime.py --- a/viff/runtime.py +++ b/viff/runtime.py @@ -39,7 +39,7 @@ from collections import deque from viff import shamir -from viff.prss import prss, prss_lsb, prss_zero +from viff.prss import prss, prss_lsb, prss_zero, generate_subsets from viff.field import GF256, FieldElement from viff.util import wrapper, rand @@ -703,6 +703,18 @@ def __init__(self, player, threshold, options=None): """Initialize runtime.""" BasicRuntime.__init__(self, player, threshold, options) +self.subsets = {} + +def select_subset(self, threshold): +"""Select subset for *threshold* based on current program counter.""" +try: +subsets = self.subsets[threshold] +except KeyError: +players = frozenset(range(1, self.num_players+1)) +subsets = list(generate_subsets(players, 2*threshold + 1)) +self.subsets[threshold] = subsets +return subsets[hash(tuple(self.program_counter)) % len(subsets)] + @increment_pc def open(self, share, receivers=None, threshold=None): (perhaps with an @increment_pc decorator...) > So far I have a failing unit test which clearly shows the bug, I'll > try and fix it now. I've pushed the new unit tests as revision 4daa42544157, but I'm afraid I'm too tired to fix things tonight... feel free to jump in :-) -- Martin Geisler pgpO73AHmQUgo.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Hi, Tomas is right, of course. For the passive case, using the first 2t+1 players always works, and for the active case, we do not use the local-multiply-and-reshare method anyway. The current implementation of active security has a preprocessing step based on either PRSS or hyper invertible matrices, and a computation phase where all we do is that we open shared values. Neither phase has the problem encountered here. regards, Ivan Quoting [EMAIL PROTECTED]: > > > Hi all > > > Today, Sebastiaan and I have been doing some serious thinking and > looking into the VIFF code, and we feel convinced that we've found the > bug. > > > > The problem lies entirely in the multiplication protocol. In > Runtime.mul, products of shares are computed and shared. Then secure > Lagrange interpolation runs to "reconstruct" the original sharing. > > With an odd number of players, $n$, and threshold $t = (n-1)/2$ a > contribution is needed from all parties. But if the threshold is lower > or there are more parties, then "reconstruction" doesn't require all > shares. VIFF uses this to optimize the protocol, using only the first > $2t+1$ shares received. > > This doesn't work for the multiplication protocol: Unless shares from > the /same/ parties are used, there will be a mismatch. Say we have > players 1,2,3,4 and a threshold of 1. Each $i$ shares their product > with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then > the polynomial is > > P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x) > > Another could use 2,3,4, thus interpolating > > P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x) > > Clearly this is not the same computation! Thus, the parties end up > with inconsistent shares -- they have points on different polynomials. > > To solve the problem, the players must agree on which shares are used. A > simple solution is to require all shares present. Alternatively (for the > passive case) we could say that only the first $2t+1$ parties share the > products of their shares. This basically eliminates any need for any of > the other parties. > > Regards, > Tomas > > > ___ > 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
Re: [viff-devel] FW: Bug in ViFF
> Tomas is right, of course. For the passive case, using the first 2t+1 players > always works, and for the active case, we do not use the > local-multiply-and-reshare method anyway. The thing is, I always just assumed that we always used the same set of shares, and it is kind of easy to miss if you just read quickly through it - it says what you expect. I guess that's why we all missed it until now. The unit tests should not be hardcoded to n=3, t=1 as they are now, because that's why we never found the problem in the first place. I can rewrite the unit tests to the general setting. It needs to be done. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk