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 ciphertexts can be compared to reveal the order of their underlying plaintexts. The ideal security notion for ORE is that \emph{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 a proof of impossibility for something we call \emph{information theoretic ORE}, which has connections to tournament graphs and a theorem by Erdös. This impossibility proof will be useful for proving other black box separations for ORE.

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

Date: received 6 Oct 2017, last revised 21 Sep 2018

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

Available format(s): PDF | BibTeX Citation

Version: 20180921:151250 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]