More efficient oblivious transfer extensions. (English) Zbl 1377.94030

Summary: 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 protocols is becoming more evident. OT extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Y. Ishai et al. [Crypto 2003, Lect. Notes Comput. Sci. 2729, 145–161 (2003; Zbl 1122.94422)] presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, J. B. Nielsen et al. [Crypto 2012, Lect. Notes Comput. Sci. 7417, 681–700 (2012; Zbl 1296.94134)] presented an efficient OT extension protocol for the setting of malicious adversaries that is secure in a random oracle model. In this work, we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich-Micali-Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.


94A60 Cryptography
Full Text: DOI Link


[1] Y. Aumann, Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries, in Journal of Cryptology, vol. 23(2), (Springer, 2010) pp. 281-343 · Zbl 1181.94091
[2] G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More efficient oblivious transfer and extensions for faster secure computation, in ACM Computer and Communications Security (CCS’13), pp. 535-548. ACM, 2013. Code: http://encrypto.de/code/OTExtension
[3] G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More efficient oblivious transfer extensions with security for malicious adversaries, in Advances in Cryptology—EUROCRYPT’15, vol. 9056 of LNCS, (Springer, 2015) pp. 673-701. Full version: http://eprint.iacr.org/2015/061 · Zbl 1370.94481
[4] J. Bringer, H. Chabanne, A. Patey. SHADE: secure hamming distance computation from oblivious transfer, in Financial Cryptography and Data Security (FC’13), vol. 7862 of LNCS, (Springer, 2013), pp. 164-176
[5] D. Beaver. Efficient multiparty protocols using circuit randomization, in Advances in cryptology—-CRYPTO’91, vol. 576 of LNCS, (Springer, 1991), pp. 420-432 · Zbl 0789.68061
[6] D. Beaver. Correlated pseudorandomness and the complexity of private computations, in Symposium on the theory of computing (STOC’96), (ACM, 1996), pp. 479-488 · Zbl 0917.94012
[7] M. Bellare, V. Hoang, S. Keelveedhi, P. Rogaway. Efficient garbling from a fixed-key blockcipher, on IEEE Symposium on Security and Privacy (S&P’13), (IEEE, 2013), pp. 478-492 · Zbl 0957.68040
[8] S. S. Burra, E. Larraia, J. B. Nielsen, P. S. Nordholt, C. Orlandi, E. Orsini, P. Scholl, and N. P. Smart. High performance multi-party computation for binary circuits based on oblivious transfer. Cryptology ePrint Archive, Report 2015/472, 2015. Online: http://eprint.iacr.org/2015/472.
[9] A. Ben-David, N. Nisan, B. Pinkas. FairplayMP: a system for secure multi-party computation, in ACM Computer and Communications Security (CCS’08), (ACM, 2008) pp. 257-266
[10] Canetti, R, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13, 143-202, (2000) · Zbl 0957.68040
[11] S.G. Choi, K.-W. Hwang, J. Katz, T. Malkin, 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), vol. 7178 of LNCS, (Springer, 2012) pp. 416-432 · Zbl 1292.94047
[12] T. Chou, C. Orlandi. The simplest protocol for oblivious transfer, in Progress in Cryptology—LATINCRYPT’15, vol. 9230 of LNCS, (Springer, 2015), pp. 40-58 · Zbl 1370.94499
[13] C. Dong, L. Chen, Z. Wen. When private set intersection meets big data: an efficient and scalable protocol, in ACM Computer and Communications Security (CCS’13), (ACM, 2013), pp. 789-800
[14] I. Damgård, R. Lauritsen, T. Toft. An empirical study and some improvements of the MiniMac protocol for secure computation, in Security and Cryptography for Networks (SCN’14), vol. 8642 of LNCS, (Springer, 2014), pp. 398-415 · Zbl 1404.94059
[15] D. Demmler, T. Schneider, M. Zohner. ABY—a framework for efficient mixed-protocol secure two-party computation, in Network and Distributed System Security (NDSS’15). The Internet Society, 2015
[16] I. Damgård, S. Zakarias. Constant-overhead secure computation of Boolean circuits using preprocessing, in Theory of cryptography conference (TCC’13), vol. 7785 of LNCS, (Springer, 2013), pp. 621-641 · Zbl 1315.94068
[17] Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, T. Toft. Privacy-preserving face recognition, in Privacy Enhancing Technologies Symposium (PETS’09), vol. 5672 of LNCS, (Springer, 2009), pp. 235-253
[18] Y. Ejgenberg, M. Farbstein, M. Levy, Y. Lindell. SCAPI: the secure computation application programming interface. Cryptology ePrint Archive, Report 2012/629, 2012. Online: http://eprint.iacr.org/2012/629
[19] S. Even, O. Goldreich, A. Lempel. A randomized protocol for signing contracts, in Communications of the ACM, vol. 28(6), (ACM, 1985), pp. 637-647 · Zbl 0538.94011
[20] J.O. Eklundh. A fast computer method for matrix transposing, in IEEE Transactions on Computers, vol. C-21(7), (IEEE, 1972), pp. 801-803 · Zbl 0238.65017
[21] K. Frikken, M. Atallah, C. Zhang. Privacy-preserving credit checking, in Electronic Commerce (EC’05), (ACM, 2005), pp. 147-154
[22] T.K. Frederiksen, M. Keller, E. Orsini, P. Scholl. A unified approach to MPC with preprocessing using OT, in Advances in Cryptology—ASIACRYPT’15, vol. 9452 of LNCS, (Springer, 2015), pp. 711-735 · Zbl 1396.94077
[23] T. K. Frederiksen, J. B. Nielsen. Fast and maliciously secure two-party computation using the GPU, in Applied Cryptography and Network Security (ACNS’13), vol. 7954 of LNCS, (Springer, 2013), pp. 339-356
[24] S.D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, Y. Vahlis. Secure two-party computation in sublinear (amortized) time, in ACM Computer and Communications Security (CCS’12), (ACM, 2012), pp. 513-524
[25] O. Goldreich, S. Micali, 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), (ACM, 1987), pp. 218-229
[26] O. Goldreich. Foundations of Cryptography, vol. 2: Basic Applications. Cambridge University Press, 2004 · Zbl 1068.94011
[27] Y. Huang, P. Chapman, D. Evans. Privacy-preserving applications on smartphones, in Hot topics in security (HotSec’11). USENIX, 2011
[28] Y. Huang, D. Evans, J. Katz. Private set intersection: Are garbled circuits better than custom protocols? in Network and Distributed System Security (NDSS’12). The Internet Society, 2012
[29] Y. Huang, D. Evans, J. Katz, L. Malka. Faster secure two-party computation using garbled circuits, in USENIX Security’11, (USENIX, 2011), pp. 539-554
[30] A. Holzer, M. Franz, S. Katzenbeisser, H. Veith. Secure two-party computations in ANSI C, in ACM Computer and Communications Security (CCS’12), (ACM, 2012) pp. 772-783
[31] D. Harnik, Y. Ishai, E. Kushilevitz, J. Buus Nielsen. OT-combiners via secure computation, in Theory of Cryptography Conference (TCC’08), vol. 4948 of LNCS, (Springer, 2008), pp. 393-411 · Zbl 1162.94366
[32] W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations, in ACM Computer and Communications Security (CCS’10), (ACM, 2010), pp. 451-462
[33] Y. Huang, L. Malka, D. Evans, J. Katz. Efficient privacy-preserving biometric identification, in Network and Distributed Security Symposium (NDSS’11). The Internet Society, 2011
[34] W. Henecka, T. Schneider. Faster secure two-party computation with less memory, in ACM Symposium on Information, Computer and Communications Security (ASIACCS’13), (ACM, 2013), pp. 437-446
[35] Y. Ishai, J. Kilian, K. Nissim, E. Petrank. Extending oblivious transfers efficiently, in Advances in Cryptology—CRYPTO’03, vol. 2729 of LNCS, (Springer, 2003), pp. 145-161 · Zbl 1122.94422
[36] Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai. Cryptography with constant computational overhead, in ACM Symposium on Theory of Computing (STOC’08), (ACM, 2008), pp. 433-442 · Zbl 1231.94050
[37] Y. Ishai, M. Prabhakaran, and A. Sahai. Founding cryptography on oblivious transfer - efficiently, in Advances in Cryptology—CRYPTO’08, vol. 5157 of LNCS, (Springer, 2008), pp. 572-591 · Zbl 1183.94037
[38] R. Impagliazzo, S. Rudich. Limits on the provable consequences of one-way permutations, in Advances in Cryptology—CRYPTO’88, vol. 403 of LNCS, (Springer, 1988), pp. 8-26 · Zbl 0718.68042
[39] F. Kerschbaum. Automatically optimizing secure computation, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 703-714
[40] V. Kolesnikov, R. Kumaresan. Improved OT extension for transferring short secrets, in Advances in Cryptology—CRYPTO’13, vol. 8043 of LNCS, (Springer, 2013) pp. 54-70 · Zbl 1316.94080
[41] M. Keller, E. Orsini, P. Scholl. Actively secure OT extension with optimal overhead, in Advances in Cryptology—CRYPTO’15, vol. 9215 of LNCS, (Springer, 2015), pp. 724-741 · Zbl 1375.94138
[42] V. Kolesnikov, T. Schneider. Improved garbled circuit: free XOR gates and applications, in International Colloquium on Automata, Languages and Programming (ICALP’08), vol. 5126 of LNCS, (Springer, 2008), pp. 486-498 · Zbl 1155.94374
[43] B. Kreuter, A. Shelat, C. Shen. Billion-gate secure computation with malicious adversaries, in USENIX Security’12, (USENIX, 2012), pp. 285-300
[44] M. Keller, P. Scholl, N.P. Smart. An architecture for practical actively secure MPC with dishonest majority, in ACM Computer and Communications Security (CCS’13), (ACM, 2013), pp. 549-560
[45] E. Larraia. Extending oblivious transfer efficiently, or - how to get active security with constant cryptographic overhead, in Progress in Cryptology- LATINCRYPT’14, vol. 8895 of LNCS, (Springer, 2014), pp. 368-386 · Zbl 1370.94524
[46] E. Larraia, E. Orsini, N.P. Smart. Dishonest majority multi-party computation for binary circuits, in Advances in Cryptology—CRYPTO’14, vol. 8617 of LNCS, (Springer, 2014), pp. 495-512 · Zbl 1335.94064
[47] L. Lovász, M.D. Plummer. Matching Theory. Akadémiai Kiadó, Budapest, 1986. Also published as vol. 121 of the North-Holland Mathematics Studies, North-Holland Publishing, Amsterdam
[48] Y. Lindell, B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer, in Theory of Cryptography Conference (TCC’11), vol. 6597 of LNCS, (Springer, 2011), pp. 329-346 · Zbl 1281.94037
[49] Y. Lindell, B. Riva. Blazing fast 2pc in the offline/online setting with security for malicious adversaries, in ACM Computer and Communications Security (CCS’15), (ACM, 2015), pp. 579-590
[50] Y. Lindell, H. Zarosim. On the feasibility of extending oblivious transfer, in Theory of Cryptography Conference (TCC’13), vol. 7785 of LNCS, (Springer, 2013), pp. 519-538 · Zbl 1315.94086
[51] L. Malka. VMCrypt—modular software architecture for scalable secure computation, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 715-724
[52] D. Malkhi, N. Nisan, B. Pinkas, Y. Sella. Fairplay—a secure two-party computation system, in USENIX Security’04, (USENIX, 2004), pp. 287-302
[53] P. MacKenzie, A. Oprea, M.K. Reiter. Automatic generation of two-party computations, in ACM Computer and Communications Security (CCS’03), (ACM, 2003), pp. 210-219
[54] J.B. Nielsen. Extending oblivious transfers efficiently—how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215, 2007. Online: http://eprint.iacr.org/2007/215
[55] NIST. NIST Special Publication 800-57, Recommendation for Key Management Part 1: General (Rev. 3). Technical report, NIST, 2012
[56] J. B. Nielsen, P.S. Nordholt, C. Orlandi, S.S. Burra. A new approach to practical active-secure two-party computation. In Advances in Cryptology - CRYPTO’12, vol. 7417 of LNCS, (Springer, 2012), pp. 681-700 · Zbl 1296.94134
[57] M. Naor, B. Pinkas. Efficient oblivious transfer protocols, in Symposium on Discrete Algorithms (SODA’01), (ACM/SIAM, 2001), pp. 448-457 · Zbl 0991.94045
[58] V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, N. Taft. Privacy-preserving ridge regression on hundreds of millions of records, in IEEE Symposium on Security and Privacy (S&P’13), (IEEE, 2013), pp. 334-348
[59] B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private set intersection using permutation-based hashing, in USENIX Security’15, (USENIX, 2015), pp. 515-530
[60] B. Pinkas, T. Schneider, M. Zohner. Faster private set intersection based on ot extension, in USENIX Security’14, (USENIX, 2014), pp. 797-812
[61] C. Peikert, V. Vaikuntanathan, B. Waters. A framework for efficient and composable oblivious transfer, in Advances in Cryptology—CRYPTO’08, vol. 5157 of LNCS, (Springer, 2008) pp. 554-571 · Zbl 1183.94046
[62] M.O. Rabin. How to exchange secrets with oblivious transfer, TR-81 edition, 1981. Aiken Computation Lab, Harvard University.
[63] A. Schröpfer, F. Kerschbaum. Demo: secure computation in JavaScript, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 849-852
[64] T. Schneider, M. Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits, in Financial Cryptography and Data Security (FC’13), vol. 7859 of LNCS, (Springer, 2013), pp. 275-292
[65] A.C. Yao. How to generate and exchange secrets, in Foundations of Computer Science (FOCS’86), (IEEE, 1986), pp. 162-167
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.