Paper 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.

Note: Extended version of paper appearing in CCS 2016.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Major revision. ACM Conference on Computer and Communications Security (CCS) 2016
DOI
10.1145/2976749.2978376
Keywords
order-revealing encryptionorder-preserving encryptionrange queries
Contact author(s)
dwu4 @ cs stanford edu
History
2018-10-24: last of 3 revisions
2016-06-14: received
See all versions
Short URL
https://ia.cr/2016/612
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/612,
      author = {Kevin Lewi and David J.  Wu},
      title = {Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/612},
      year = {2016},
      doi = {10.1145/2976749.2978376},
      note = {\url{https://eprint.iacr.org/2016/612}},
      url = {https://eprint.iacr.org/2016/612}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.