Efficient Pairing-Free Adaptable k-out-of-n Oblivious Transfer Protocols

Khosravani, Keykhosro; Eghlidos, Taraneh; Aref, Mohammad Reza

doi:10.22042/isecure.2025.237327

Efficient Pairing-Free Adaptable k-out-of-n Oblivious Transfer Protocols

Articles in Press

Document Type : Research Article

Authors

Keykhosro Khosravani ¹

Taraneh Eghlidos ²

Mohammad Reza Aref ³

¹ Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

² Electronics Research Institute, Sharif University of Technology, Tehran, Iran

³ Information Systems and Security Lab (ISSL), Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

10.22042/isecure.2025.237327

Abstract

Oblivious Transfer (OT) is one of the fundamental building blocks in cryptography that enables various privacy-preserving applications. Constructing efficient OT schemes has been an active research area. This paper presents three efficient two-round pairing-free k-out-of-n oblivious transfer protocols with standard security. Our constructions follow the minimal communication pattern: the receiver sends k messages to the sender, who responds with n+k messages, achieving the lowest data transmission among pairing-free k-out-of-n OT schemes. Furthermore, our protocols support adaptivity and enable the sender to encrypt the n messages offline, independent of the receiver’s variables, offering significant performance advantages in one-sender-multiple-receiver scenarios. We provide security proofs under the Computational Diffie-Hellman (CDH) and RSA assumptions, without relying on the Random Oracle Model. Our protocols combine minimal communication rounds, adaptivity, offline encryption capability, and provable security, making them well-suited for privacy-preserving applications requiring efficient oblivious transfer.

Keywords

Oblivious Transfer (OT)

adaptable Oblivious Transfer

privacy-preserving

secure multiparty computation

offline precomputation

[1] Chuan Zhao, Shengnan Zhao, Minghao Zhao, Zhenxiang Chen, Chong-Zhi Gao, Hongwei Li, and Yu-an Tan. Secure multi-party computation: theory, practice and applications. Information Sciences, 476:357–372, 2019.

[2] Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable private set intersection based on ot extension. ACM Transactions on Privacy and Security (TOPS), 21(2):1–35, 2018.

[3] Daniel Morales, Isaac Agudo, and Javier Lopez. Private set intersection: A systematic literature review. Computer Science Review, 49:100567, 2023.

[4] Bo Bi, Darong Huang, Bo Mi, Zhenping Deng, and Hongyang Pan. Efficient lbs securitypreserving based on ntru oblivious transfer. Wireless Personal Communications, 108(4):2663– 2674, 2019.

[5] Michael O Rabin. How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, 2005.

[6] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl. Oblivious transfer with constant computational overhead. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 271–302. Springer, 2023.

[7] Vanessa Vitse. Simple oblivious transfer protocols compatible with supersingular isogenies. In International Conference on Cryptology in Africa, pages 56–78. Springer, 2019.

[8] Gilles Brassard, Claude Cr´epeau, and JeanMarc Robert. All-or-nothing disclosure of secrets. In Conference on the Theory and Application of Cryptographic Techniques, pages 234–238. Springer, 1986.

[9] Vijay Kumar Yadav, Nitish Andola, Shekhar Verma, and S Venkatesan. A survey of oblivious transfer protocol. ACM Computing Surveys (CSUR), 54(10s):1–37, 2022.

[10] Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In SODA, volume 1, pages 448–457, 2001.

[11] Moni Naor and Benny Pinkas. Oblivious transfer with adaptive queries. In Annual International Cryptology Conference, pages 573–590. Springer, 1999.

[12] Stanis law Jarecki and Xiaomin Liu. Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection. In Theory of Cryptography Conference, pages 577–594. Springer, 2009.

[13] Moni Naor and Benny Pinkas. Computationally secure oblivious transfer. Journal of Cryptology, 18(1):1–35, 2005.

[14] Jan Camenisch, Maria Dubovitskaya, Robert R Enderlein, and Gregory Neven. Oblivious transfer with hidden access control from attribute-based encryption. In International Conference on Security and Cryptography for Networks, pages 559–579. Springer, 2012.

[15] Yizhou Huang and Ian Goldberg. Outsourced private information retrieval. In Proceedings of the 12th ACM Workshop on Workshop on Privacy in the Electronic Society, pages 119–130, 2013.

[16] Yi Li and Wei Xu. Privpy: General and scalable privacy-preserving data mining. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1299–1307, 2019.

[17] Huijie Yang, Jian Shen, Junqing Lu, Tianqi Zhou, Xueya Xia, and Sai Ji. A privacy-preserving data transmission scheme based on oblivious transfer and blockchain technology in the smart healthcare. Security and Communication Networks, 2021(1):5781354, 2021.

[18] Jianchang Lai, Yi Mu, Fuchun Guo, Rongmao Chen, and Sha Ma. Efficient k-out-of-n oblivious transfer scheme with the ideal communication cost. Theoretical Computer Science, 714:15–26, 2018.

[19] Cheng-Kang Chu, Wen-Guey Tzeng, et al. Efficient k-out-of-n oblivious transfer schemes. J. Univers. Comput. Sci., 14(3):397–415, 2008.

[20] Cheng-Kang Chu and Wen-Guey Tzeng. Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries. In International Workshop on Public Key Cryptography, pages 172–183. Springer, 2005.

[21] Bing Zeng, Christophe Tartary, Peng Xu, Jiandu Jing, and Xueming Tang. A practical framework for t-out-of-n oblivious transfer with security against covert adversaries. IEEE Transactions on Information Forensics and Security, 7(2):465– 479, 2012.

[22] Ran Canetti, Pratik Sarkar, and Xiao Wang. Efficient and round-optimal oblivious transfer and commitment with adaptive security. In International Conference on the Theory and Application of Cryptology and Information Security, pages 277–308. Springer, 2020.

[23] Fuchun Guo, Yi Mu, and Willy Susilo. Subset membership encryption and its applications to oblivious transfer. IEEE transactions on information forensics and security, 9(7):1098–1107, 2014.

[24] Qian-Hong Wu, Jian-Hong Zhang, and Yu-Min Wang. Practical t-out-n oblivious transfer and its applications. In International Conference on Information and Communications Security, pages 226–237. Springer, 2003.

[25] Jen-Chieh Hsu, Raylin Tso, Yu-Chi Chen, and Mu-En Wu. Oblivious transfer protocols based on commutative encryption. In 2018 9th IFIP International Conference on New Technologies, Mobility and Security (NTMS), pages 1–5. IEEE, 2018.

[26] Xiaopeng Zhu, Yong Wu, Xiaodong Li, and Jianyi Zhang. A new ciphertext based ot protocol in cloud computing. In 2023 4th International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT), pages 408–413. IEEE, 2023.

[27] Xianmin Wang, Xiaohui Kuang, Jin Li, Jing Li, Xiaofeng Chen, and Zheli Liu. Oblivious transfer for privacy-preserving in vanet’s feature matching. IEEE transactions on intelligent transportation systems, 22(7):4359–4366, 2020.

[28] Oded Goldreich. Foundations of cryptography: volume 2, basic applications, volume 2. Cambridge university press, 2001.

[29] Whitfield Diffie and Martin E Hellman. New directions in cryptography. In Democratizing cryptography: the work of Whitfield Diffie and Martin Hellman, pages 365–390. 2022.