Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects - both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processing attacks in which the adversary gains access to (classical or quantum) advice that is relevant to the particular construction. In this work, we show that indifferentiability is (generically) insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable (with pre-computation) from a random oracle. This yields the first (and tight) classical/quantum space-time trade-off for one-round sponge inversion.

@misc{EPRINT:CarPorZha24,
  author = {Joseph Carolan and Alexander Poremba and Mark Zhandry},
  title = {(Quantum) Indifferentiability and Pre-Computation},
  howpublished = {Cryptology {ePrint} Archive, Paper 2024/1727},
  year = {2024},
  url = {https://eprint.iacr.org/2024/1727}
}

Cryptographic group actions are a leading contender for post-quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum group actions, which consist of a group acting on a set of quantum states. We show the following results:

• In certain settings, statistical (even query bounded) security is impossible, analogously to post-quantum classical group actions.

• We construct quantum state group actions and prove that many computational problems that have been proposed by cryptographers hold it. Depending on the construction, our proofs are either unconditional, rely on LWE, or rely on the quantum random oracle model. While our analysis does not directly apply to classical group actions, we argue it gives at least a sanity check that there are no obvious flaws in the post-quantum assumptions made by cryptographers.

• Our quantum state group action allows for unifying two existing quantum money schemes: those based on group actions, and those based on non-collapsing hashes. We also explain how they can unify classical and quantum key distribution.

@misc{EPRINT:MutZha24,
    author = {Saachi Mutreja and Mark Zhandry},
    title = {Quantum State Group Actions},
    howpublished = {Cryptology ePrint Archive, Paper 2024/1636},
    year = {2024},
    note = {\url{https://eprint.iacr.org/2024/1636}},
    url = {https://eprint.iacr.org/2024/1636}
}

The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications.

In this work, we ask: which heuristics are closer to reality? Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly "milder" heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.

@inproceedings{AC:ZhaZha23,
    author =        {Cong Zhang and Mark Zhandry},
    booktitle =     {ASIACRYPT~2023, Part~VI},
    editor =        {Jian Guo and Ron Steinfeld},
    month =         dec,
    pages =         {390--419},
    publisher =     {Springer, Singapore},
    series =        {{LNCS}},
    title =         {The Relationship Between Idealized Models Under 
                     Computationally Bounded Adversaries},
    volume =        {14443},
    year =          {2023}
}

We give the first black box lower bound for isogeny-based protocols that can be described as group actions. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be Ω(λ²/\logλ). Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

@inproceedings{EC:BonGuaZha23,
    author =        {Dan Boneh and Jiaxin Guan and Mark Zhandry},
    booktitle =     {EUROCRYPT~2023, Part~V},
    editor =        {Carmit Hazay and Martijn Stam},
    month =         apr,
    pages =         {507--531},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {A Lower Bound on the Length of Signatures Based on
                     Group Actions and Generic Isogenies},
    volume =        {14008},
    year =          {2023},
}

We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1:

• There are NP search problems solvable by BQP machines but not BPP machines.

• There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.

• There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.

• Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.

By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

@inproceedings{FOCS:YamZha22,
    author =        {Takashi Yamakawa and Mark Zhandry},
    booktitle =     {63rd FOCS},
    editor =        {},
    month =         oct # {~/~} # nov,
    pages =         {69--74},
    publisher =     {{IEEE} Computer Society Press},
    title =         {Verifiable Quantum Advantage without Structure},
    year =          {2022}
}

We propose a new paradigm for justifying the security of random oracle-based protocols, which we call the Augmented Random Oracle Model (AROM). We show that the AROM captures a wide range of important random oracle impossibility results. Thus a proof in the AROM implies some resiliency to such impossibilities. We then consider three ROM transforms which are subject to impossibilities: Fiat-Shamir (FS), Fujisaki-Okamoto (FO), and Encrypt-with-Hash (EwH). We show in each case how to obtain security in the AROM by strengthening the building blocks or modifying the transform.

Along the way, we give a couple other results. We improve the assumptions needed for the FO and EwH impossibilities from indistinguishability obfuscation to circularly secure LWE; we argue that our AROM still captures this improved impossibility. We also demonstrate that there is no ``best possible'' hash function, by giving a pair of security properties, both of which can be instantiated in the standard model separately, which cannot be simultaneously satisfied by a single hash function.

@inproceedings{C:Zhandry22a,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2022, Part~III},
    editor =        {Yevgeniy Dodis and Thomas Shrimpton},
    month =         aug,
    pages =         {35--65},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Augmented Random Oracles},
    volume =        {13509},
    year =          {2022}
}

Generic groups are an important tool for analyzing the feasibility and in-feasibility of group-based cryptosystems. There are two distinct wide-spread versions of generic groups, Shoup's and Maurer's, the main difference being whether or not group elements are given explicit labels. The two models are often treated as equivalent. In this work, however, we demonstrate that the models are in fact quite different, and care is needed when stating generic group results:

• We show that numerous textbook constructions are not captured by Maurer, but are captured by Shoup. In the other direction, any construction captured by Maurer is captured by Shoup.

• For constructions that exist in both models, we show that security is equivalent for "single stage" games, but Shoup security is strictly stronger than Maurer security for some "multi-stage" games.

• The existing generic group un-instantiability results do not apply to Maurer. We fill this gap with a new un-instantiability result.

• We explain how the known black box separations between generic groups and identity-based encryption do not fully apply to Shoup, and resolve this by providing such a separation.

• We give a new un-instantiability result for the algebraic group model.

@inproceedings{C:Zhandry22b,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2022, Part~III},
    editor =        {Yevgeniy Dodis and Thomas Shrimpton},
    month =         aug,
    pages =         {66--96},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {To Label, or Not To Label (in Generic Groups)},
    volume =        {13509},
    year =          {2022}
}

Indifferentiability is used to analyze the security of constructions of idealized objects, such as random oracles or ideal ciphers. Reset indifferentiability is a strengthening of plain indifferentiability which is applicable in far more scenarios, but has largely been abandoned due to significant impossibility results and a lack of positive results. Our main results are:

• Under weak reset indifferentiability, ideal ciphers imply (fixed size) random oracles, and domain shrinkage is possible. We thus show reset indifferentiability is more useful than previously thought.

• We lift our analysis to the quantum setting, showing that ideal ciphers imply random oracles under quantum indifferentiability.

• Despite Shor's algorithm, we observe that generic groups are still meaningful quantumly, showing that they are quantumly (reset) indifferentiable from ideal ciphers; combined with the above, cryptographic groups yield post-quantum symmetric key cryptography. In particular, we obtain a plausible post-quantum random oracle that is a subset-product followed by two modular reductions.

@inproceedings{AC:Zhandry21,
    author =        {Mark Zhandry},
    booktitle =     {ASIACRYPT~2021, Part~I},
    editor =        {Mehdi Tibouchi and Huaxiong Wang},
    month =         dec,
    pages =         {518--548},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Redeeming Reset Indifferentiability and Applications to 
                     Post-Quantum Security},
    volume =        {13090},
    year =          {2021}
}

In this paper, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First, we introduce a notion of a proof of quantum access to a random oracle (PoQRO), which is a protocol to prove the capability to quantumly access a random oracle to a classical verifier. We observe that a proof of quantumness recently proposed by Brakerski et al. (TQC '20) can be seen as a PoQRO. We also give a construction of a publicly verifiable PoQRO relative to a classical oracle. Based on them, we construct digital signature and public key encryption schemes that are secure in the ROM but insecure in the QROM. In particular, we obtain the first examples of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption.

On the other hand, we give lifting theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example, our lifting theorems are applicable to Fiat-Shamir non-interactive arguments, Fiat-Shamir signatures, and Full-Domain-Hash signatures etc. We also discuss applications of our lifting theorems to quantum query complexity.

@inproceedings{EC:YamZha21,
    author =        {Takashi Yamakawa and Mark Zhandry},
    booktitle =     {EUROCRYPT~2021, Part~II},
    editor =        {Anne Canteaut and Fran\c{c}ois-Xavier Standaert},
    month =         oct,
    pages =         {568--597},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Classical vs Quantum Random Oracles},
    volume =        {12697},
    year =          {2021}
}

We initiate the study of indifferentiability for public key encryption and other public key primitives. Our main results are definitions and constructions of public key cryptosystems that are indifferentiable from ideal cryptosystems, in the random oracle model. Cryptosystems include:

• Public key encryption;
• Digital signatures;
• Non-interactive key agreement.

Our schemes are based on standard public key assumptions. By being indifferentiable from an ideal object, our schemes satisfy any security property that can be represented as a single-stage game and can be composed to operate in higher-level protocols.

@inproceedings{C:ZhaZha20,
    author =        {Mark Zhandry and Cong Zhang},
    booktitle =     {CRYPTO~2020, Part~I},
    editor =        {Daniele Micciancio and Thomas Ristenpart},
    month =         aug,
    pages =         {63--93},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Indifferentiability for Public Key Cryptosystems},
    volume =        {12170},
    year =          {2020}
}

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary's queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this "recording barrier". Our central observation is that when viewing the adversary's query and the oracle itself in the Fourier domain, an oracle query switches from writing to the adversary's space to writing to the oracle itself. This allows a reduction to simulate the oracle by simply recording information about the adversary's query in the Fourier domain.

We then use this new technique to show the indifferentiability of the Merkle-Damgard domain extender for hash functions. Given the threat posed by quantum computers and the push toward quantum-resistant cryptosystems, our work represents an important tool for efficient post-quantum cryptosystems.

@inproceedings{C:Zhandry19,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2019, Part~II},
    editor =        {Alexandra Boldyreva and Daniele Micciancio},
    month =         aug,
    pages =         {239--268},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {How to Record Quantum Queries, and Applications to
                     Quantum Indifferentiability},
                     volume =        {11693},
                     year =          {2019}
    }

The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting.

In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.

@inproceedings{C:LiuZha19,
    author =        {Qipeng Liu and Mark Zhandry},
    booktitle =     {CRYPTO~2019, Part~II},
    editor =        {Alexandra Boldyreva and Daniele Micciancio},
    month =         aug,
    pages =         {326--355},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Revisiting Post-quantum {Fiat}-{Shamir}},
    volume =        {11693},
    year =          {2019}
}

There is surprisingly little consensus on the precise role of the generator g in group-based assumptions such as DDH. Some works consider g to be a fixed part of the group description, while others take it to be random. We study this subtle distinction from a number of angles.

• In the generic group model, we demonstrate the plausibility of groups in which random-generator DDH (resp. CDH) is hard but fixed-generator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications.

• We find that seemingly tight generic lower bounds for the Discrete-Log and CDH problems with preprocessing (Corrigan-Gibbs and Kogan, Eurocrypt 2018) are not tight in the sub-constant success probability regime if the generator is random. We resolve this by proving tight lower bounds for the random generator variants; our results formalize the intuition that using a random generator will reduce the effectiveness of preprocessing attacks.

• We observe that DDH-like assumptions in which exponents are drawn from low-entropy distributions are particularly sensitive to the fixed- vs. random-generator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Eurocrypt 2018) used for non-malleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixed-generator assumption that suffices for a new construction of non-malleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixed-generator, low-entropy DDH (Canetti, Crypto 1997).

@inproceedings{C:BarMaZha19,
    author =        {James Bartusek and Fermi Ma and Mark Zhandry},
    booktitle =     {CRYPTO~2019, Part~II},
    editor =        {Alexandra Boldyreva and Daniele Micciancio},
    month =         aug,
    pages =         {801--830},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {The Distinction Between Fixed and Random Generators
                     in Group-Based Assumptions},
    volume =        {11693},
    year =          {2019}
}

A conjunction is a function f(x₁,...,x_n) = ∧_{i ∈ S} l_i where S ⊆ [n] and each l_i is x_i or ¬ x_i. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where |S| ≥ 0.226n. While conjunction obfuscation is known from LWE, these constructions rely on substantial technical machinery.

In this work, we conduct an extensive study of simple conjunction obfuscation techniques.

• We abstract the Bishop et al. scheme to obtain an equivalent yet more efficient "dual" scheme that handles conjunctions over exponential size alphabets. We give a significantly simpler proof of generic group security, which we combine with a novel combinatorial argument to obtain distributional VBB security for |S| of any size.

• If we replace the Reed-Solomon code with a random binary linear code, we can prove security from standard LPN and avoid encoding in a group. This addresses an open problem posed by Bishop et al.~to prove security of this simple approach in the standard model.

• We give a new construction that achieves information theoretic distributional VBB security and weak functionality preservation for |S| ≥ n - n^δ and δ < 1. Assuming discrete log and δ < 1/2, we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.

@inproceedings{EC:BLMZ19,
    author =        {James Bartusek and Tancr{\'e}de Lepoint and Fermi Ma and
                     Mark Zhandry},
    booktitle =     {EUROCRYPT~2019, Part~III},
    editor =        {Yuval Ishai and Vincent Rijmen},
    month =         may,
    pages =         {636--666},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {New Techniques for Obfuscating Conjunctions},
    volume =        {11478},
    year =          {2019}
}

A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, Θ(N^{(1/2)(1-1/(2^k-1))}) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

@inproceedings{EC:LiuZha19,
    author =        {Qipeng Liu and Mark Zhandry},
    booktitle =     {EUROCRYPT~2019, Part~III},
    editor =        {Yuval Ishai and Vincent Rijmen},
    month =         may,
    pages =         {189--218},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {On Finding Quantum Multi-collisions},
    volume =        {11478},
    year =          {2019},
}

We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et al., CRYPTO 2013) that captures all known classical polynomial-time attacks on the maps. We then show important applications of our model. First, we show that in our model, several existing obfuscation and order-revealing encryption schemes, when instantiated with CLT13 maps, are secure against known attacks under a mild algebraic complexity assumption used in prior work. These are schemes that are actually being implemented for experimentation. However, until our work, they had no rigorous justification for security.

Next, we turn to building constant degree multilinear maps on top of CLT13 for which there are no known attacks. Precisely, we prove that our scheme achieves the ideal security notion for multilinear maps in our weak CLT13 model, under a much stronger variant of the algebraic complexity assumption used above. Our multilinear maps do not achieve the full functionality of multilinear maps as envisioned by Boneh and Silverberg (Contemporary Mathematics, 2003), but do allow for re-randomization and for encoding arbitrary plaintext elements.

@inproceedings{TCC:MaZha18,
    author =        {Fermi Ma and Mark Zhandry},
    booktitle =     {TCC~2018, Part~II},
    editor =        {Amos Beimel and Stefan Dziembowski},
    month =         nov,
    pages =         {513--543},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {The {MMap} Strikes Back: Obfuscation and New
                     Multilinear Maps Immune to {CLT13} Zeroizing Attacks},
    volume =        {11240},
    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}
}

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called "zeroizing attacks," which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks.

In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a "GGH15 zeroizing model" as a new general framework which greatly generalizes known attacks.

Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

@inproceedings{TCC:BGMZ18,
    author =        {James Bartusek and Jiaxin Guan and Fermi Ma and
                     Mark Zhandry},
    booktitle =     {TCC~2018, Part~II},
    editor =        {Amos Beimel and Stefan Dziembowski},
    month =         nov,
    pages =         {544--574},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Return of {GGH15}: Provable Security Against
                     Zeroizing Attacks},
    volume =        {11240},
    year =          {2018}
}

All known candidate indistinguishibility obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available for iO candidates were in a generic model that only allows "honest" use of the multilinear map. Most notably, in this model the zero-test procedure only reveals whether an encoded element is 0, and nothing more.

However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zero-test procedure. In particular, Miles, Sahai and Zhandry [Crypto'16] recently gave a polynomial-time attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi [Eurocrypt'13], and also proposed a new "weak multilinear map model" that captures all known polynomial-time attacks on GGH13.

In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters [FOCS'13]. We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomial-time attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in NC¹.

@inproceedings{TCC:GMMSSZ16,
    author =        {Sanjam Garg and Eric Miles and Pratyay Mukherjee and
                     Amit Sahai and Akshayaram Srinivasan and
                     Mark Zhandry},
    booktitle =     {TCC~2016-B, Part~II},
    editor =        {Martin Hirt and Adam D. Smith},
    month =         oct # {~/~} # nov,
    pages =         {241--268},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Secure Obfuscation in a Weak Multilinear Map Model},
    volume =        {9986},
    year =          {2016}
}

In this work, we put forward a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks on GGH13 were "zeroizing" attacks that generally required the availability of low-level encodings of zero. Most significantly, such zeroizing attacks were not applicable to candidate indistinguishability obfuscation (iO) schemes. iO has been the subject of intense study.

To address this gap, we introduce annihilation attacks, which attack multilinear maps using non-linear polynomials. Annihilation attacks can work in situations where there are no low-level encodings of zero. Using annihilation attacks, we give the first polynomial-time cryptanalysis of candidate iO schemes over GGH13. More specifically, we exhibit two simple programs that are functionally equivalent, and show how to efficiently distinguish between the obfuscations of these two programs.

Given the enormous applicability of iO, it is important to devise iO schemes that can avoid attack.

@inproceedings{C:MilSahZha16,
    author =        {Eric Miles and Amit Sahai and Mark Zhandry},
    booktitle =     {CRYPTO~2016, Part~II},
    editor =        {Matthew Robshaw and Jonathan Katz},
    month =         aug,
    pages =         {629--658},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Annihilation Attacks for Multilinear Maps: Cryptanalysis 
                     of Indistinguishability Obfuscation over {GGH13}},
    volume =        {9815},
    year =          {2016}
}

Recent devastating attacks by Cheon et al.~[Eurocrypt'15] and others have highlighted significant gaps in our intuition about security in candidate multilinear map schemes, and in candidate obfuscators that use them. The new attacks, and some that were previously known, are typically called "zeroizing" attacks because they all crucially rely on the ability of the adversary to create encodings of 0.

In this work, we initiate the study of post-zeroizing obfuscation, and we present a construction for the special case of evasive functions. We show that our obfuscator survives all known attacks on the underlying multilinear maps, by proving that no encodings of 0 can be created by a generic-model adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a less-conservative "pre-zeroizing" model that does not capture recent attacks, or were proved secure relative to assumptions that are now known to be false.

To prove security, we introduce a new technique for analyzing polynomials over multilinear map encodings. This technique shows that the types of encodings an adversary can create are much more restricted than was previously known, and is a crucial step toward achieving post-zeroizing security. We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes.

@inproceedings{EC:BMSZ16,
    author =        {Saikrishna Badrinarayanan and Eric Miles and
                     Amit Sahai and Mark Zhandry},
    booktitle =     {EUROCRYPT~2016, Part~II},
    editor =        {Marc Fischlin and Jean-S{\'{e}}bastien Coron},
    month =         may,
    pages =         {764--791},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Post-zeroizing Obfuscation: New Mathematical Tools,
                     and the Case of Evasive Circuits},
    volume =        {9666},
    year =          {2016}
}

The results showing a quantum query complexity of Θ(N^1/3) for the collision problem do not apply to random functions. The issues are two-fold. First, the Ω(N^1/3) lower bound only applies when the range is no larger than the domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to r-to-1 functions, which are quite different from random functions.

Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N^1/3) holds for all interesting domain and range sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results.

Using our techniques, we also give an optimal Ω(N^1/3) lower bound for the set equality problem. This new lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

@article{QIC:Zhandry15, 
    author = {Zhandry, Mark}, 
    title = {A Note on the Quantum Collision and Set Equality Problems}, 
    year = {2015}, 
    issue_date = {May 2015}, 
    publisher = {Rinton Press, Incorporated}, 
    volume = {15}, 
    number = {7–8}, 
    journal = {Quantum Info. Comput.}, 
    month = may, 
    pages = {557–567}, 
    numpages = {11}
}

We give the first proof of security for an identity-based encryption scheme in the quantum random oracle model. This is the first proof of security for any scheme in this model that requires no additional assumptions. Our techniques are quite general and we use them to obtain security proofs for two random oracle hierarchical identity-based encryption schemes and a random oracle signature scheme, all of which have previously resisted quantum security proofs, even using additional assumptions. We also explain how to remove the extra assumptions from prior quantum random oracle model proofs. We accomplish these results by developing new tools for arguing that quantum algorithms cannot distinguish between two oracle distributions. Using a particular class of oracle distributions, so called semi-constant distributions, we argue that the aforementioned cryptosystems are secure against quantum adversaries.

@inproceedings{C:Zhandry12,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2012},
    editor =        {Reihaneh Safavi-Naini and Ran Canetti},
    month =         aug,
    pages =         {758--775},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Secure Identity-Based Encryption in the Quantum 
                     Random Oracle Model},
    volume =        {7417},
    year =          {2012}
}

The interest in post-quantum cryptography — classical systems that remain secure in the presence of a quantum adversary — has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum state.

We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore postquantum secure. We conclude with a rich set of open problems in this area.

@inproceedings{AC:BDFLSZ11,
    author =        {Dan Boneh and {\"O}zg{\"u}r Dagdelen and 
                     Marc Fischlin and Anja Lehmann and 
                     Christian Schaffner and Mark Zhandry},
    booktitle =     {ASIACRYPT~2011},
    editor =        {Dong Hoon Lee and Xiaoyun Wang},
    month =         dec,
    pages =         {41--69},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Random Oracles in a Quantum World},
    volume =        {7073},
    year =          {2011}
}