Gilad Asharov
Yehuda Lindell
Thomas Schneider
ABSTRACT
Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.
In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.
- D. Beaver. Efficient multiparty protocols using circuit randomization. In Advances in Cryptology -- CRYPTO'91, volume 576 of LNCS, pages 420--432. Springer, 1991. Google Scholar
Digital Library
- D. Beaver. Correlated pseudorandomness and the complexity of private computations. In Symposium on Theory of Computing (STOC'96), pages 479--488. ACM, 1996. Google ScholarDigital Library
- M. Bellare, S. Goldwasser, and D. Micciancio. "pseudo-random" number generation within cryptographic algorithms: The DDS case. In Advances in Cryptology -- CRYPTO'97, volume 1294 of LNCS, pages 277--291. Springer, 1997. Google ScholarDigital Library
- M. Bellare, V. Hoang, S. Keelveedhi, and P. Rogaway. Efficient garbling from a fixed-key blockcipher. In Symposium on Security and Privacy, pages 478--492. IEEE, 2013. Google ScholarDigital Library
- A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP: a system for secure multi-party computation. In Computer and Communications Security (CCS'08), pages 257--266. ACM, 2008. Google ScholarDigital Library
- J. Boyar and R. Peralta. The exact multiplicative complexity of the Hamming weight function. Electronic Colloquium on Computational Complexity (ECCC'05), (049), 2005.Google Scholar
- R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143--202, 2000.Google ScholarDigital Library
- S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces. In Cryptographers' Track at the RSA Conference (CT-RSA'12), volume 7178 of LNCS, pages 416--432. Springer, 2012. Google ScholarDigital Library
- E. De Cristofaro and G. Tsudik. Practical private set intersection protocols with linear complexity. In Financial Cryptography and Data Security (FC'10), volume 6052 of LNCS, pages 143--159. Springer, 2010. Google ScholarDigital Library
- J. O. Eklundh. A fast computer method for matrix transposing. IEEE Transactions on Computers, C-21(7):801--803, 1972. Google ScholarDigital Library
- Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft. Privacy-preserving face recognition. In Privacy Enhancing Technologies Symposium (PETS'09), volume 5672 of LNCS, pages 235--253. Springer, 2009. Google ScholarDigital Library
- S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communmunications of the ACM, 28(6):637--647, 1985. Google ScholarDigital Library
- K. Frikken, M. Atallah, and C. Zhang. Privacy-preserving credit checking. In Electronic Commerce (EC'05), pages 147--154. ACM, 2005. Google ScholarDigital Library
- O. Goldreich. Foundations of Cryptography, volume 2: Basic Applications. Cambridge University Press, 2004. Google ScholarDigital Library
- O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Symposium on Theory of Computing (STOC'87), pages 218--229. ACM, 1987. Google ScholarDigital Library
- S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis. Secure two-party computation in sublinear (amortized) time. In Computer and Communications Security (CCS'12), pages 513--524. ACM, 2012. Google ScholarDigital Library
- D. Harnik, Y. Ishai, E. Kushilevitz, and J. B. Nielsen. OT-combiners via secure computation. In Theory of Cryptography (TCC'08), volume 4948 of LNCS, pages 393--411. Springer, 2008. Google ScholarDigital Library
- J. Håstad and A. Shamir. The cryptographic security of truncated linearly related variables. In Symposium on Theory of Computing (STOC'85), pages 356--362. ACM, 1985. Google ScholarDigital Library
- W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In Computer and Communications Security (CCS'10), pages 451--462. ACM, 2010. Google ScholarDigital Library
- W. Henecka and T. Schneider. Faster secure two-party computation with less memory. In ACM Symposium on Information, Computer and Communications Security (ASIACCS'13), pages 437--446. ACM, 2013. Google ScholarDigital Library
- A. Holzer, M. Franz, S. Katzenbeisser, and H. Veith. Secure two-party computations in ANSI C. In Computer and Communications Security (CCS'12), pages 772--783. ACM, 2012. Google ScholarDigital Library
- Y. Huang, P. Chapman, and D. Evans. Privacy-preserving applications on smartphones. In Hot topics in security (HotSec'11). USENIX, 2011. Google ScholarDigital Library
- Y. Huang, D. Evans, and J. Katz. Private set intersection: Are garbled circuits better than custom protocols? In Network and Distributed Security Symposium (NDSS'12). The Internet Society, 2012.Google Scholar
- Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In Security Symposium. USENIX, 2011. Google ScholarDigital Library
- Y. Huang, J. Katz, and D. Evans. Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution. In Symposium on Security and Privacy, pages 272--284. IEEE, 2012. Google ScholarDigital Library
- Y. Huang, L. Malka, D. Evans, and J. Katz. Efficient privacy-preserving biometric identification. In Network and Distributed Security Symposium (NDSS'11). The Internet Society, 2011.Google Scholar
- Intelligence Advanced Research Projects Activity (IARPA). Security and Privacy Assurance Research (SPAR) Program, 2010.Google Scholar
- Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology -- CRYPTO'03, volume 2729 of LNCS, pages 145--161. Springer, 2003.Google Scholar
- A. Jarrous and B. Pinkas. Secure hamming distance based computation and its applications. In Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 107--124. Springer, 2009. Google ScholarDigital Library
- F. Kerschbaum. Automatically optimizing secure computation. In Computer and Communications Security (CCS'11), pages 703--714. ACM, 2011. Google ScholarDigital Library
- V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In Cryptology And Network Security (CANS'09), volume 5888 of LNCS, pages 1--20. Springer, 2009. Google ScholarDigital Library
- V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In International Colloquium on Automata, Languages and Programming (ICALP'08), volume 5126 of LNCS, pages 486--498. Springer, 2008. Google ScholarDigital Library
- H. Krawczyk. Cryptographic extraction and key derivation: The HKDF scheme. In Advances in Cryptology -- CRYPTO'10, volume 6223 of LNCS, pages 631--648. Springer, 2010. Google ScholarDigital Library
- B. Kreuter, A. Shelat, and C.-H. Shen. Billion-gate secure computation with malicious adversaries. In Security Symposium. USENIX, 2012. Google ScholarDigital Library
- P. MacKenzie, A. Oprea, and M. K. Reiter. Automatic generation of two-party computations. In Computer and Communications Security (CCS'03), pages 210--219. ACM, 2003. Google ScholarDigital Library
- L. Malka. VMCrypt - modular software architecture for scalable secure computation. In Computer and Communications Security (CCS'11), pages 715--724. ACM, 2011. Google ScholarDigital Library
- D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -- a secure two-party computation system. In Security Symposium, pages 287--302. USENIX, 2004. Google ScholarDigital Library
- A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. Google ScholarDigital Library
- S. Nagaraja, P. Mittal, C.-Y. Hong, M. Caesar, and N. Borisov. Botgrep: Finding P2P bots with structured graph analysis. In Security Symposium, pages 95--110. USENIX, 2010. Google ScholarDigital Library
- M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In ACM-SIAM Symposium On Discrete Algorithms, SODA'01, pages 448--457. Society for Industrial and Applied Mathematics, 2001. Google ScholarDigital Library
- A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. Location privacy via private proximity testing. In Network and Distributed Security Symposium (NDSS'11). The Internet Society, 2011.Google Scholar
- J. B. Nielsen. Extending oblivious transfers efficiently - how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215, 2007.Google Scholar
- J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra. A new approach to practical active-secure two-party computation. In Advances in Cryptology -- CRYPTO'12, volume 7417 of LNCS, pages 681--700. Springer, 2012.Google Scholar
- V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. Privacy-preserving ridge regression on hundreds of millions of records. In Symposium on Security and Privacy, pages 334--348. IEEE, 2013. Google ScholarDigital Library
- NIST. NIST Special Publication 800--57, Recommendation for Key Management Part 1: General (Rev. 3). Technical report, 2012.Google Scholar
- M. Osadchy, B. Pinkas, A. Jarrous, and B. Moskovich. SCiFI - a system for secure face identification. In Symposium on Security and Privacy, pages 239--254. IEEE, 2010. Google ScholarDigital Library
- B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. Secure two-party computation is practical. In Advances in Cryptology -- ASIACRYPT'09, volume 5912 of LNCS, pages 250--267. Springer, 2009. Google ScholarDigital Library
- M. O. Rabin. How to exchange secrets with oblivious transfer, TR-81 edition, 1981. Aiken Computation Lab, Harvard University.Google Scholar
- T. Schneider and M. Zohner. GMW vs. Yao -- Efficient secure two-party computation with low depth circuits. In Financial Cryptography and Data Security (FC'13), LNCS. Springer, 2013.Google Scholar
- A. Schröpfer and F. Kerschbaum. Demo: secure computation in JavaScript. In Computer and Communications Security (CCS'11), pages 849--852. ACM, 2011. Google ScholarDigital Library
- A. C. Yao. How to generate and exchange secrets. In Foundations of Computer Science (FOCS'86), pages 162--167. IEEE, 1986. Google ScholarDigital Library
Index Terms
- More efficient oblivious transfer and extensions for faster secure computation
Recommendations
More Efficient Oblivious Transfer Extensions
Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT ...
Improvements to Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityMotivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
Comments