This blog post is the second in a series of three in which we describe what SPDZ is. The first part can be found here and the third here.

### The Preprocessing Model

The preprocessing model is a framework in which we assume the existence of a 'trusted dealer' who distributes 'raw material' to the parties before any circuit evaluation takes place. The reason for doing this is that if we have the 'raw material' already in place, the circuit can be evaluated very efficiently.We realise this by splitting the protocol into two phases: a 'preprocessing' (or 'offline') phase where we generate the preprocessed data, and an 'online' phase where we evaluate the circuit. (The term 'offline' is a little misleading, since the parties still communicate.)

### Evaluating the Circuit

We now suppose that the parties have agreed on some arithmetic circuit they want to evaluate jointly.#### Providing input

The
first step of the circuit evaluation is to read in values from (some
of) the parties. In SPDZ, this means getting each party with input,
$P_i$ with $x^i$ (the superscript $i$ is an index to avoid confusion
with $x_i$ which is a share of $x$), to secret-share input $x^i$ to the
other parties.

To
do this, we need to use a share of a random value: each party $P_i$
holds some $r_i$ and the value $r = \sum_i r_i$ is uniformly random and
not known by any party. First, every party sends their share $r_j$ of
$r$ to party $P_i$. This is called a 'partial opening' because $P_i$ now
discovers the value of $r$ (by summing the shares).

Party $P_i$ then broadcasts the value $x^i - r$. Party $P_1$ sets its share of $x^i$ as $x_1^i=r_1 + x^i - r$, and $P_j$ for $j > 1$ sets its share of $x^i$ as $x_i^j=r_j$. (In practice, it is not always $P_1$ who does a different computation.)

Thus we have turned $x^i$ into $\langle x^i \rangle$.

Party $P_i$ then broadcasts the value $x^i - r$. Party $P_1$ sets its share of $x^i$ as $x_1^i=r_1 + x^i - r$, and $P_j$ for $j > 1$ sets its share of $x^i$ as $x_i^j=r_j$. (In practice, it is not always $P_1$ who does a different computation.)

Thus we have turned $x^i$ into $\langle x^i \rangle$.

#### Addition

Suppose
we want to compute some arithmetic circuit on our data; that is, some
series of additions and multiplications. We have the following very
useful properties of an additive sharing scheme:

- If we have some secret-shared field elements $\langle a \rangle$ and $\langle b \rangle$, so party $P_i$ has $a_i$ and $b_i$, each party can locally compute $a_i + b_i$, and hence, since $\sum_i a_i + \sum_i b_i = \sum_i (a_i+b_i)$, they obtain a secret sharing $\langle a + b \rangle$ of the value $a+b$.
- If each party multiplies its share by some public value $\alpha$, then since $\sum_i \alpha a_i = \alpha \sum_i a_i = \alpha a$ the parties obtain a secret sharing $\langle \alpha a \rangle$ of the value $\alpha a$.

In
other words, the secret-sharing is linear; this is good because it
means there is no communication cost for doing these operations.
Unfortunately, we have to do a bit more work to multiply secret-shared
elements.

#### Multiplication

In
1991, Donald Beaver [2] observed the following: suppose we want to
compute $\langle x y \rangle$ given some $\langle x \rangle$ and
$\langle y \rangle$, and we already have three secret-shared values,
called a ‘triple’, $\langle a \rangle$, $\langle b \rangle$ and $\langle
c \rangle$ such that $c = a b$. Then note that if each party broadcasts
$x_i-a_i$ and $y_i - b_i$, then each party $P_i$ can compute $x-a$ and
$y-b$ (so these values are publicly known), and hence compute
\[ z_i=c_i + (x-a) b_i + (y-b) a_i + (x-a)(y-b) \]
Now observe that if we add all of these up, we get
\[\sum_i z_i = c + (x-a)b + (y-b)a + (x-a)(y-b) = xy\]
and so we have a secret sharing $\langle z \rangle$ of $xy$.

The
upshot is that if we have lots of triples, then we can perform many
multiplications on secret-shared data and hence we can compute any
arithmetic circuit. (Note that a triple cannot be reused because this
would reveal information about the secrets we are trying to multiply -
i.e. since $x-a$ and $y-b$ are made public in the process above)

Importantly,
observe that not only do these triples not depend on the input
secret-shared values they are used to multiply, they are also completely
independent of the circuit to be evaluated. This means that we can
generate these triples at any point prior to evaluating the circuit. The
values of $a$, $b$ and $c$ are not known by any parties when generated -
each party only knows a share of each of 'some values' for which they
are told this relation holds.

Combining the above, we have now established roughly how SPDZ evaluates an arithmetic circuit.

*: In the final part, we will look at what makes SDPZ different from other MPC protocols which achieve the same thing.*

**Next time**#### References

[1] B. Applebaum, Y. Ishai, and E. Kushilevitz. How to garble arithmetic circuits. 52nd FOCS, pp120–129. IEEE Computer Society Press, 2011

[2] D. Beaver. Efficient Multiparty Protocols using Circuit Randomisation. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pp420-432, Springer, 2012.

[3] R. Bendlin, I. Damgard, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, pp169-188, 2011.

[4] I. Damgard, M. Keller, E. Larraia, V. Pastro, P. Scholl, N. P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits.
In ESORICS (2013), J. Crampton, S. Jajodia, and K. Mayes, Eds., vol.
8134 of Lecture Notes in Computer Science, Springer, pp. 1–18.

[5] I. Damgard, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology – CRYPTO 2012, volume 7417 of LNCS, pp643–662. Springer, 2012.

[6] I. Damgard and S. Zakarias. Constant-overhead secure computation of

boolean circuits using preprocessing. In TCC, pp621-641, 2013.

[7] M. Keller and E. Orsini and P. Scholl. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. Cryptology ePrint Archive, Report 2016/505, 2016.

[8] J. Buus Nielsen, P. Nordholt, C. Orlandi, and S. Burra. A new approach to practical active-secure two-party computation.
In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in
Cryptology CRYPTO 2012, volume 7417 of Lecture Notes in Computer
Science, pp681-700. Springer Berlin Heidelberg, 2012.

[9] A. Shamir. How to Share a Secret. In Communications of the ACM, Volume 22 Issue 11, Nov. 1979, pp612-613.

[10] A. Yao. How to generate and exchange secrets. In SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp162–167. IEEE, 1986.

## No comments:

## Post a Comment