IXT: Improved searchable encryption for multi-word queries based on PSI

Abstract

Oblivious Cross-Tags (OXT) [1] is the first efficient searchable encryption (SE) protocol for conjunctive queries in a single-writer single-reader framework. However, it also has a trade-off between security and efficiency by leaking partial database information to the server. Recent attacks on these SE schemes show that the leakages from these SE schemes can be used to recover the content of queried keywords. To solve this problem, Lai et al. [2] propose Hidden Cross-Tags (HXT), which reduces the access pattern leakage from Keyword Pair Result Pattern (KPRP) to Whole Result Pattern (WRP). However, the WRP leakage can also be used to recover some additional contents of queried keywords. This paper proposes Improved Cross-Tags (IXT), an efficient searchable encryption protocol that achieves access and searches pattern hiding based on the labeled private set intersection. We also prove the proposed labeled private set intersection (PSI) protocol is secure against semi-honest adversaries, and IXT is L^{\prime }-semi-honest secure (L^{\prime } is leakage function). Finally, we do experiments to compare IXT with HXT. The experimental results show that the storage overhead and computation overhead of the search phase at the client-side in IXT is much lower than those in HXT. Meanwhile, the experimental results also show that IXT is scalable and can be applied to various sizes of datasets.

Graphical abstract

Keywords

searchable encryption / private set intersection

Yunbo Yang is a doctoral student in East China Normal University, China. His main research direction is secure multiparty computation (MPC) and private set intersection (PSI). He also works as a cryptographic researcher in Kunyao Academy of Shanghai Kunyao Network Technology Co., Ltd. and is responsible for the design of cryptographic algorithm

Xiaolei Dong received her PhD degree at Harbin Institute of Technology, China in 2001. She is a doctoral supervisor in East China Normal University, China. Her research interests include number theory, cryptography and network security (cloud computing, cloud processing security and privacy protection, big data security and privacy protection, etc.)

Zhenfu Cao is a doctoral supervisor in East China Normal University, China. His research interests include number theory, cryptography and new theories of network security (cloud computing, cloud processing security and privacy protection, big data security and privacy protection, etc.)

Jiachen Shen received his Bachelor degree at Shanghai Jiao Tong University, China in 2001, his Master and PhD degrees at University of Louisiana at Lafayette, USA in 2003 and 2008, respectively. He joined East China Normal University, China in 2015. His research interests include applied cryptography, cloud security, searchable encryption, and blockchains

Shangmin Dou received his Bachelor degree in Shanghai Ocean University, China in 2020. His main research interests is network security and applied cryptography (secure multiparty computation and data security, etc.). He is now working as a developer in PwC and is responsible for the design of system structure

References

[1] Cash D, Jarecki S, Jutla C, Krawczyk H, Roşu M C, Steiner M. Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 353–373

[2] Lai S, Patranabis S, Sakzad A, Liu J K, Mukhopadhyay D, Steinfeld R, Sun S F, Liu D, Zuo C. Result pattern hiding searchable encryption for conjunctive queries. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 745–762

[3] Curtmola R, Garay J, Kamara S, Ostrovsky R . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895–934

[4] Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection. In: Proceedings of 2004 International Conference on the Theory and Applications of Cryptographic Techniques on Cryptology. 2004, 1–19

[5] Lee K, Seo M . Functional encryption for set intersection in the multi-client setting. Designs, Codes and Cryptography, 2022, 90( 1): 17–47

[6] Huang Y, Evans D, Katz J. Private set intersection: are garbled circuits better than custom protocols? In: Proceedings of the 19th Network and Distributed Security Symposium. 2012

[7] Dong C, Chen L, Wen Z. When private set intersection meets big data: an efficient and scalable protocol. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 789–800

[8] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1243–1255

[9] Chen H, Huang Z, Laine K, Rindal P. Labeled PSI from fully homomorphic encryption with malicious security. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 1223–1237

[10] Wang J, Chen X, Sun S F, Liu J K, Au M H, Zhan Z H. Towards efficient verifiable conjunctive keyword search for large encrypted database. In: Proceedings of the 23rd European Symposium on Research in Computer Security. 2018, 83–100

[11] Liu C, Zhu L, Wang M, Tan Y A . Search pattern leakage in searchable encryption: attacks and new construction. Information Sciences, 2014, 265: 176–188

[12] Peter A, Tews E, Katzenbeisser S . Efficiently outsourcing multiparty computation under multiple keys. IEEE Transactions on Information Forensics and Security, 2013, 8( 12): 2046–2058

[13] Islam M S, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: Proceedings of the 19th Annual Network and Distributed System Security Symposium. 2012, 12

[14] Garg S, Mohassel P, Papamanthou C. TWORAM: efficient oblivious ram in two rounds with applications to searchable encryption. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 563–592

[15] Wang B, Song W, Lou W, Hou Y T. Inverted index based multi-keyword public-key searchable encryption with strong privacy guarantee. In: Proceedings of 2015 IEEE Conference on Computer Communications (INFOCOM). 2015, 2092–2100

[16] Wang Y, Sun S F, Wang J, Liu J K, Chen X . Achieving searchable encryption scheme with search pattern hidden. IEEE Transactions on Services Computing, 2022, 15( 2): 1012–1025

[17] Pinkas B, Rosulek M, Trieu N, Yanai A. PSI from PaXoS: fast, malicious private set intersection. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 739–767

[18] Rabin M O. How to exchange secrets with oblivious transfer. Paper 2005/187. Cryptology ePrint Archive, 2005

[19] Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 54–70

[20] Orrù M, Orsini E, Scholl P. Actively secure 1-out-of-N OT extension with application to private set intersection. In: Proceedings of 2017 Cryptographers’ Track at the RSA Conference on Topics in Cryptology. 2017, 381–396

[21] Goldreich O. Foundations of Cryptography: Vol. 2, Basic Applications. Cambridge: Cambridge University Press, 2004

[22] Apache Lucene. See Lucene.apache website

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China (2020YFA0712300), in part by the National Natural Science Foundation of China (Grant Nos. 62172162, 62132005), and in part by the Shanghai Trusted Industry Internet Software Collaborative Innovation Center.

RIGHTS & PERMISSIONS

2023 Higher Education Press