Efficient Secure Computation with Garbled Circuits

Yan Huang, Chih-hao Shen, David Evans, Jonathan Katz, and abhi shelat
Seventh International Conference on Information Systems Security (ICISS 2011)
(Invited Paper)
15-19 December 2011
Jadavpur University, Kolkata

Abstract

Secure two-party computation enables applications in which participants compute the output of a function that depends on their private inputs, without revealing those inputs or relying on any trusted third party. In this paper, we show the potential of building privacy-preserving applications using garbled circuits, a generic technique that until recently was believed to be too inefficient to scale to realistic problems. We present a Java-based framework that uses pipelining and circuit-level optimizations to build efficient and scalable privacy-preserving applications. Although the standard garbled circuit protocol assumes a very week, honest-but-curious adversary, techniques are available for converting such protocols to resist stronger adversaries, including fully malicious adversaries. We summarize approaches to producing malicious-resistant secure computations that reduce the costs of transforming a protocol to be secure against stronger adversaries. In addition, we summarize results on ensuring fairness, the property that either both parties receive the result or neither party does. Several open problems remain, but as theory and pragmatism advance, secure computation is approaching the point where it offers practical solutions for a wide variety of important problems.

Paper

Full paper (21 pages): [PDF (21 pages)]
Springer Copyright Form (that justifies this open posting): [PDF]

Secure Computation Project site