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

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

RIGHTS & PERMISSIONS

Higher Education Press