| Abstract | 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.
|
