On the Security of O-PSI: A Delegated Private Set Intersection on Outsourced Datasets (Extended Version)



1 Electronics Research Institute of Sharif university of Technology, Tehran, Iran

2 Department of Electrical Engineering, Sharif university of Technology, Tehran, Iran


In recent years, determining the common information privately and efficiently between two mutually mistrusting parties have become an important issue in social networks. Many Private Set Intersection (PSI) protocols have been introduced to address this issue. By applying these protocols, two parties can compute the intersection between their sets without disclosing any information about components that are not in the intersection. Due to the broad range of computational resources that the cloud can provide for its users, determining the set intersection by cloud may decrease the computational cost of the users. The proposed protocols by Abadi et al. are two protocols in this context. In this paper, we show that their protocols are vulnerable to eavesdropping attack. Also, a solution is proposed to secure the protocol against mentioned attack. Moreover, we analyze the performance of both O-PSI and modified O-PSI protocols and show that our scheme is comparable with the O-PSI protocol. Actually, one trivial solution for the Abadi et al.’s proposed schemes is to use a secure channel like TLS. However, in the performance evaluation, we compare our applied modification with this trivial solution, and show that our proposed modification is more efficient as some extra encryptions imposed by TLS are no longer required.


[1] Michael J Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques, pages 1–19. Springer, 2004.
[2] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 223–238. Springer, 1999.
[3] Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. Fast and private computation of cardinality of set intersection and union. In International Conference on Cryptology and Network Security, pages 218–231. Springer, 2012.
[4] Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. In International Conference on Financial Cryptography and Data Security, pages 143–159. Springer, 2010.

[5] Giuseppe Ateniese, Emiliano De Cristofaro, and Gene Tsudik. (if) size matters: size-hiding private set intersection. In International Workshop on Public Key Cryptography, pages 156–173.Springer, 2011.
[6] Lea Kissner and Dawn Song. Privacy-preserving set operations. In Annual International Cryptology Conference, pages 241–257. Springer, 2005.
[7] Atsuko Miyaji and Shohei Nishida. A scalable multiparty private set intersection. In International Conference on Network and System Security, pages 376–385. Springer, 2015.
[8] Dilip Many and Martin Burkhart. Fast private set operations with sepia. 2012.
[9] Peter Rindal and Mike Rosulek. Improved private set intersection against malicious adversaries. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 235–259. Springer, 2017.
[10] Changhee Hahn and Junbeom Hur. Scalable and secure private set intersection for big data. In Big Data and Smart Computing (BigComp), 2016 International Conference on, pages 285–288.IEEE, 2016.
[11] Changyu Dong, Liqun Chen, and Zikai Wen. When private set intersection meets big data: an efficient and scalable protocol. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 789–800.
ACM, 2013.
[12] Arun Thapa, Ming Li, Sergio Salinas, and Pan Li. Asymmetric social proximity based private matching protocols for online social networks. IEEE Transactions on parallel and distributed systems, 26(6):1547–1559, 2015.
[13] Zhiyi Shao, Bo Yang, and Yong Yu. Private set intersection via public key encryption with multiple keywords search. In Intelligent Networking and Collaborative Systems (INCoS), 2013 5th International Conference on, pages 323–328. IEEE,
[14] Keita Emura, Atsuko Miyaji, and Mohammad Shahriar Rahman. Private multiparty set intersection protocol in rational model. In 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, pages 431–438. IEEE, 2013.
[15] Dongdong Zhao and Wenjian Luo. A study of the private set intersection protocol based on negative databases. In Dependable, Autonomic and Secure Computing (DASC), 2013 IEEE 11th International Conference on, pages 58–64. IEEE,
[16] Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable private set intersection based on ot extension. ACM Transactions on Privacy and Security (TOPS), 21(2):7, 2018.
[17] Qingji Zheng and Shouhuai Xu. Verifiable delegated set intersection operations on outsourced encrypted data. In Cloud Engineering (IC2E), 2015 IEEE International Conference on, pages 175–184. IEEE, 2015.
[18] Mohammadhassan Ameri Ekhtiarabadi, Habib Allah Yajam, Javad Mohajeri, and Mahmoud Salmasizadeh. Verifiable identity-based mix network. In Electrical Engineering (ICEE), 2015 23rd Iranian Conference on, pages 406–409.IEEE, 2015.
[19] Vahid Yousefipoor, Mohammad Hassan Ameri, Javad Mohajeri, and Taraneh Eghlidos. A secure attribute based keyword search scheme against keyword guessing attack. In Telecommunications (IST), 2016 8th International Symposium on, pages 124–128. IEEE, 2016.
[20] Mahdi Mahdavi Oliaiy, Mohammad Hassan Ameri, Javad Mohajeri, and Mohammad Reza Aref. A verifiable delegated set intersection without pairing. In Electrical Engineering (ICEE), 2017 Iranian Conference on, pages 2047–2051. IEEE, 2017.

[21] Shuo Qiu, Jiqiang Liu, Yanfeng Shi, Ming Li, and Wei Wang. Identity-based private matching over outsourced encrypted datasets. IEEE Transactions on Cloud Computing, 2015.
[22] Ran Canetti, Omer Paneth, Dimitrios Papadopoulos, and Nikos Triandopoulos. Verifiable set operations over outsourced databases. In International Workshop on Public Key Cryptography, pages 113–130. Springer, 2014.
[23] En Zhang, Fenghua Li, Ben Niu, and Yanchao Wang. Server-aided private set intersection based on reputation. Information Sciences, 387:180–194, 2017.
[24] Florian Kerschbaum. Outsourced private set intersection using homomorphic encryption. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 85–86. ACM, 2012.
[25] Florian Kerschbaum. Collusion-resistant outsourcing of private set intersection. In Proceedings of the 27th Annual ACM Symposium on Applied Computing, pages 1451–1456. ACM, 2012.
[26] Fang Liu, Wee Keong Ng, Wei Zhang, Shuguo Han, et al. Encrypted set intersection protocol for outsourced datasets. In Cloud Engineering(IC2E), 2014 IEEE International Conference on, pages 135–140. IEEE, 2014.
[27] Aydin Abadi, Sotirios Terzis, and Changyu Dong. O-psi: delegated private set intersection on outsourced datasets. In IFIP International Information Security Conference, pages 3–17. Springer,2015.
[28] Aydin Abadi, Sotirios Terzis, Roberto Metere, and Changyu Dong. Efficient delegated private set intersection on outsourced private datasets. IEEE Transactions on Dependable and Secure Computing, 2017.
[29] Aydin Abadi, Sotirios Terzis, and Changyu Dong. Vd-psi: Verifiable delegated private set intersection on outsourced private datasets. In International Conference on Financial Cryptography and Data Security, pages 149–168. Springer, 2016.
[30] Xiaoyuan Yang, Xiaoshuang Luo, Xu An Wang, and Shuaiwei Zhang. Improved outsourced private set intersection protocol based on polynomial interpolation. Concurrency and Computation: Practice and Experience, 30(1):e4329, 2018.
[31] Seny Kamara, Payman Mohassel, Mariana Raykova, and Saeed Sadeghian. Scaling private set intersection to billion-element sets. In International Conference on Financial Cryptography and Data Security, pages 195–215. Springer,2014.
[32] Mohammad Hassan Ameri, Mahshid Delavar, Javad Mohajeri, and Mahmoud Salmasizadeh. A key-policy attribute-based temporary keyword search scheme for secure cloud storage. IEEE Transactions on Cloud Computing, 2018.
[33] Sergei V Fedorenko and Peter V Trifonov. Finding roots of polynomials over finite fields. IEEE Transactions on communications, 50(11):1709–1711, 2002.
[34] S Dov Gordon, Jonathan Katz, Feng-Hao Liu, Elaine Shi, and Hong-Sheng Zhou. Multi-client verifiable computation with stronger security guarantees. In Theory of Cryptography Conference, pages 144–168. Springer, 2015.