MPC Techniques Series, Part 9: SPDZ
By Claudio Orlandi, Associate Professor and Chief Cryptographic Protocol Designer at Partisia
This post will outline some of the key ideas behind one of the most celebrated protocols for MPC, the SPDZ protocol.
The SPDZ protocol, pronounced SPeeDz, will soon be turning 10 years old and gets its name from a cheeky permutation of the initials of its authors: Damgård, Pastro, Smart, and Zakarias. Today, when people refer to SPDZ they don’t only refer to the original protocol, but also to its most recent versions with improved techniques and optimizations. Some publicly available implementations of SPDZ include: FRESCO, MP-SPDZ, SCALE-MAMBA.
Regardless of its variants, the main characteristics of SPDZ are the following:
- It allows any number of parties, call it n, to perform MPC.
- It tolerates up to n-1 corrupted parties.
- It provides active security e.g. it is secure even if the corrupt parties misbehave in the protocol (as explained in a previous post here).
- In its original version it allows the evaluation of arithmetic circuits e.g., circuits where all operations are performed over the integer modulo a large prime. However other variants exist to deal with Boolean circuits, finite fields, arithmetic modulo power of 2s, etc.
- It is composed of two phases: a somewhat slower pre-processing phase and an incredibly fast online phase. The pre-processing phase produces the “fuel”, which is then used during the online phase. This “fuel” is composed of random multiplication triples (or Beaver Triples as explained in an earlier post here), and is therefore independent of both the function that has to be computed and the secret inputs of the parties. Therefore, the bulk of the time used to run SPDZ can be done well in advance. When the inputs are available, the online phase of the computation can be performed very quickly, thus providing low-latency MPC.
There are several variants of the preprocessing phase for the SPDZ family of protocols, based either on homomorphic encryption, oblivious transfer, or other “public-key” type of cryptographic tools. In any case, the preprocessing phase uses the properties of its underlying tools to perform multiplications of random values chosen by the parties, and ensures that these values are consistent and correct according to the protocol specification using a combination of sanity checks, cut-and-choose, zero-knowledge protocols, etc. The details of the pre-processing phase are too technical to be covered in this blog post format but if you are interested there are plenty of resources online, for instance Ivan gave a great tutorial at one of the Bar-Ilan Winter Schools.
However, I believe that the ideas underlying the protocol used for the online phase are simple enough to be explained in a blog post, so here we go.
SPDZ uses additive secret sharing, which means that every secret value x is represented by having every party Pi know a random value xi such that x=x1+…+xn. Eventually by computing on these secret values the output of the computation z is obtained (in secret shared form). At this point, the parties can learn this output z by sending their shares zi to each other such that everyone can recompute z. However if some of the participants are dishonest, they can simply lie about their shares, leading to an incorrect result.
The SPDZ protocol “augments” the representation of secret shared values by adding some authentication mechanisms to the secret sharing format. You are probably familiar with digital signature schemes (used to authenticate transactions in cryptocurrencies), or even their symmetric-key counterpart “message authentication codes” or MAC. A MAC is a way of authenticating a value so that it is infeasible to lie about a value unless you know the key which was used to produce the MAC.
Using a MAC, SPDZ solves the problem of “lying parties” by giving everyone, on top of their share zi, also a share mi of a MAC m and a share ki of a key k, such that the sum of the mi’s is equal to m, the sum of the ki’s is equal to k, and m=MAC(k,z). When the value z has to be reconstructed, everybody sends their shares of (m, k, z) to everyone else. Now the parties can reconstruct the three values and also check for correctness. There are some extra countermeasures to be implemented to deal with so-called “rushing adversaries’’ but for the sake of simplicity let’s assume that the parties exchange their shares simultaneously.
This sounds of course great, but who should compute these MACs and distribute them to the parties? And moreover, remember that additive secret sharing has the convenient property that it is possible to compute additions of two secret-shared values without any interaction between the parties due to the commutative property of sum. How can this property be preserved once we add the MACs to the secret shared representation?
The answer to both of the above questions lies in the exact kind of MAC used in SPDZ. This MAC is both incredibly simple and effective. A MAC m on a value x under key k is simply defined as
m=k*x mod p
where p is some large-ish prime number (something like 60–80 bits would suffice). Remember that both the MAC m, the value x and (crucially) the key k are not known by anyone, since they are secret shared. This means that we can reuse the same key k over different secret values. So if we have two secret values x1, x2 their MACs will be computed as
m1=k*x2 mod p and m2=k*x2 mod p
Then, if each party simply adds their shares of the values and their shares of the MACs we will get a valid MAC on the resulting value since
(m1+m2)=k*(x1+x2) mod p
Therefore, to achieve active security during the online phase all we have to do is to make sure that the pre-processing phase produces random Beaver multiplication triples together with MACs on all the values under some random key k. Then, every time we do some computation on some values the MACs will “follow” the computation thanks to their homomorphic properties. Finally, note that computing the MAC is “just” computing a multiplication between secret values. Therefore, whatever technology we were using in the pre-processing phase to produce the Beaver multiplication triples can be also used to produce the MACs.
About the author:
Claudio is Associate Professor in Computer Science at Aarhus University and co-founder of Partisia Infrastructure. He is a leading researcher on secure multiparty computation and zero-knowledge protocols. Claudio has a broad interest in the theory and practice of cryptographic protocols, with a focus on efficient constructions of advanced cryptographic primitives, threshold cryptography, privacy-preserving technologies, theory and practice of cryptographic protocols.
