Enhanced TDP ⇒ 2PC with expected-time simulation (Ostrovsky–Richelson–Scafuro)
Statement
If enhanced trapdoor permutations exist, every two-party functionality in which one party receives output has a four-round plain-model protocol secure with abort against a malicious adversary, with a black-box simulator running in expected polynomial time, which uses the trapdoor permutation only as a black box and is round-optimal for black-box simulation. Its building block is a four-round OT that uses any enhanced trapdoor permutation as a black box, a parallel version of which is plugged into a black-box non-interactive secure computation protocol — ORS15. A functionality in which both parties receive output reduces to one in which one party does, at the cost of one more round: that party also receives the other’s output encrypted under a one-time pad and authenticated under a one-time MAC, with keys the other party supplied as input, and forwards it. Every two-party functionality therefore has such a protocol (2PC with expected polynomial-time simulation, the notion a constant-round black-box simulator meets) — standard.
Notes
- Rounds: four when one party receives output, which is optimal for black-box simulation — ORS15. Five are necessary when both parties receive output and one party sends per round: unconditionally, four rounds do not suffice to compute coin tossing of a super-logarithmic number of coins with a black-box proof of security — KO04; the bound concerns protocols without a simultaneous-message channel — GMPP16.
- KO04’s five-round protocols are based on certified trapdoor permutations, implied by RSA with large public exponents, or on homomorphic encryption with additional properties, implied by DDH, and use the primitives’ code — KO04, ORS15.
- With a simultaneous-message channel, four rounds suffice for 2PC with black-box simulation, from trapdoor permutations secure against polynomial-time adversaries — COSV17.
- In the plain model with simultaneous messages, MPC with a black-box proof of security needs at least four rounds, already for two parties — GMPP16.