Doubly enhanced certified TDP ⇒ Five-round 2PC (Katz–Ostrovsky)

Free reduction · standard model · KO04

Statement

If certified trapdoor permutations exist, every two-party functionality, possibly randomized and with a separate output for each party, has a five-round plain-model protocol, one party sending per round, that is secure with abort against a malicious adversary corrupting either party and has a black-box simulator running in expected polynomial time (five-round 2PC) — KO04. A doubly enhanced certified trapdoor permutation is a certified one.

Notes

• The protocols may instead be based on homomorphic encryption with additional properties, which DDH implies; certified trapdoor permutations follow from RSA with large public exponents — KO04.
• Five rounds are optimal: unconditionally, no four-round protocol with one party sending per round securely computes the coin-tossing functionality for a super-logarithmic number of coins with a black-box proof of security — KO04.
• With black-box use of the primitive, four rounds suffice when one party receives output, from enhanced trapdoor permutations (enhanced TDP ⇒ 2PC with expected-time simulation) — ORS15.
• With a simultaneous-message channel, four rounds suffice for 2PC from trapdoor permutations — COSV17.