Sikhar Patranabis (ETH Zurich), Debdeep Mukhopadhyay (IIT Kharagpur)

Dynamic searchable symmetric encryption (SSE) supports updates and keyword searches in tandem on outsourced symmetrically encrypted data, while aiming to minimize the information revealed to the (untrusted) host server. The literature on dynamic SSE has identified two crucial security properties in this regard - emph{forward} and emph{backward} privacy. Forward privacy makes it hard for the server to correlate an update operation with previously executed search operations. Backward privacy limits the amount of information learnt by the server about documents that have already been deleted from the database.

To date, work on forward and backward private SSE has focused mainly on single keyword search. However, for any SSE scheme to be truly practical, it should at least support conjunctive keyword search. In this setting, most prior SSE constructions with sub-linear search complexity do not support dynamic databases. The only exception is the scheme of Kamara and Moataz (EUROCRYPT'17); however it only achieves forward privacy. Achieving emph{both} forward and backward privacy, which is the most desirable security notion for any dynamic SSE scheme, has remained open in the setting of conjunctive keyword search.

In this work, we develop the first forward and backward private SSE scheme for conjunctive keyword searches. Our proposed scheme, called Oblivious Dynamic Cross Tags (or ODXT in short), scales to very large arbitrarily-structured databases (including both attribute-value and free-text databases). ODXT provides a realistic trade-off between performance and security by efficiently supporting fast updates and conjunctive keyword searches over very large databases, while incurring only moderate access pattern leakages to the server that conform to existing notions of forward and backward privacy. We precisely define the leakage profile of ODXT, and present a detailed formal analysis of its security. We then demonstrate the practicality of ODXT by developing a prototype implementation and evaluating its performance on real world databases containing millions of documents.

View More Papers

Censored Planet: An Internet-wide, Longitudinal Censorship Observatory

R. Sundara Raman, P. Shenoy, K. Kohls, and R. Ensafi (University of Michigan)

Read More

XDA: Accurate, Robust Disassembly with Transfer Learning

Kexin Pei (Columbia University), Jonas Guan (University of Toronto), David Williams-King (Columbia University), Junfeng Yang (Columbia University), Suman Jana (Columbia University)

Read More

Favocado: Fuzzing the Binding Code of JavaScript Engines Using...

Sung Ta Dinh (Arizona State University), Haehyun Cho (Arizona State University), Kyle Martin (North Carolina State University), Adam Oest (PayPal, Inc.), Kyle Zeng (Arizona State University), Alexandros Kapravelos (North Carolina State University), Gail-Joon Ahn (Arizona State University and Samsung Research), Tiffany Bao (Arizona State University), Ruoyu Wang (Arizona State University), Adam Doupe (Arizona State University),…

Read More

When DNS Goes Dark: Understanding Privacy and Shaping Policy...

Vijay k. Gurbani and Cynthia Hood ( Illinois Institute of Technology), Anita Nikolich (University of Illinois), Henning Schulzrinne (Columbia University) and Radu State (University of Luxembourg)

Read More