DCR ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai)

Free reduction · standard model · BGJ+18

Statement

If the $N$-th residuosity assumption holds for polynomial-time adversaries, that is, DCR: for an RSA modulus $n$, $n$-th powers modulo $n^2$ are indistinguishable from uniform elements of ${\mathbb{Z}}_{n^2}^{\ast }$ — Pai99 — then every functionality has a four-round protocol in the plain model, with simultaneous messages over the broadcast channel, that is secure with abort against a malicious adversary corrupting any number of parties and has a black-box simulator running in expected polynomial time (four-round MPC) — BGJ+18. The protocol is the compiler of DDH ⇒ four-round MPC, which turns a three-round semi-malicious protocol whose first round is public-coin into a four-round malicious one, with its components instantiated under $N$-th residuosity — BGJ+18.

Notes

• Polynomially hard DDH or QR gives the same result — BGJ+18.
• Four rounds are optimal: with a black-box proof of security, MPC in the plain model needs at least four rounds — GMPP16.