This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Oblivious transfer (OT) is a cryptographic primitive originally used to transfer a collection of messages from the sender to the receiver in an oblivious manner. OT extension protocol reduces expensive asymmetric operations by running a small number of OT instances first and then cheap symmetric operations. While most earlier works discussed security model or communication and computation complexity of OT in general case, we focus on concrete application scenarios, especially where the sender in the OT protocol is a database with less computation and limited interaction capability. In this paper, we propose a generic outsourced OT extension protocol ( OTex ) that outsources all the asymmetric operations of the sender to a semihonest server so as to adapt to specific scenarios above. We give OTex a standard security definition, and the proposed protocol is proven secure in the semihonest model. In OTex , the sender works on the fly and performs only symmetric operations locally. Whatever the number of rounds OT to be executed and the length of messages in OT to be sent, our protocol realizes optimal complexity. Besides, OTex can be used to construct high-level protocols, such as private membership test (PMT) and private set intersection (PSI). We believe our OTex construction may be a building block in other applications as well.
C.-C. Y. Andrew, “How to generate and exchange secrets,” in Proceedings of the 27th Annual Symposium on Foundations of Computer Science (SFCS 1986), pp. 162–167, Washington, DC, USA, October 1986.
O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game, or a completeness theorem for protocols with honest majority,” in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 307–328, Weizmann Institute of Science, Rehovot, Israel, 2019.
I. Damgård, V. Pastro, N. Smart, and S. Zakarias, “Multiparty computation from somewhat homomorphic encryption,” in Proceedings of the Annual Cryptology Conference, pp. 643–662, Santa Barbara, CA, USA, August 2012.
Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, “Extending oblivious transfers efficiently,” in Proceedings of the Annual International Cryptology Conference, pp. 145–161, Santa Barbara, CA, USA, August 2003.
V. Kolesnikov and R. Kumaresan, “Improved ot extension for transferring short secrets,” in Proceedings of the Annual Cryptology Conference, pp. 54–70, Santa Barbara, CA, USA, 2013.
S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM, vol. 28, no. 6, pp. 637–647, 1985.
G. Brassard, C. Claude, and J.-M. Robert, “All-or-nothing disclosure of secrets,” in Proceedings of the Conference on the Theory and Application of Cryptographic Techniques, pp. 234–238, Santa Barbara, CA, USA, 1986.
W.-G. Tzeng, “Efficient 1-out-n oblivious transfer schemes,” in Proceedings of the International Workshop on Public Key Cryptography, pp. 159–171, Paris, France, February 2002.
Y. Mu, J. Zhang, and V. Varadharajan, “m out of n oblivious transfer,” in Proceedings of the Australasian Conference on Information Security and Privacy, pp. 395–405, Melbourne, Australia, 2002.
C.-K. Chu and W.-G. Tzeng, “Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries,” in Proceedings of the International Workshop on Public Key Cryptography, pp. 172–183, New York, NY, USA, March 2005.
Y. Lindell, K. Nissim, and C. Orlandi, “Hiding the input-size in secure two-party computation,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, pp. 421–440, Bengaluru, India, December 2013.
C. Cho, N. Döttling, S. Garg, D. Gupta, P. Miao, and A. Polychroniadou, “Laconic oblivious transfer and its applications,” in Proceedings of the Annual International Cryptology Conference, pp. 33–65, Santa Barbara, CA, USA, 2017.
V. Kolesnikov, R. Kumaresan, M. Rosulek, and T. Ni, “Efficient batched oblivious PRF with applications to private set intersection,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 818–829, Vienna, Austria, October 2016.
V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and T. Ni, “Practical multi-party private set intersection from symmetric-key techniques,” IACR Cryptology ePrint Archive, vol. 799, p. 2017, 2017.
B. Pinkas, T. Schneider, and M. Zohner, “Scalable private set intersection based on ot extension,” ACM Transactions on Privacy and Security, vol. 21, no. 2, p. 7, 2018.
B. Pinkas, M. Rosulek, T. Ni, and A. Yanai, “Spot-light: lightweight private set intersection from sparse ot extension,” in Proceedings of the Annual International Cryptology Conference, pp. 401–431, Santa Barbara, CA, USA, August 2019.
M. Chase and P. Miao, “Private set intersection in the internet setting from lightweight oblivious PRF,” in Proceedings of the Annual International Cryptology Conference, pp. 34–63, Santa Barbara, CA, USA, August 2020.
B. Pinkas, T. Schneider, C. Weinert, and U. Wieder, “Efficient circuit-based psi via cuckoo hashing,” in Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 125–157, Darmstadt, Germany, May 2018.
M. Ciampi and C. Orlandi, “Combining private set-intersection with secure two-party computation,” in Proceedings of the International Conference on Security and Cryptography for Networks, pp. 464–482, Amalfi, Italy, September 2018.
B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based psi with linear communication,” in Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 122–153, Darmstadt, Germany, May 2019.
T. Duong, D. H. Phan, and T. Ni, Catalic: Delegated PSI Cardinality with Applications to Contact Tracing, vol. 1105, p. 2020, IACR Cryptology ePrint Archive, 2020.
M. O. Rabin, “How to exchange secrets with oblivious transfer,” IACR Cryptology ePrint Archive, vol. 187, p. 2005, 2005.
A. Y. Lindell, “Efficient fully-simulatable oblivious transfer,” in Proceedings of the Cryptographers’ Track at the RSA Conference, pp. 52–70, San Francisco, CA, USA, April 2008.
B. Zeng, C. Tartary, P. Xu, J. Jing, and X. Tang, “A Practical Framework for t-out-of-n oblivious transfer with security against covert adversaries,” IEEE Transactions on Information Forensics and Security, vol. 7, no. 2, pp. 465–479, 2012.
M. Green and S. Hohenberger, “Universally composable adaptive oblivious transfer,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, pp. 179–197, Melbourne, Australia, December 2008.
D. Beaver, “Precomputing oblivious transfer,” in Proceedings of the Annual International Cryptology Conference, pp. 97–109, Santa Barbara, CA, USA, August 1995.
D. Beaver, “Correlated pseudorandomness and the complexity of private computations,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 479–488, Philadelphia, PA, USA, May 1996.
Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan, “The relationship between public key encryption and oblivious transfer,” in Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 325–335, Redondo Beach, CA, USA, November 2000.
Y. Gertner, T. Malkin, and O. Reingold, “On the impossibility of basing trapdoor functions on trapdoor predicates,” in Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 126–135, Heraklion, Greece, 2001.
H. Carter, B. Mood, P. Traynor, and K. Butler, “Secure outsourced garbled circuit evaluation for mobile devices,” Journal of Computer Security, vol. 24, no. 2, pp. 137–180, 2016.
D. Mansy and P. Rindal, “Endemic oblivious transfer,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 309–326, London, UK, November 2019.
V. Kolesnikov, M. Rosulek, T. Ni, and X. Wang, “Scalable private set union from symmetric-key techniques,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, pp. 636–666, Kobe, Japan, December 2019.
O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, Cambridge, UK, 2009.
M. J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold, “Keyword search and oblivious pseudorandom functions,” in Proceedings of the Theory of Cryptography Conference, pp. 303–324, Cambridge, MA, USA, February 2005.
R. Pagh and F. F. Rodler, “Cuckoo hashing,” Journal of Algorithms, vol. 51, no. 2, pp. 122–144, 2004.