Cryptology ePrint Archive: Report 2016/612

Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds

Kevin Lewi and David J. Wu

Abstract: 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-preserving encryption (OPE) scheme (i.e., an encryption scheme that supports comparisons over encrypted values). However, Naveed et al. (CCS 2015) recently showed that OPE-encrypted databases are extremely vulnerable to "inference attacks."

In this work, we consider a related primitive called order-revealing encryption (ORE), which is a generalization of OPE that allows for stronger security. We begin by constructing a new ORE scheme for small message spaces which achieves the "best-possible" notion of security for ORE. Next, we introduce a "domain-extension" technique and apply it to our small-message-space ORE. While our domain-extension technique does incur a loss in security, the resulting ORE scheme we obtain is more secure than all existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives. As part of our analysis, we also give a tight lower bound for OPE and show that no efficient OPE scheme can satisfy best-possible security if the message space contains just three messages. Thus, achieving strong notions of security for even small message spaces requires moving beyond OPE.

Finally, we examine the properties of our new ORE scheme and show how to use it to construct an efficient range query protocol that is robust against the inference attacks of Naveed et al. We also give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes, it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.

Category / Keywords: secret-key cryptography / order-revealing encryption, order-preserving encryption, range queries

Original Publication (with major differences): ACM Conference on Computer and Communications Security (CCS) 2016
DOI:
10.1145/2976749.2978376

Date: received 11 Jun 2016, last revised 8 Aug 2016

Contact author: dwu4 at cs stanford edu

Available format(s): PDF | BibTeX Citation

Note: Extended version of paper appearing in CCS 2016.

Version: 20160808:191250 (All versions of this report)

Short URL: ia.cr/2016/612

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]