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

Free reduction · standard model · BGJ+18

Statement

If QR is hard for polynomial-time adversaries, 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 QR — BGJ+18.

Notes

• Polynomially hard DDH or $N$-th residuosity 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.