Order-revealing encryption (ORE) is an important cryptographic primitive in
the study of searchable symmetric encryption because it allows for efficient
range queries, sorting, and threshold filtering on encrypted data.
The original notion of order-revealing encryption, which was called
"order-preserving encryption" (OPE), was proposed as a solution to allowing
for efficient range queries on encrypted data. However, OPE schemes inherently
leak a lot of additional information of their plaintexts, and are rather
insecure.
ORE offers a solution to range queries on encrypted data without suffering
from the same inherent limitations of OPE. Our goal is to construct and
analyze ORE in a provably secure manner, and also to study the applicability
of order-revealing encryption to real-world applications.
The ideal ORE schemes are:
A collection of encryptions should reveal no more than the ordering of
their plaintexts.
The size of an encryption should be about the same as the size of the
plaintext it encrypts.
Encryptions should be able to be computed in parallel and
independently of one another.
The scheme should rely only on simple, realizable, and efficient
cryptographic primitives.
An OPE scheme has the desirable property that its encryptions are numbers, and
that comparing two encryptions yields the ordering of the plaintexts they
encrypt. However, no such OPE scheme can be provably secure in a strong sense
(known as "best-possible" CPA security).
Here is a (non-exhaustive) chronological list of existing work in the realm of
OPE and ORE.
SIGMOD 2004
Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu
CRYPTO 2009
Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O’Neill
Media Forensics and Security 2009
Wenjun Lu, Ashwin Swaminathan, Avinash L. Varna, and Min Wu
EUROCRYPT 2015
Dan Boneh, Kevin Lewi, Mariana Raykova, Amit Sahai, Mark Zhandry, and
Joe Zimmerman
FSE 2016
Nathan Chenette, Kevin Lewi, Stephen A. Weis, and David J. Wu
