Beaver triples

The additions of linearly shared values (and generally any linear operations) can be done locally, without any interaction between the parties: ​$[x + y] = [x] + [y]$. Multiplication requires interaction. The following fundamental construction by Beaver allows to do it provided we have a certain precomputed data:

Assume that we have a precomputed triple of shared values ​$[a], [b], [c]$, satisfying the following properties:

1. $ab = c$
2. $a, b$ and sharings of all three are distributed uniformly randomly independently for all parties.

Then, the following construction allows us to sacrifice this pre-computed triple to multiply two shared elements: $\text{open: } (x+a), (y+b)$ $[xy] = (x+a)[y] + (y+b)[x] - (x+a)(y+b) + [c]$ It is easy to see (by direct inspection), that what we've obtained is, indeed, the sharing of $xy$. ​ The triple must be "sacrificed", i.e. never used again anywhere, so that openings of $x+a$ and $y+b$ leak no information. The problem of actually constructing Beaver triples is a known cryptographic problem. It is isolated and out of scope of our research, so we treat Beaver triples as an idealized functionality.