@article {15108, title = {Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution}, journal = {IEEE Symposium on Security and Privacy}, year = {2012}, month = {2012///}, abstract = {Known protocols for secure two-party computa-tion that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party{\textquoteright}s input. Correctness of the honest party{\textquoteright}s output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some heuristic enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing stronger security guarantees. }, author = {Huang,Y. and Katz, Jonathan and Evans,D.} }