Breaking and Building Encrypted Databases

The subject of this thesis is encrypted databases: systems that use novel cryptographic techniques to store and efficiently query encrypted data. Motivated by the increasing frequency and severity of harmful data breaches, encrypted databases keep data encrypted at all times, ensuring that it is unavailable even to an attacker that compromises the database system’s security. To keep queries efficient, encrypted databases must leak some information about the underlying plaintext data and queries. The leakage and its impact on security differs depending on the way the system is compromised. In this thesis, I investigate the performance-security tradeoffs made by encrypted databases. First, I study current encrypted databases to understand the leakage that would be available to an attacker in likely compromise scenarios. I conclude that many of the security claims made of encrypted databases are incorrect. Then, I examine the security impact of a concrete leakage shared by most encrypted databases. In the process I develop new technical tools based on statistical learning theory. Finally, informed by an understanding of existing databases, I propose a novel performance-security tradeoff for encrypted key-value stores. I instantiate that new tradeoff with frequency smoothing, analyze it using new theory, and build a system.

Name thesis:degree_name

Ph. D., Computer Science

Level thesis:degree_level

Doctor of Philosophy

Discipline thesis:degree_discipline

Computer Science

Grantor

Cornell University

Year dc:date.issued

2020

Author dc:creator

• Grubbs, Paul Allen

Committee members dc:contributor.committeemember

• Zabih, Ramin
• Shmatikov, Vitaly

• applied cryptography
• computer security
• cryptography
• databases
• encryption

Statement dc:rights

• Attribution 4.0 International

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

DOI

https://doi.org/10.7298/1tvp-fr92

Dc Identifier Other

ProQuest Submission ID: 12252
ProQuest Publication ID: 28089155

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/102884