Inference Attacks on Encrypted Databases

Data breaches are an ever increasing concern nowadays. For instance, the 2017 Equifax breach exposed sensitive financial information of an estimated 143 millions US persons. Furthermore, companies are often powerless to protected themselves as exemplified by Yahoo! which was breached in 2013 and then again in 2014!

As a defense, some security researchers have advocated for the use of always-encrypted databases. A prominent approach to construct always-encrypted databases is to leverage weak forms of encryption which expose, in their ciphertexts, some plaintext information in order to preserve query processing functionality. The level of security offered by such constructions remains unclear and recent academic papers have suggested that straightforward inference techniques such as frequency analysis undermine their security. This project seeks to analyze the security of popular encrypted databases constructions through the design of sophisticated inference attacks which exploit the complexity of real-world data such as correlations between data record attributes.