On ELFs, Deterministic Encryption, and CorrelatedInput Security






We construct deterministic public key encryption secure for any constant number
of arbitrarily correlated computationally unpredictable messages. Prior works
required either random oracles or nonstandard knowledge assumptions. In contrast,
our constructions are based on the exponential hardness of DDH, which is plausible in
elliptic curve groups. Our central tool is a new trapdoored extremely lossy
function, which modifies extremely lossy functions by adding a trapdoor.
@inproceedings{EC:Zhandry19a,
author = {Mark Zhandry},
booktitle = {EUROCRYPT~2019, Part~III},
editor = {Yuval Ishai and Vincent Rijmen},
month = may,
pages = {332},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {On {ELFs}, Deterministic Encryption, and
CorrelatedInput Security},
volume = {11478},
year = {2019}
}

ParameterHiding Order Revealing Encryption






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{AC:CLOZZ18,
author = {David Cash and FengHao Liu and Adam O'Neill and
Mark Zhandry and Cong Zhang},
booktitle = {ASIACRYPT~2018, Part~I},
editor = {Thomas Peyrin and Steven Galbraith},
month = dec,
pages = {181210},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {ParameterHiding Order Revealing Encryption},
volume = {11272},
year = {2018}
}

Impossibility of OrderRevealing Encryption in Idealized Models






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 Erdős.
This impossibility proof will be useful for proving other black box separations for
ORE.
@inproceedings{TCC:ZhaZha18,
author = {Mark Zhandry and Cong Zhang},
booktitle = {TCC~2018, Part~II},
editor = {Amos Beimel and Stefan Dziembowski},
month = nov,
pages = {129158},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {Impossibility of OrderRevealing Encryption in
Idealized Models},
volume = {11240},
year = {2018}
}

OrderRevealing Encryption and the Hardness of Private Learning






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{TCC:BunZha16,
author = {Mark Bun and Mark Zhandry},
booktitle = {TCC~2016A, Part~I},
editor = {Eyal Kushilevitz and Tal Malkin},
month = jan,
pages = {176206},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {OrderRevealing Encryption and the Hardness of
Private Learning},
volume = {9562},
year = {2016}
}

Semantically Secure OrderRevealing Encryption: MultiInput Functional Encryption Without Obfuscation






Deciding "greaterthan" relations among data items just given their encryptions is at
the heart of search algorithms on encrypted data, most notably, noninteractive binary
search on encrypted data. Orderpreserving encryption provides one solution, but
provably provides only limited security guarantees. Twoinput functional encryption is
another approach, but requires the full power of obfuscation machinery and is
currently not implementable.
We construct the first implementable encryption system supporting greaterthan
comparisons on encrypted data that provides the "bestpossible" semantic security. In
our scheme there is a public algorithm that given two ciphertexts as input, reveals
the order of the corresponding plaintexts and nothing else. Our constructions are
inspired by obfuscation techniques, but do not use obfuscation. For example, to
compare two 16bit encrypted values (e.g., salaries or age) we only need a 9way
multilinear map. More generally, comparing kbit values requires only a (k/2+1)way
multilinear map. The required degree of multilinearity can be further reduced, but at
the cost of increasing ciphertext size. Beyond comparisons, our results give an
implementable secretkey multiinput functional encryption scheme for functionalities
that can be expressed as (generalized) branching programs of polynomial length and
width. Comparisons are a special case of this class, where for kbit inputs the
branching program is of length k+1 and width 4.
@inproceedings{EC:BLRSZZ15,
author = {Dan Boneh and Kevin Lewi and Mariana Raykova and
Amit Sahai and Mark Zhandry and Joe Zimmerman},
booktitle = {EUROCRYPT~2015, Part~II},
editor = {Elisabeth Oswald and Marc Fischlin},
month = apr,
pages = {563594},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {Semantically Secure OrderRevealing Encryption:
Multiinput Functional Encryption Without Obfuscation},
volume = {9057},
year = {2015}
}
