[viff-devel] FW: Bug in ViFF

[ivan at daimi.au.dk]

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 T.Toft at cwi.nl:

>
>
> 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 at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>