Skip to content Skip to navigation
Qualifying Exam
12/20/2017 03:00 pm
CoRE A (301)

Impossibility of Order-Revealing Encryption in Idealized Model

Cong Zhang, Dept. of Computer Science

Examination Committee: Prof David Cash (chair); Prof Rebecca Wright; Prof Eric Allender; Prof Abdeslam Boularias


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.