LWE + NIZK ⇒ Two-round MPC in the CRS model (Mukherjee–Wichs)

Free reduction · CRS model · MW16

Statement

If LWE is hard with sub-exponential modulus-to-noise ratio and NIZK arguments for NP exist, then in the common random string model every functionality has a two-round protocol secure against malicious adversaries corrupting any number of parties (two-round MPC). Each party broadcasts an encryption of its input under its own key of a multi-key FHE scheme with one-round threshold decryption, and then broadcasts a partial decryption of the homomorphically evaluated output — MW16.

Notes

• Against semi-honest adversaries LWE alone suffices, in the same model and with the same two rounds — MW16.
• For circuits of depth $d$ the partial decryptions are smudged with noise $2^{d\lambda \log \lambda }$ times the LWE noise bound, so the modulus-to-noise ratio must exceed $2^{d\lambda \log \lambda }$ and grows with the depth — MW16.
• Efficiency: two rounds, each party broadcasting one multi-key FHE ciphertext of its input and then one partial decryption — MW16. Two rounds are optimal: from the honest parties’ messages in a one-round protocol a corrupted party can compute the output on any inputs of its own, which the ideal execution does not allow — standard.
• Three rounds from LWE and NIZK came first — AJL+12 — and two rounds were known from indistinguishability obfuscation — GGHR14.
• Two-round malicious OT in the common reference string model also suffices (two-round UC OT ⇒ two-round MPC) — GS18; DDH, QR and LWE with polynomial modulus-to-noise ratio give it — PVW08 — and so do CDH and LPN — DGHMW20.