Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution

Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution

Yan Huang, Jonathan Katz, David Evans
S&P 2012 [pdf] [bibtex]

Mohassel and Franklin MF06 introduced the dual-execution approach for 2PC. The idea is for the parties to execute two instances of Yao's protocol, with the parties taking opposite roles in the two instances. Then they run an auxiliary protocol to test the equality of their outputs. This protocol is secure against malicious adversaries but leaks a single (arbitrary, adversarially chosen) bit: an adversary can send a corrupt garbled circuit and check its output against a string of its choice using the final equality test.

This work provides a full formal treatment of the 1-bit-leaked security model, and a proof of security for the dual-execution protocol within this model. A highly efficient secure equality-test protocol is also provided.

Variants of dual-execution are also discussed, which further restrict the adversary's ability to cheat (e.g., adversary learns the final output only if not caught cheating in the equality-test).

Categories:

SecurityModels