Paper 2016/661

Reducing the Leakage in Practical Order-Revealing Encryption

David Cash, Feng-Hao Liu, Adam O'Neill, and Cong Zhang


We study practical order-revealing encryption (ORE) with a well-defined leakage profile (the information revealed about the plaintexts from their ciphertexts), a direction recently initiated by Chenette, Lewi, Weis, and Wu (CLWW). ORE, which allows public comparison of plaintext order via their ciphertexts, is a useful tool in the design of secure outsourced database systems. We first show a general construction of ORE with reduced leakage as compared to CLWW, by combining ideas from their scheme with a new type of ''property-preserving'' hash function. We then show how to construct such a hash function efficiently based on bilinear maps. Our resulting ORE scheme is fairly practical: for n-bit plaintexts, ciphertexts consists of about 4n group elements, and order comparison requires about n^2 pairings. The leakage is, roughly speaking, the ''equality pattern'' of the most-significant differing bits, whereas CLWW's is the location and values of the most-significant differing bits. We also provide a generalization of our scheme that improves the leakage and/or efficiency. To analyze the quality of our leakage profile, we show several additional results. In particular, we show that order-\emph{preserving} (OPE) encryption, an important special case of ORE scheme in which ciphertexts are ordered, cannot be secure wrt.our leakage profile. This implies that our ORE scheme is the first one without multilinear maps that is proven secure wrt.a leakage profile unachievable by OPE. We also also show that our generalized scheme meets a ''semantically meaningful'' one-wayness notion that schemes with the leakage of CLWW do not.

Available format(s)
Publication info
Preprint. Minor revision.
Contact author(s)
cz200 @ cs rutgers edu
david cash @ cs rutgers edu
adam @ cs georgetown edu
fenghao liu @ fau edu
2016-06-28: received
Short URL
Creative Commons Attribution


      author = {David Cash and Feng-Hao Liu and Adam O'Neill and Cong Zhang},
      title = {Reducing the Leakage in Practical Order-Revealing Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/661},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.