3
$\begingroup$

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?
$\endgroup$
5
$\begingroup$

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$$

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!

$\endgroup$
  • $\begingroup$ Thank you for your answer! Does it mean that the number of multiplication triples equal to the number of multiplication gates? $\endgroup$ – mallea Apr 10 at 1:18
  • 1
    $\begingroup$ That's correct. At the end of the preprocessing phase you need to have generated exactly as many triples as you have multiplication gates in the circuit. $\endgroup$ – ZeroKnowledge Apr 10 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.