Fast Secure Computation Using Garbled Circuits

Our Java-based framework and library enable programmers to build efficient and scalable privacy-preserving applications using Yao's garbled circuit techniques.

Software

This software package is made freely available under the MIT license.

Papers

This paper describes the framework and illustrates our approach with several applications:

Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster Secure Two-Party Computation Using Garbled Circuits, 20th USENIX Security Symposium, San Francisco, CA. 8-12 August 2011. [PDF, 16 pages]

Abstract. Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function's output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 109 gates at a rate of roughly 10 microseconds per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES.

This paper describes a way to use the framework to provide security assurances much stronger than the semi-honest model:

Yan Huang, Jonathan Katz, and David Evans. Quid-Pro-Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution. In 33rd IEEE Symposium on Security and Privacy ("Oakland" 2012), San Francisco, CA. 20-23 May 2012. [PDF, 13 pages]

This paper describes using the framework to perform private set intersection:

Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?. In 19^th Network and Distributed Security Symposium (NDSS 2012), San Diego, CA. 5-8 February 2012. [PDF, 15 pages]

This paper describes adapting the framework to support privacy-preserving applications on mobile devices:

Yan Huang, Peter Chapman, and David Evans. Privacy-Preserving Applications on Smartphones. 6th USENIX Workshop on Hot Topics in Security (HotSec 2011), San Francisco. 9 August 2011. Paper: [PDF, 6 pages]. Talk slides: [PDF] (Peter Chapman).

People