Paper 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.