Cryptology ePrint Archive: Report 2020/1328

SWiSSSE: System-Wide Security for Searchable Symmetric Encryption

Zichen Gui and Kenneth G. Paterson and Sikhar Patranabis and Bogdan Warinschi

Abstract: This paper initiates a new direction of research for searchable symmetric encryption (SSE). We provide comprehensive security models and notions for SSE in the simulation tradition that encompass leakage from the whole SSE system, including accesses to encrypted indices and the encrypted database documents themselves. We provide static and dynamic SSE constructions targeting our new notions. Our constructions involve a combination of novel techniques: bucketization to hide volumes of responses to queries; delayed, pseudorandom write-backs to disrupt access patterns; and indistinguishable search and update operations. The oblivious operations make it easy to establish strong versions of forward and backward security for our dynamic SSE scheme and rule out file-injection attacks. Our implementation of the dynamic SSE scheme demonstrates that it offers very strong security against general classes of leakage-abuse attack with moderate overhead. Our schemes scale smoothly to databases containing hundreds of thousand of documents and millions of keyword-document pairs.

Category / Keywords: applications / Searchable Symmetric Encryption, System-Wide Security, Leakage Cryptanalysis, Bucketization, Forward and Backward Privacy, Oblivious Operations

Date: received 22 Oct 2020

Contact author: zg13988 at bristol ac uk,kenny paterson@inf ethz ch,sikharpatranabis@gmail com,csxbw@bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20201023:085005 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]