TY - JOUR T1 - Faster secure two-party computation using garbled circuits JF - USENIX Security Symposium Y1 - 2011 A1 - Huang,Y. A1 - Evans,D. A1 - Katz, Jonathan A1 - Malka,L. AB - Secure two-party computation enables two parties toevaluate a function cooperatively without revealing to ei- ther 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 in- efficiency. We demonstrate several techniques for im- proving the running time and memory requirements of the garbled-circuit technique, resulting in an implemen- tation 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 cir- cuits with over 109 gates at a rate of roughly 10 µs per garbled gate, and showing order-of-magnitude improve- ments over the best previous privacy-preserving proto- cols for computing Hamming distance, Levenshtein dis- tance, Smith-Waterman genome alignment, and AES. ER -