Ideal OT + PRG ⇒ UC MPC (IPS)

Standard model · IPS08

Statement

In the OT-hybrid model (ideal OT), given a PRG used only as a black box, every functionality has a computationally UC-secure protocol with a constant number of rounds against a static malicious adversary corrupting any number of parties (UC MPC). For three or more parties these are the first constant-round protocols that use cryptographic primitives only as black boxes, and they avoid zero-knowledge proofs. The compiler combines a protocol secure with an honest majority with a protocol secure against semi-honest parties without an honest majority — IPS08.

Notes

• Efficiency: constant rounds — IPS08.
• The same compiler gives, in the OT-hybrid model, statistically UC-secure 2PC with communication $O(s)+\mathrm{poly}(\lambda ,d,\log s)$ and $O(d)$ rounds for a circuit of size $s$ and depth $d$, which extends to any constant number of parties, and malicious OT extension with constant amortized communication overhead — IPS08.
• A protocol that UC-realizes OT can replace the ideal calls, by the composition theorem — Can01; without any setup UC MPC is impossible (no UC MPC from authenticated channels) — CKL03.