Shi-Feng Sun (Monash University, Australia), Ron Steinfeld (Monash University, Australia), Shangqi Lai (Monash University, Australia), Xingliang Yuan (Monash University, Australia), Amin Sakzad (Monash University, Australia), Joseph Liu (Monash University, Australia), ‪Surya Nepal‬ (Data61, CSIRO, Australia), Dawu Gu (Shanghai Jiao Tong University, China)

In Dynamic Symmetric Searchable Encryption (DSSE), forward privacy ensures that previous search queries cannot be associated with future updates, while backward privacy guarantees that subsequent search queries cannot be associated with deleted documents in the past. In this work, we propose a generic forward and backward-private DSSE scheme, which is, to the best of our knowledge, the first practical and non-interactive Type-II backward-private DSSE scheme not relying on trusted execution environments. To this end, we first introduce a new cryptographic primitive, named Symmetric Revocable Encryption (SRE), and propose a modular construction from some succinct cryptographic primitives. Then we present our DSSE scheme based on the proposed SRE, and instantiate it with lightweight symmetric primitives. At last, we implement our scheme and
compare it with the most efficient Type-II backward-private scheme to date (Demertzis et al., NDSS 2020). In a typical network environment, our result shows that the search in our scheme outperforms it by 2-11x under the same security notion.

View More Papers

Sn4ke: Practical Mutation Analysis of Tests at Binary Level

Mohsen Ahmadi (Arizona State University), Pantea Kiaei (Worcester Polytechnic Institute), Navid Emamdoost (University of Minnesota)

Read More

BaseSpec: Comparative Analysis of Baseband Software and Cellular Specifications...

Eunsoo Kim (KAIST), Dongkwan Kim (KAIST), CheolJun Park (KAIST), Insu Yun (KAIST), Yongdae Kim (KAIST)

Read More

SpecTaint: Speculative Taint Analysis for Discovering Spectre Gadgets

Zhenxiao Qi (UC Riverside), Qian Feng (Baidu USA), Yueqiang Cheng (NIO Security Research), Mengjia Yan (MIT), Peng Li (ByteDance), Heng Yin (UC Riverside), Tao Wei (Ant Group)

Read More

Tales of Favicons and Caches: Persistent Tracking in Modern...

Konstantinos Solomos (University of Illinois at Chicago), John Kristoff (University of Illinois at Chicago), Chris Kanich (University of Illinois at Chicago), Jason Polakis (University of Illinois at Chicago)

Read More