Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution
Authors:
- Yan HuangYHYan Huang
- Jonathan KatzJKJonathan Katz
- David EvansDEDavid Evans
Open Access
- 1 May 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10816011,p. 272-284
Abstract
Known protocols for secure two-party computation 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's input. Correctness of the honest party'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 dramatically stronger security guarantees.Keywords
This publication has 15 references indexed in Scilit:
- The IPS Compiler: Optimizations, Variants and Concrete EfficiencyLecture Notes in Computer Science, 2011
- Two-Output Secure Computation with Malicious Adversaries2011
- TASTY2010
- LEGO for Two-Party Secure Computation2009
- A Proof of Security of Yao’s Protocol for Two-Party ComputationJournal of Cryptology, 2008
- Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries2008
- OT-Combiners via Secure ComputationLecture Notes in Computer Science, 2008
- Direct Minimum-Knowledge Computations (Extended Abstract)1988
- How to generate and exchange secrets1986
- How to exchange (secret) keysACM Transactions on Computer Systems, 1983