We construct deterministic public key encryption secure for any constant number of arbitrarily correlated computationally unpredictable messages. Prior works required either random oracles or non-standard 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 =         {3--32},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {On {ELFs}, Deterministic Encryption, and
                     Correlated-Input Security},
    volume =        {11478},
    year =          {2019}
}

Order-revealing 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 parameter-hiding 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 Feng-Hao 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 =         {181--210},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Parameter-Hiding Order Revealing Encryption},
    volume =        {11272},
    year =          {2018}
}

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 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 =         {129--158},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Impossibility of Order-Revealing Encryption in
                     Idealized Models},
    volume =        {11240},
    year =          {2018}
}

An order-revealing 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 order-revealing 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 order-revealing 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~2016-A, Part~I},
    editor =        {Eyal Kushilevitz and Tal Malkin},
    month =         jan,
    pages =         {176--206},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Order-Revealing Encryption and the Hardness of
                     Private Learning},
    volume =        {9562},
    year =          {2016}
}

Deciding "greater-than" relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input 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 greater-than comparisons on encrypted data that provides the "best-possible" 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 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing k-bit 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 secret-key multi-input 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 k-bit 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 =         {563--594},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Semantically Secure Order-Revealing Encryption:
                     Multi-input Functional Encryption Without Obfuscation},
    volume =        {9057},
    year =          {2015}
}