Rethinking Searchable Encryption

Speaker: Sikhar Patranabis

Abstract

Database encryption is a key enabler for secure storage-as-a-service, wherein clients can securely outsource the storage and processing of large databases to (potentially untrusted) third party cloud servers. Over the past 20 years, searchable symmetric encryption (SSE) has emerged as an attractive and highly practical subclass of database encryption that allows directly querying encrypted databases, without actually decrypting the data. A crucial aspect of designing any SSE scheme is to minimize leakage, i.e., the information learnt by the untrusted server about the client's data and queries. In this talk, I will introduce a new and practically motivated system-wide viewpoint of analyzing the leakage of SSE schemes. This naturally leads to the question: do existing SSE schemes in the literature actually protect the security of data and queries when analyzed from such a system-wide viewpoint? The answer turns out to be no -- we develop a new inference attack that exploits system-wide leakage to achieve practically efficient, highly scalable, and accurate query reconstruction against a vast majority of existing SSE schemes. I will then briefly discuss the possibility of applying existing leakage-suppression techniques such as volume-hiding encrypted multi-maps to protect SSE schemes against attacks exploiting system-wide leakage. The answer here also turns out to be negative. We validate this via experiments showing that such leakage protected implementations of SSE are practically inefficient and do not realistically scale to large databases. In totality, I hope to convey through this talk the need to thoroughly re-evaluate how to build SSE schemes (and more generally database encryption schemes) that offer both security and efficiency in practice. Based on a joint work with Zichen Gui and Kenny Paterson. No prior background on cryptography will be required.

Bio

Sikhar Patranabis is a research scientist at IBM Research India (IBM IRL), where he is a member of the blockchain and supply chain department. His research focuses on theoretical and applied aspects of cryptography and hardware security. He was previously a staff research scientist at Visa Research USA, a postdoctoral researcher at ETH Zurich, Switzerland, and a research associate at IISc Bangalore. He received his PhD and B.Tech in Computer Science and Engineering from IIT Kharagpur. He is the recipient of an IBM PhD fellowship, a Qualcomm Innovation Fellowship, and the President of India gold medal from IIT Kharagpur.