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
