Impossibility of Order-Revealing Encryption in Idealized Models

Mark Zhandry, Cong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 16th International Conference, TCC 2018, Proceedings
EditorsAmos Beimel, Stefan Dziembowski
PublisherSpringer Science and Business Media Deutschland GmbH
Pages129-158
Number of pages30
ISBN (Print)9783030038090
DOIs
StatePublished - 2018
Event16th International Conference on Theory of Cryptography, TCC 2018 - Panaji, India
Duration: Nov 11 2018Nov 14 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11240 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Theory of Cryptography, TCC 2018
Country/TerritoryIndia
CityPanaji
Period11/11/1811/14/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Black-box separations
  • Generic group model
  • Order-revealing encryption
  • Random oracle model

Fingerprint

Dive into the research topics of 'Impossibility of Order-Revealing Encryption in Idealized Models'. Together they form a unique fingerprint.

Cite this