Practical Order-Revealing Encryption with Limited Leakage

Nathan Chenette, Kevin Lewi, Stephen A. Weis, and David J. Wu

Abstract

In an order-preserving encryption scheme, the encryption algorithm produces ciphertexts that preserve the order of their plaintexts. Order-preserving encryption schemes have been studied intensely in the last decade, and yet not much is known about the security of these schemes. Very recently, Boneh et al. (Eurocrypt 2015) introduced a generalization of order-preserving encryption, called order-revealing encryption, and presented a construction which achieves this notion with best-possible security. Because their construction relies on multilinear maps, it is too impractical for most applications and therefore remains a theoretical result. In this work, we build efficiently implementable order-revealing encryption from pseudorandom functions. We present the first efficient order-revealing encryption scheme which achieves a simulation-based security notion with respect to a leakage function that precisely quantifies what is leaked by the scheme. In fact, ciphertexts in our scheme are only about 1.6 times longer than their plaintexts. Moreover, we show how composing our construction with existing order-preserving encryption schemes results in order-revealing encryption that is strictly more secure than all preceding order-preserving encryption schemes.

Note: Full version of FSE 2016 paper.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2016
Keywords
order-revealing encryptionorder-preserving encryption
Contact author(s)
dwu4 @ cs stanford edu
History
2018-08-07: last of 5 revisions
See all versions
Short URL
https://ia.cr/2015/1125

CC BY

BibTeX

@misc{cryptoeprint:2015/1125,
author = {Nathan Chenette and Kevin Lewi and Stephen A.  Weis and David J.  Wu},
title = {Practical Order-Revealing Encryption with Limited Leakage},
howpublished = {Cryptology ePrint Archive, Paper 2015/1125},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1125}},
url = {https://eprint.iacr.org/2015/1125}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.