TY - GEN
T1 - Impossibility of Order-Revealing Encryption in Idealized Models
AU - Zhandry, Mark
AU - Zhang, Cong
N1 - Publisher Copyright:
© 2018, International Association for Cryptologic Research.
PY - 2018
Y1 - 2018
N2 - 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 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 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.
AB - 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 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 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.
KW - Black-box separations
KW - Generic group model
KW - Order-revealing encryption
KW - Random oracle model
UR - http://www.scopus.com/inward/record.url?scp=85120050518&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120050518&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-03810-6_5
DO - 10.1007/978-3-030-03810-6_5
M3 - Conference contribution
AN - SCOPUS:85120050518
SN - 9783030038090
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 129
EP - 158
BT - Theory of Cryptography - 16th International Conference, TCC 2018, Proceedings
A2 - Beimel, Amos
A2 - Dziembowski, Stefan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Conference on Theory of Cryptography, TCC 2018
Y2 - 11 November 2018 through 14 November 2018
ER -