TWo-IN-one-SSE: Fast, Scalable and Storage-Efficient Searchable Symmetric Encryption for Conjunctive and Disjunctive Boolean Queries
Abstract
Searchable Symmetric Encryption (SSE) supports efficient yet se- cure 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 sup- ports arbitrary Boolean queries over encrypted databases? In this paper, we present the design, analysis and prototype implementa- tion of the first SSE scheme that efficiently supports conjunctive, disjunctive and more general Boolean queries (in both the con- junctive 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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000568666Publication status
publishedExternal links
Journal / series
Proceedings on Privacy Enhancing TechnologiesVolume
Pages / Article No.
Publisher
Privacy Enhancing Technologies Symposium Advisory BoardEvent
Subject
Searchable encryption; Database encryption; Encrypted search; Boolean queries; Conjunctive and disjunctive queriesOrganisational unit
09653 - Paterson, Kenneth / Paterson, Kenneth
More
Show all metadata
ETH Bibliography
no
Altmetrics