Charalampos Papamanthou: Leakage Abuse Attacks in Encrypted Databases

Since the seventies, one of the holy grails of cryptography has been the invention of encryption algorithms that allow computation to be performed directly on ciphertexts without prior decryption. While heavy cryptographic hammers like fully-homomorphic encryption and oblivious RAMs can address (versions of) the aforementioned problem with ideal security guarantees, encrypted databases provide a more practical alternative. An encrypted database achieves considerable efficiency by releasing some formally-defined and superficially harmless information, known as leakage. However, it turns out such leakage can lead to complete value reconstruction of the database! In this talk I will review some of the basic techniques to perform database reconstruction from range search leakage and then I will present my recent work on query distribution-agnostic attacks on encrypted databases. I will conclude with some suggestions about how to argue formally about the security of encrypted databases. This talk is based on joint works with Evgenios Kornaropoulos (UC Berkeley), Alexandros Psomas (Purdue University), Dawn Song (UC Berkeley) and Roberto Tamassia (Brown University).