Ioannis Demertzis (University of Maryland), Javad Ghareh Chamani (Hong Kong University of Science and Technology & Sharif University of Technology), Dimitrios Papadopoulos (Hong Kong University of Science and Technology), Charalampos Papamanthou (University of Maryland)

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

Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning

Harsh Chaudhari (Indian Institute of Science, Bangalore), Rahul Rachuri (Aarhus University, Denmark), Ajith Suresh (Indian Institute of Science, Bangalore)

Read More

Automated Discovery of Cross-Plane Event-Based Vulnerabilities in Software-Defined Networking

Benjamin E. Ujcich (University of Illinois at Urbana-Champaign), Samuel Jero (MIT Lincoln Laboratory), Richard Skowyra (MIT Lincoln Laboratory), Steven R. Gomez (MIT Lincoln Laboratory), Adam Bates (University of Illinois at Urbana-Champaign), William H. Sanders (University of Illinois at Urbana-Champaign), Hamed Okhravi (MIT Lincoln Laboratory)

Read More

ProtectIOn: Root-of-Trust for IO in Compromised Platforms

Aritra Dhar (ETH Zurich), Enis Ulqinaku (ETH Zurich), Kari Kostiainen (ETH Zurich), Srdjan Capkun (ETH Zurich)

Read More

SPEECHMINER: A Framework for Investigating and Measuring Speculative Execution...

Yuan Xiao (The Ohio State University), Yinqian Zhang (The Ohio State University), Radu Teodorescu (The Ohio State University)

Read More