Forward and Backward Private Conjunctive Searchable Symmetric Encryption

Forward and Backward Private Conjunctive Searchable Symmetric Encryption

Cybersecurity Seminars Online seminar
Thursday, 11 March 2021
12 pm - 1 pm (AEDT)

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 - forward and 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 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.

About the speaker

Sikhar Patranabis
Staff Research Scientist, Visa Research

Sikhar Patranabis is a staff research scientist at Visa Research. Prior to that, he was a postdoctoral researcher in the Applied Cryptography group at ETH Zurich. He received his Ph.D. from IIT Kharagpur, India. Sikhar’s research interests span all aspects of cryptography and security, with special focus on cryptographic foundations and real-world cryptographic protocols. He has published in top crypto and security conferences, including Crypto, Eurocrypt, Asiacrypt, ACM CCS and NDSS. He is currently serving on the program committees of Crypto 2021 and ESORICS 2021. Sikhar is the recipient of the IBM Ph.D. Fellowship and the Qualcomm Research Innovation Fellowship.


Event contact

About Monash Cybersecurity Seminars

Be the first to know about cybersecurity innovations.

Gain rare insights from world-leading experts. Free to attend, the Monash Cybersecurity Seminars are your portal to the latest and greatest in the discipline – from quantum-safe cryptography to blockchain.

Explore our seminars

Share this event