[CLO^{+}18] 
ParameterHiding Order Revealing Encryption
AsiaCrypt 2018
[PDF]
[ePrint]
Orderrevealing encryption (ORE) is a popular primitive for outsourcing encrypted databases, as it allows for efficiently performing range queries over encrypted data.
Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides
little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the
mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameterhiding ORE, which maintains the
secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.
@inproceedings{CLOZZ18, author = {David Cash and FengHao Liu and Adam O'Neill and Mark Zhandry and Cong Zhang}, title = {ParameterHiding Order Revealing Encryption}, booktitle = {Proceedings of AsiaCrypt 2018}, misc = {Full version available at \url{https://eprint.iacr.org/2018/698}}, year = {2018} }

[ZZ18] 
Impossibility of OrderRevealing Encryption in Idealized Models
By  Mark Zhandry and Cong Zhang 
TCC 2018
[PDF]
[ePrint]
An OrderRevealing 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 realworld applications. In this work, we give evidence
that building ORE from weaker tools may be hard. Indeed, we show blackbox separations between ORE and most symmetrickey primitives, as well as public key encryption and
anything else implied by generic groups in a blackbox 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 nonblackbox 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 Erdoös.
This impossibility proof will be useful for proving other black box separations for ORE.
@inproceedings{ZZ18, author = {Mark Zhandry and Cong Zhang}, title = {Impossibility of OrderRevealing Encryption in Idealized Models}, booktitle = {Proceedings of TCC 2018}, misc = {Full version available at \url{https://eprint.iacr.org/2017/1001}}, year = {2018} }

[BZ16] 
OrderRevealing Encryption and the Hardness of Private Learning
TCC 2016A
[PDF]
[arXiv]
An orderrevealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying
plaintexts. We show how to use orderrevealing encryption to separate computationally efficient PAC learning from efficient (ε,δ)differentially
private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially
private. This answers a question of Kasiviswanathan et al. (FOCS `08, SIAM J. Comput. `11).
To prove our result, we give a generic transformation from an orderrevealing encryption scheme into one with strongly correct comparison, which enables the
consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.
@inproceedings{BZ16, author = {Mark Bun and Mark Zhandry}, title = {OrderRevealing Encryption and the Hardness of Private Learning}, booktitle = {Proceedings of TCC 2016A}, misc = {Full version available at \url{http://arxiv.org/abs/1505.00388}}, year = {2016} }

[BLR^{+}15] 
Semantically Secure OrderRevealing Encryption: MultiInput Functional Encryption Without Obfuscation
EUROCRYPT 2015
[PDF]
[ePrint]
