Giving this an importance level of 5... feel free to bump it if you
think it should go higher!

I'm also not sure if this will be worth the complexity, especially if
it only works in special cases... It was just something Tomas Toft
talked about a long time ago and I just wanted to record it out here
on the tracker.

At 9:30 +0100 14/03/08, Martin Geisler wrote:
>..
>using only one resharing at the end, saving network traffic. There
>does not seem to be many places where we do stuff like that, though.
>So the overhead of keeping track of when resharing is needed might be
>too big for this to be an improvement.
>

Note also that the actual values of n and t, and whether we have 
active security influence whether this will work or not. Example: if 
we have n= 3t+1 and active adversary, then a polynomial of degree 2t 
will not determine the secret uniquely: the bad guys could arrange to 
be consistent with 2t of the honest players using some incorrect 
polynomial. Then only one honest player will be unhappy, and we can 
only tell that someone cheated, not what the correct value is. In 
general for active security, you need honest players enough to 
determine the polynomial (degree+1) and then on top as many honest 
players as there are bad guys. Then the secret is unique and can be 
reconstructed from the shares, even if bad guys send incorrect stuff.

regards, Ivan

After multiplying two shares, the result is a correct share of the
product, but a share from a polynomial of degree 2t. We therefore
normally reshare to get a polynomial of degree t.

But for doing addition these degree 2t shares are fine, so we could
wait with the resharing until it is surely needed.

Let [a]_t denote a share of a using a degree t polynomial and let
[a]_2t -> [a]_t denote a resharing going from degree 2t to t.

We could then calculate

  sum([a_i]_t * [b_i]_t) = sum([a_i b_i]_2t)
                         = [sum(a_i b_i)]_2t -> [sum(a_i b_i)]_t

using only one resharing at the end, saving network traffic. There
does not seem to be many places where we do stuff like that, though.
So the overhead of keeping track of when resharing is needed might be
too big for this to be an improvement.