Faster Secure Two-Party Computation Using Garbled Circuits

Conference Paper
Authors:Huang, Yan, Computer ScienceUniversity of Virginia Evans, David, Computer ScienceUniversity of Virginia Katz, Jonathan, Computer ScienceUniversity of Maryland Malka, LiorIntel
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.

Keywords:
secure computation, privacy-preserving applications, garbled circuits, security, privacy
Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Huang, Yan, David Evans, Jonathan Katz, and Lior Malka. "Faster Secure Two-Party Computation Using Garbled Circuits." 20th USENIX Security Symposium, San Francisco, CA. 2011.

Published Date:
2011
Notes:

See http://mightbeevil.com/framework/ for more information.