SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ)

Standard model · DPSZ12

Statement

The preprocessing phase of MPC with preprocessing can be instantiated from somewhat homomorphic encryption given a trusted key setup: SPDZ generates authenticated Beaver multiplication triples by depth-1 homomorphic evaluation under a shared key, giving a protocol secure against an active adversary corrupting up to $n-1$ of the $n$ parties, whose online phase is unconditionally secure — DPSZ12. The scheme is an extension of a scheme of Brakerski et al. that supports distributed decryption and packs many plaintexts into one ciphertext, and the proof is in a hybrid model where a key-generation functionality deals the public key and shares of the secret key to the parties before the inputs are chosen, a dealer of correlated randomness — DPSZ12.

Sketch

The parties encrypt random shares under a joint SHE public key, multiply ciphertexts homomorphically, and jointly decrypt to additively shared, MAC-authenticated triples; the online phase consumes the triples to evaluate the arithmetic circuit with no further public-key operations.

Notes

• The instantiation from semi-homomorphic encryption is Semi-homomorphic encryption ⇒ MPC with preprocessing (BDOZ) — BDOZ11.