Paper 2023/1712

Beyond Volume Pattern: Storage-Efficient Boolean Searchable Symmetric Encryption with Suppressed Leakage

Feng Li, Xidian University
Jianfeng Ma, Xidian University
Yinbin Miao, Xidian University
Pengfei Wu, National University of Singapore
Xiangfu Song, National University of Singapore

Boolean Searchable Symmetric Encryption (BSSE) enables users to perform retrieval operations on the encrypted data while sup- porting complex query capabilities. This paper focuses on addressing the storage overhead and privacy concerns associated with existing BSSE schemes. While Patel et al. (ASIACRYPT’21) and Bag et al. (PETS’23) introduced BSSE schemes that conceal the number of single keyword re- sults, both of them suffer from quadratic storage overhead and neglect the privacy of search and access patterns. Consequently, an open ques- tion arises: Can we design a storage-efficient Boolean query scheme that effectively suppresses leakage, covering not only the volume pattern for singleton keywords, but also search and access patterns? In light of the limitations of existing schemes in terms of storage over- head and privacy protection, this work presents a novel solution called SESAME. It realizes efficient storage and privacy preserving based on Bloom filter and functional encryption. Moreover, we propose an en- hanced version, SESAME+, which offers improved search performance. By rigorous security analysis on the leakage functions of our schemes, we provide a formal security proof. Finally, we implement our schemes and demonstrate that SESAME+ achieves superior search efficiency and reduced storage overhead.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2023
searchable symmetric encryption
Contact author(s)
feng li @ stu xidian edu cn
jfma @ xidian edu cn
ybmiao @ xidian edu cn
wupf @ comp nus edu sg
songxf @ comp nus edu sg
2023-11-06: approved
2023-11-05: received
See all versions
Short URL
No rights reserved


      author = {Feng Li and Jianfeng Ma and Yinbin Miao and Pengfei Wu and Xiangfu Song},
      title = {Beyond Volume Pattern: Storage-Efficient Boolean Searchable Symmetric Encryption with Suppressed Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1712},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.