We study the problem of dynamic searchable encryption (DSE) with forward-and-backward privacy. Many DSE schemes have been proposed recently but the most efficient ones have one limitation: they require maintaining an operation counter for each unique keyword, either stored locally at the client or accessed obliviously (e.g., with an oblivious map) at the server, during every operation. We propose three new schemes that overcome the above limitation and achieve constant permanent client storage with improved performance, both asymptotically and experimentally, compared to prior state-of-the-art works. In particular, our first two schemes adopt a "static-to-dynamic" transformation which eliminates the need for oblivious accesses during searches. Due to this, they are the first practical schemes with minimal client storage and non-interactive search. Our third scheme is the first quasi-optimal forward-and-backward DSE scheme with only a logarithmic overhead for retrieving the query result (independently of previous deletions). While it does require an oblivious access during search in order to keep permanent client storage minimal, its practical performance is up to four orders of magnitude better than the best existing scheme with quasi-optimal search.

View More Papers

Proof of Storage-Time: Efficiently Checking Continuous Data Availability

Giuseppe Ateniese (Stevens Institute of Technology), Long Chen (New Jersey Institute of Technology), Mohammard Etemad (Stevens Institute of Technology), Qiang...

Read More

Finding Safety in Numbers with Secure Allegation Escrows

Venkat Arun (Massachusetts Institute of Technology), Aniket Kate (Purdue University), Deepak Garg (Max Planck Institute for Software Systems), Peter Druschel...

Read More

A Practical Approach for Taking Down Avalanche Botnets Under...

Victor Le Pochat (imec-DistriNet, KU Leuven), Tim Van hamme (imec-DistriNet, KU Leuven), Sourena Maroofi (Univ. Grenoble Alpes, CNRS, Grenoble INP,...

Read More

CloudLeak: Large-Scale Deep Learning Models Stealing Through Adversarial Examples

Honggang Yu (University of Florida), Kaichen Yang (University of Florida), Teng Zhang (University of Central Florida), Yun-Yun Tsai (National Tsing...

Read More