Cryptology ePrint Archive: Report 2017/1001

Impossibility of Order-Revealing Encryption in Idealized Models

Mark Zhandry and Cong Zhang

Abstract: An Order-Revealing Encryption (ORE) scheme gives a public procedure by which two ciphertext can be compared to reveal the order of their underlying plaintexts. The ideal security notion for ORE is that only the order is revealed --- anything else, such as the distance between plaintexts, is hidden. The only known constructions of ORE achieving such ideal security are based on cryptographic multilinear maps, and are currently too impractical for real-world applications. In this work, we give evidence that building ORE from weaker tools may be hard. Indeed, we show black-box separations between ORE and most symmetric-key primitives, as well as public key encryption and anything else implied by generic groups in a black-box way. Thus, any construction of ORE must either (1) achieve weaker notions of security, (2) be based on more complicated cryptographic tools, or (3) require non-black-box techniques. This suggests that any ORE achieving ideal security will likely be somewhat inefficient. Central to our proof is an proof of impossibility for something we call information theoretic ORE, which has connections to tournament graphs and a theorem by Erdos. This impossibility proof will be useful for proving other black box separations for ORE.

Category / Keywords: Black-box separations, Order-revealing encryption, Random oracle, Generic group model

Date: received 6 Oct 2017, last revised 9 Oct 2017

Contact author: congresearch at gmail com, mzhandry@princeton edu

Available format(s): PDF | BibTeX Citation

Version: 20171013:171141 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]