Can we use fixed Beaver's multiplication triples many times?

Question

In the secure computation based on GMW and SPDZ style approaches, we use multiplication triples to gain efficient online computation time.

1. Can a same triples be used multiple times?
2. Is there any need to update the triples?

Answer 1

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply.

Let's recall how the multiplication works in Beaver's protocol for secure evaluation of arithmetic circuits. Protocols like the ones from the SPDZ family follow Beaver's blueprint and "just" add some additional magic on top for getting active security. Let's focus on the simple approach of Beaver, since you will already run into problems there, when you reuse multiplication triples:

Assume you have a secret shared values $[x]$ and $[y]$, where the notation $[x]$ means that $x = \sum^n_{i=1}x_i$ and party $P_i$ has share $x_i$. Let $[a],[b],[c]$ with $c = a \cdot b$ be a secret shared multiplication triple.

To multiply $[x]$ and $[y]$ you compute $[z]$, where $z = x \cdot y$, as follows:

1. Each party computes $$[d] := [x] - [a] = [x-a]$$ and publishes its share thereof (thus revealing $d$)
2. Each party computes $$[e] := [y] - [b] = [y-b]$$ and publishes its share thereof (thus revealing $e$)
3. All parties locally compute $$[z] = [c] + [x]\cdot e + [y] \cdot d - e \cdot d$$ (Note that when we want to add or subtract a public value like $e \cdot d$ to a secret shared value, then only one of the parties adds the public value to its shares.)

Now if you were to reuse the same multiplication triple $[a],[b],[c]$ in another multiplication of some other secret values $[u]$ and $[v]$, then you would reveal $$d' = u - a$$ and $$e' = v - b$$

From this information, a honest-but-curious party could now compute $$ d - d' = (x-a) - (u-a) = x - u$$ This is clearly bad, since it directly reveals the difference between two secret values $x$ and $u$. The same, with $e$ and $e'$, obviously also works to compute the difference $y - v$.

For this reason it is crucial for the security of the protocol that you use every multiplication triple at most once!

Answer 2

There is a problem with this explanation.

At stage 3 you write: " 3. All parties locally compute [z]=[c]+[x]⋅e+[y]⋅d−e⋅d "

You mean that:

z_1 = c_1 + x_1 * e + y_1 * d - e*d

...

z_n = c_n +x_n * e + y_n * d - e*d

When you compute the sum of all shares you want z=xy. However,

z_1+...+z_n = c + x * e + y * d - n * ed = c + x(y-b) + y*(x-a) -n*(x-a)*(y-b) =

= c + xy -xb +xy -ya -n*(xy-ay-xb+ab).

For n different than 1, this is not what you want.