Current worldwide trends towards remote data storage solutions such as cloud storage, in which large stores of data on insecure networks must be efficiently accessible, and increasing security requirements emphasized the need to support efficient search functionality on large encrypted databases. Searchable encryption is a balancing act of efficiency, functionality, and security. The solutions either require extensive interaction and computation, linear data scan on each query, which is prohibitive for large databases, or knowing all data in advance. This research advances the state of the art of efficiently-searchable encryption (ESE) by focusing on three key areas: new security guarantees for order-preserving encryption, searchable encryption for fuzzy queries, and seeking a general definition of ESE.
The PI has conducted a cryptographic study of order-preserving encryption for supporting efficient range queries on remote encrypted data. This project clarifies the security guarantees of the previous definition and studies the alternative settings in order to develop new secure solutions. This research focuses on fuzzy queries which return database elements that correspond to messages which are close to the underlying queried message. This work initiates the first formal cryptographic study of fuzzy searchable encryption (FSE). In particular, the work focuses on developing appropriate security definitions and building provably-secure FSE schemes. This research seeks a general definition that will cover all known types of ESE, and investigates related impossibility issues. The research extends security definitions for various ESE to security of the database as a whole.
