In this part, we consider what it is that makes SPDZ SDPZ.

### SPDZ MPC

Using
the term SPDZ is perhaps a little misleading. There are actually a few
protocols which we call SPDZ because they are really just improvements
on the original. As the online phase of SPDZ is already ‘pretty good’,
optimisations to the protocol normally involve improving the offline
phase.

In
what follows, we talk about the methods used in SPDZ for preprocessing
(generating the triples) and then explain some improvements that have
been made.

#### Original SPDZ

Here we will outline some of the methods in the original SPDZ protocol, as in [5].

*Preprocessing*

In
the first SPDZ paper, the authors show how to use somewhat homomorphic
encryption (SHE) to generate the triples. This is a (pretty expensive)
public key cryptosystem in which the encryption operation is ring
homomorphic - that is,
\[\textsf{Enc}_{\textsf{pk}}(a)\boxplus\textsf{Enc}_{\textsf{pk}}(b)=\textsf{Enc}_{\textsf{pk}}(a+b)\]
and
\[\textsf{Enc}_{\textsf{pk}}(a)
\boxdot \textsf{Enc}_{\textsf{pk}}(b) = \textsf{Enc}_{\textsf{pk}}(a
\cdot b)\]

(For
those who know about FHE: we can do MPC with FHE, as you’d hope; however, at
the time of writing no FHE scheme which is competitive with current
secret-sharing MPC currently exists. SPDZ is what the authors call the
‘ideal use of FHE in MPC’: raw material is computed locally so that the
online computations are minimal and communication overhead is small.)

During the offline phase, we also generate lots of random values which are used by the parties to provide input to the circuit.

*Sacrificing*

In
order to check that the adversary has not introduced errors into the
triples, for each triple we want to use we have to ‘sacrifice’ a triple
by taking another triple from the preprocessing and checking that the
third element is the product of the first two using Beaver’s method
outlined in the previous post. Fortunately the method by which triples are generated is
very efficient.

*ZKPoPKs*

Zero-Knowledge
Proofs of Plaintext Knowledge (ZKPoPKs) are a way of ensuring parties
encrypt as they should: when encrypting in the SHE scheme, there are
conditions on the plaintext and noise that need to be met to ensure the
ciphertext is well-formed.

*MACs*

Before
any preprocessing computation takes place, the parties agree on some
MAC key $\alpha$ with which they MAC all their data and which they
secret-share amongst themselves so that no individual party knows the
MAC key.

This MAC key is used to MAC all the data in the circuit. For each secret-shared

After the circuit has been evaluated, the parties open the secret corresponding to the circuit output and also the MAC on it, and check that the MAC is correct. If an actively corrupt party cheats at any point in the circuit evaluation, the final MAC check reveals this has happened. Note that this means the parties could be computing on invalid data.

This MAC key is used to MAC all the data in the circuit. For each secret-shared

*value*, there is also a secret-shared MAC on that value.After the circuit has been evaluated, the parties open the secret corresponding to the circuit output and also the MAC on it, and check that the MAC is correct. If an actively corrupt party cheats at any point in the circuit evaluation, the final MAC check reveals this has happened. Note that this means the parties could be computing on invalid data.

In
the original paper, each party also MACked the global MAC key with a
personal MAC key. This was not needed in subsequent works.

#### Updated SPDZ: SDPZ2

While
the online phase of SPDZ was (almost) the same, in SPDZ2 [4] the
authors made significant changes to the offline phase of the original
protocol. We outline the major changes here.

They solved an open problem left by the first paper in giving a secure protocol which generated a shared SHE decryption key.

They
also offered various performance enhancements, including the
introduction of ‘squares’ and ‘bits’ in the preprocessing, which allowed
faster online computations of specific operations in the circuit.

A
major improvement was allowing MACs to be checked on data before the
end of the computation. This involved checking the MAC of a public value
that depended on the underlying data. The big advantage of this is that
the preprocessed data MACked under the same key can still be used after
this MAC check, but not in the original protocol since the check
reveals the key.

The
new protocol had covert and malicious variants, the former having
lesser parameter requirements. A covertly secure protocol ensures the
adversary wins with probability at most $1/n$ for some $n \in
\mathbb{N}$. The reason for this was that it was believed more closely
to match the real-world situation.

#### New SPDZ: MASCOT

The
most recent improvements to the SPDZ protocol is a work known as MASCOT
[3]. As with SPDZ2, the online phase of SPDZ was left as it was; this
paper improves on the offline phase, showing how to use oblivious
transfer (OT) to achieve much faster preprocessed data than by using
SHE. It is authored by Bristol’s own Marcel, Emmanuela and Peter, and
appeared at CCS last week.

(Oblivious
transfer is a process in which one party inputs two strings and a
second party chooses exactly one; this is done in such a way that the
first party doesn’t know which string the second chose, and the second
does not learn anything about the string it didn’t choose.)

The
authors of MASCOT note that the heavy machinery of public-key
cryptography required in the original SPDZ paper to generate the
preprocessing (namely, the use of SHE) prevents the communication from
being a bottleneck since the local computation takes so long.

The protocol is actively secure and performs significantly faster than previous SPDZ2 implementations, with much lower communication overhead.

The protocol is actively secure and performs significantly faster than previous SPDZ2 implementations, with much lower communication overhead.

#### The Future of SPDZ

MASCOT has only just been released, and there are already whispers of a new paper. Watch this space...

#### 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