Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Black-box separationsOrder-revealing encryptionRandom oracle modelGeneric group model
Contact author(s)
mzhandry @ princeton edu
congresearch @ gmail com
History
2018-09-21: revised
2017-10-13: received
See all versions
Short URL
https://ia.cr/2017/1001
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1001,
      author = {Mark Zhandry and Cong Zhang},
      title = {Impossibility of Order-Revealing Encryption in Idealized Models},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1001},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1001}},
      url = {https://eprint.iacr.org/2017/1001}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.