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.