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

By Yan Huang, Jonathan Katz, David E. Evans. 2012

116 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, background): “Several other frameworks explored extensions to malicious adversaries [25], [30]–[32].”
Privacy-preserving matrix factorization (2013, background): “There are presently many frameworks that implement Yao garbled circuits [45, 23, 24, 44, 53, 25, 36].”
A Methodology for Formalizing Model-Inversion Attacks (2016, background): “On the other hand, we note that, frequently, additional information is intentionally revealed by an SMC protocol due to performance considerations (for example, revealing the centroid in privacy-preserving clustering or revealing a bit of a honest party’s input in the dualexecution SMC protocol [21]”
More efficient oblivious transfer and extensions for faster secure computation (2013, unknown): “The FastGC framework was a breakthrough result regarding the practicality of secure computation and has been used in many subsequent works, e.g., [22, 23, 25, 26, 44].”
Obliv-C: A Language for Extensible Data-Oblivious Computation (2015, methodology): “Another protocol we have implemented for Obliv-C is the dual execution variant of Yao’s protocol [21, 33].”