Breaking and Building Encrypted Databases

Grubbs, Paul Allen

Breaking and Building Encrypted Databases

Abstract

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.

Description

139 pages

Date Issued

2020-08

Keywords

applied cryptography; computer security; cryptography; databases; encryption

Committee Chair

Ristenpart, Thomas

Committee Member

Zabih, Ramin
Shmatikov, Vitaly

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Rights

Attribution 4.0 International

Rights URI

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

Types

dissertation or thesis