No reduction from authenticated channels to UC MPC

Unconditional · against free reductions · CKL03

Statement

Over authenticated point-to-point channels without setup, large classes of deterministic and probabilistic two-party functionalities have no protocol that UC-realizes them against a malicious adversary statically corrupting one of the two parties, whatever computational assumption the protocol relies on. For deterministic functionalities in which both parties receive the same output, in which only one party receives output, or in which only one party has input, CKL03 characterize the functionalities that can be UC-realized — CKL03. UC MPC asks for a protocol for every functionality, $n=2$ included, so no reduction of any kind gives it from authenticated channels.

Sketch

A UC simulator for a corrupted party must extract that party’s effective input straight-line, since the environment runs the party and cannot be rewound, and without a setup the simulator holds nothing the honest party lacks. A corrupted party that runs the simulator on the honest party’s messages therefore learns the honest party’s effective input, which the functionality may hide — CKL03.

Notes

• Two-party UC commitments do not exist in the plain model, and they do exist in the common reference string model — CF01.
• Security under concurrent general composition is equivalent to a relaxed variant of UC security that differs only in the order of quantifiers, so the plain-model impossibility carries over to concurrent general composition, and it holds for non-black-box simulation too — Lin03b.
• A setup circumvents the barrier: a common reference string together with enhanced trapdoor permutations (enhanced TDP ⇒ UC MPC) — CLOS02; ideal OT together with a PRG (ideal OT + PRG ⇒ UC MPC) — IPS08; and dealt correlated randomness (correlated randomness ⇒ UC MPC) — BDOZ11.