[viff-devel] FW: Bug in ViFF

[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