What is SPDZ? Part 2: Circuit Evaluation

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.

In this part we discuss how we perform the additions and multiplications of shared secret values as in the SPDZ protocol.

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

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\] Additionally, one party (chosen arbitrarily) adds on the public value $(x-a)(y-b)$ to their share so that summing all the shares up, the parties get \[\sum_i z_i = c + (x-a)b + (y-b)a + (x-a)(y-b) = xy\] and so they 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.

Moreover, if these triples are generated in the offline phase at some point before the circuit evaluation, since addition, scalar multiplication and field multiplication are inexpensive in terms of communication and computation, the online phase is both highly efficient and information-theoretically secure.

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

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

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.