[viff-devel] FW: Bug in ViFF

[Martin Geisler]

T.Toft at cwi.nl 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20081006/5c7d2b81/attachment.pgp>