Paper 2022/1096

TWo-IN-one-SSE: Fast, Scalable and Storage-Efficient Searchable Symmetric Encryption for Conjunctive and Disjunctive Boolean Queries

Arnab Bag, IIT Kharagpur, India
Debadrita Talapatra, IIT Kharagpur, India
Ayushi Rastogi, IIT Kharagpur, India
Sikhar Patranabis, IBM Research India
Debdeep Mukhopadhyay, IIT Kharagpur, India

Searchable Symmetric Encryption (SSE) supports efficient yet secure query processing over outsourced symmetrically encrypted databases without the need for decryption. A longstanding open question has been the following: can we design a fast, scalable, linear storage and low-leakage SSE scheme that efficiently supports arbitrary Boolean queries over encrypted databases? In this paper, we present the design, analysis and prototype implementation of the first SSE scheme that efficiently supports conjunctive, disjunctive and more general Boolean queries (in both the conjunctive and disjunctive normal forms) while scaling smoothly to extremely large encrypted databases, and while incurring linear storage overheads and supporting extremely fast query processing in practice. We quantify the leakage of our proposal via a rigorous cryptographic analysis and argue that it achieves security against a well-known class of leakage-abuse and volume analysis attacks. Finally, we demonstrate the storage-efficiency and scalability of our proposed scheme by presenting experimental results of a prototype implementation of our scheme over large real-world databases.

Available format(s)
Publication info
Published elsewhere. PoPETs 2023 (to appear)
Searchable Symmetric Encryption Boolean Queries Conjunctive Queries Disjunctive Queries
Contact author(s)
amiarnabbolchi @ gmail com
debadritat fg2219 @ gmail com
rayushi835 @ gmail com
sikharpatranabis @ gmail com
debdeep mukhopadhyay @ gmail com
2022-08-29: approved
2022-08-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arnab Bag and Debadrita Talapatra and Ayushi Rastogi and Sikhar Patranabis and Debdeep Mukhopadhyay},
      title = {TWo-IN-one-SSE: Fast, Scalable and Storage-Efficient Searchable Symmetric Encryption for Conjunctive and Disjunctive Boolean Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1096},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.