Abstract | ||
---|---|---|
We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (Crypto 2013) have obtained optimal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple-execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2x improvement (per execution) in communication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5x improvement) per execution for as low as 3500 executions. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-662-44381-1_26 | ADVANCES IN CRYPTOLOGY - CRYPTO 2014, PT II |
DocType | Volume | ISSN |
Journal | 8617 | 0302-9743 |
Citations | PageRank | References |
36 | 0.90 | 36 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yan Huang | 1 | 976 | 35.15 |
Jonathan Katz | 2 | 7579 | 347.97 |
Vladimir Kolesnikov | 3 | 272 | 12.09 |
Ranjit Kumaresan | 4 | 387 | 19.14 |
Alex J. Malozemoff | 5 | 158 | 8.98 |