TWo-IN-one-SSE: Fast, Scalable and Storage-Efficient Searchable Symmetric Encryption for Conjunctive and Disjunctive Boolean Queries
Authors: Arnab Bag (Indian Institute of Technology, Kharagpur, India), Debadrita Talapatra (Indian Institute of Technology, Kharagpur, India), Ayushi Rastogi (Indian Institute of Technology, Kharagpur, India), Sikhar Patranabis (IBM Research India), Debdeep Mukhopadhyay (Indian Institute of Technology, Kharagpur, India)
Volume: 2023
Issue: 1
Pages: 115–139
DOI: https://doi.org/10.56553/popets-2023-0008
Abstract: 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.
Keywords: Searchable Encryption, Database Encryption, Encrypted Search, Boolean Queries, Conjunctive and Disjunctive Queries
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
