Symmetric schemes for efficient range and error-tolerant search on encrypted data
Chenette, Nathan Lee
MetadataShow full item record
Large-scale data management systems rely more and more on cloud storage, where the need for efficient search capabilities clashes with the need for data confidentiality. Encryption and efficient accessibility are naturally at odds, as for instance strong encryption necessitates that ciphertexts reveal nothing about underlying data. Searchable encryption is an active field in cryptography studying encryption schemes that provide varying levels of efficiency, functionality, and security, and efficient searchable encryption focuses on schemes enabling sub-linear (in the size of the database) search time. I present the first cryptographic study of efficient searchable symmetric encryption schemes supporting two types of search queries, range queries and error-tolerant queries. The natural solution to accommodate efficient range queries on ciphertexts is to use order-preserving encryption (OPE). I propose a security definition for OPE schemes, construct the first OPE scheme with provable security, and further analyze security by characterizing one-wayness of the scheme. Efficient error-tolerant queries are enabled by efficient fuzzy-searchable encryption (EFSE). For EFSE, I introduce relevant primitives, an optimal security definition and a (somewhat space-inefficient, but in a sense efficient as possible) scheme achieving it, and more efficient schemes that achieve a weaker, but practical, security notion. In all cases, I introduce new appropriate security definitions, construct novel schemes, and prove those schemes secure under standard assumptions. The goal of this line of research is to provide constructions and provable security analysis that should help practitioners decide whether OPE or FSE provides a suitable efficiency-security-functionality tradeoff for a given application.
Showing items related by title, author, creator and subject.
Alperin-Sheriff, Jacob (Georgia Institute of Technology, 2015-07-24)Fully homomorphic encryption (FHE) allows for computation of arbitrary func- tions on encrypted data by a third party, while keeping the contents of the encrypted data secure. This area of research has exploded in recent ...
Yan, Chenyu (Georgia Institute of Technology, 2008-11-17)This thesis explores architectural level optimizations to make secure systems more efficient, secure and affordable. It extends prior work for secure architecture in several areas. It proposes a new combined memory ...
Cash, Charles David (Georgia Institute of Technology, 2009-09-24)This thesis is concerned with the design and analysis of practical provably-secure encryption schemes. We give several results that include new schemes with attractive tradeoffs between efficiency and security and new ...