Efficiency Tradeoffs for Malicious Two-Party Computation

Efficiency Tradeoffs for Malicious Two-Party Computation

Payman Mohassel, Matthew Franklin
PKC 2006 [pdf] [bibtex]

This paper is best known for its introduction of the dual-execution technique for 2PC. Roughly speaking, dual execution 2PC of a functionality ⚠ {$f$} works as follows:

  • The parties run an instance of Yao's semi-honest protocol, with Alice as sender and Bob as receiver. The result is for Bob to learn the output of ⚠ {$f$} as well as the corresponding output wire labels, which constitute a kind of "proof" of this output.
  • The parties run another instance of Yao's protocol, with the roles reversed. Now Alice learns the output of ⚠ {$f$} and corresponding wire labels.
  • Each party has a garbled output of one of the executions, and was the sender in the other execution, so can predict what the other party's output wire labels should have been. Hence, both parties can determine the "correct" output wire labels from both executions. If both parties ran the protocol honestly, they should be in agreement about these wire labels.
  • The parties perform a secure protocol to check equality of these combined output wire labels. If the equality test succeeds, both parties halt with their computed output, otherwise they abort.

A malicious adversary can (among other things) send a garbled circuit for some other function ⚠ {$g$} and use the equality test to determine whether ⚠ {$f(x,y) = g(x,y)$}. Hence, the protocol is not secure against malicious adversaries.

However, the authors claim that the protocol leaks at most one bit. More formally, they define a ⚠ {$k$}-leaked model of security, where the ideal functionality allows the adversary to learn any chosen ⚠ {$k$}-bit function applied to the honest party's input, in addition to learning the output of ⚠ {$f$}. The dual execution protocol is secure in the 1-leaked model (more details are given in HKE12).

See also:

HKE12

Other links:

PKC presentation slides (PDF)

Categories:

SecurityModels Paradigms