4
$\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$
7
$\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$$ (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!

| improve this answer | |
$\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 '19 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$ – Cryptonaut Apr 10 '19 at 1:21
  • $\begingroup$ @ZeroKnowledge There is another answer posted here that is basically a comment on your answer. Can you have a quick look at it and see if it has any value for this answer? I'll have to remove it soon, and it is too big to convert to comment. $\endgroup$ – Maarten Bodewes Apr 5 at 11:24
  • 1
    $\begingroup$ @MaartenBodewes Added a note to my answer to clarify the possible misunderstanding in the referenced comment. $\endgroup$ – Cryptonaut Apr 6 at 12:17
-2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Usually you assume some basic "standard" arithmetic rules, when computing on secret shared values. One of these rules is that if you add/subtract a public constant like $e \cdot d$ to some secret shared value, then this is realized by only one party adding it to its share. For the sake of completeness I'll add a short note in my answer regarding this issue. Thank you for pointing out this possible issue of confusion. $\endgroup$ – Cryptonaut Apr 6 at 12:12

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.