Semi-homomorphic encryption ⇒ MPC with preprocessing (BDOZ)

Non-standard model · BDOZ11

Statement

In the registered public-key model, in which all parties’ public keys are known and corrupted parties know their own secret keys, the preprocessing phase of MPC with preprocessing can be instantiated from semi-homomorphic encryption, a relaxed notion BDOZ11 introduce. The resulting protocol for arithmetic circuits is UC-secure against an active adversary corrupting up to $n-1$ of the $n$ parties, and its online phase uses only additive secret sharing and information-theoretic MACs — BDOZ11.

Sketch

The online phase follows Beaver’s circuit randomization, consuming one multiplication triple per multiplication gate, with every party’s share authenticated towards every other party by a pairwise information-theoretic MAC. The preprocessing produces the triples and the MACs from two-party products of private values: $P_i$ sends ${\mathsf{Enc}}_{{\mathsf{pk}}_i}(a)$, $P_j$ homomorphically computes ${\mathsf{Enc}}_{{\mathsf{pk}}_i}(ab+r)$ for its value $b$ and a random mask $r$, and the parties keep $ab+r$ and $-r$ as additive shares of $ab$, while zero-knowledge proofs of plaintext knowledge and of correct multiplication enforce active security.

Notes

• The pairwise MACs make the total computation and communication of the online phase quadratic in $n$; the SPDZ protocol replaces them by one global MAC key and makes both linear in $n$ — DPSZ12.
• The instantiation from somewhat homomorphic encryption is SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ) — DPSZ12.