David Wu: 2017 Security Workshop


Monday, April 10, 2017
Location: McCaw Hall, Arrillaga Alumni Center

"Order-Revealing Encryption: How to Search on Encrypted Data"



In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-revealing encryption (ORE) scheme (i.e., an encryption scheme that enables comparisons on encrypted values). While these encryption schemes have the advantage of being legacy-friendly (i.e., easy to integrate with existing database management systems), a recent line of work beginning with Naveed et al. (CCS 2015) showed that these legacy-friendly solutions are extremely vulnerable to "inference attacks." Naveed et al. (and subsequently, Durak et al. (CCS 2016) as well as Grubbs et al. (S&P 2017)) show that an attacker who just obtains a static dump (i.e., offline access) to a database encrypted under an ORE scheme can actually recover nearly all of the data contained in the database.

In this work, we introduce a new paradigm for constructing order-revealing encryption that enables substantially stronger security in the offline setting. Notably, when using our new ORE candidate to perform range queries over an encrypted database, the ciphertexts in the database provide semantic security, and thus, provably reveal no information about the underlying contents. In this way, our new ORE scheme is the first practically-viable scheme that is robust against all offline inference attacks. In the online setting, we show that our ORE scheme is more secure than existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives (e.g., AES). Finally, we give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes (the current standard that has been deployed in several industry applications), it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.

Joint work with Kevin Lewi.


David Wu is a PhD student working with Dan Boneh on both applied and theoretical cryptography. On the applied side, he has worked on problems related to searching on encrypted data, developing privacy-preserving protocols for personal genomics, and building secure authentication protocols for the Internet of Things. On the theoretical side, his recent work include introducing new constructions of succinct non-interactive argument (SNARG) systems and exploring the connections between different flavors of functional encryption.