2026-09-18T22:11:50Zhttps://ecommons.cornell.edu/server/oai/request

oai:ecommons.cornell.edu:1813/1028842026-05-15T19:48:25Zcom_1813_35col_1813_47

Grubbs, Paul Allen Ristenpart, Thomas Zabih, Ramin Shmatikov, Vitaly 2021-03-12T17:38:21Z 2021-03-12T17:38:21Z 2020-08 ProQuest Submission ID: 12252 ProQuest Publication ID: 28089155 https://hdl.handle.net/1813/102884 https://doi.org/10.7298/1tvp-fr92 13277835 139 pages 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. en Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/ applied cryptography computer security cryptography databases encryption Breaking and Building Encrypted Databases dissertation or thesis https://catalog.library.cornell.edu/catalog/13277835 application/pdf Computer Science Cornell University Doctor of Philosophy Ph. D., Computer Science https://hdl.handle.net/1813/59810 Publication Cornell Theses and Dissertations Grubbs, Paul Allen 5893a6ea-7af3-41d7-abc6-04bcd26ab5df open.access open.access <Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="0c095f41-bafd-4197-b069-87c04ba331da"> <Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Breaking and Building Encrypted Databases</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2020-08</PublicationDate> <DOI>https://doi.org/10.7298/1tvp-fr92</DOI> <Authors> <Author> <DisplayName>Grubbs, Paul Allen</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <License>https://creativecommons.org/licenses/by/4.0/</License> <Keyword>applied cryptography</Keyword> <Keyword>computer security</Keyword> <Keyword>cryptography</Keyword> <Keyword>databases</Keyword> <Keyword>encryption</Keyword> <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.</Abstract> <Access xmlns="http://purl.org/coar/access_right" > </Access> </Publication>