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 ...
Carter, Henry; Amrutkar, Chaitrali; Dacosta, Italo; Traynor, Patrick (Georgia Institute of Technology, 2011)The growth of smartphone capability has led to an explosion of new applications. Many of the most useful apps use context-sensitive data, such as GPS location or social network information. In these cases, users may not ...
Lau, Billy; Chung, Simon; Song, Chengyu; Jang, Yeongjin; Lee, Wenke; Boldyreva, Alexandra (Georgia Institute of Technology, 2014-07)Users are increasingly storing, accessing, and exchanging data through public cloud services such as those provided by Google, Facebook, Apple, and Microsoft. Although users may want to have faith in cloud providers ...