Cryptology ePrint Archive: Report 2015/1125

Practical Order-Revealing Encryption with Limited Leakage

Nathan Chenette and Kevin Lewi and 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.

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

Original Publication (with major differences): IACR-FSE-2016

Date: received 20 Nov 2015, last revised 6 Aug 2018

Contact author: dwu4 at cs stanford edu

Available format(s): PDF | BibTeX Citation

Note: Full version of FSE 2016 paper.

Version: 20180807:011258 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]