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

Free reduction · standard model · BGJ+18

Statement

If DDH 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. A compiler turns a three-round semi-malicious protocol whose first round is public-coin into a four-round malicious one. Its main tool is a three-round promise zero-knowledge protocol in the simultaneous-message model, which is zero knowledge only against verifiers that do not abort, and its simulator treats aborting and non-aborting adversaries separately — BGJ+18.

Notes

• Polynomially hard QR 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.
• Earlier, polynomially hard DDH gave five rounds, and four rounds needed one-way permutations together with sub-exponentially hard DDH — ACJ17.
• Four-round OT also suffices (four-round OT ⇒ four-round MPC) — CCG+20.