The Relationship Between Idealized Models Under Computationally Bounded Adversaries


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 realworld
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 = {390419}, publisher = {Springer, Singapore}, series = {{LNCS}}, title = {The Relationship Between Idealized Models Under Computationally Bounded Adversaries}, volume = {14443}, year = {2023} }  
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies


We give the first black box lower bound for isogenybased 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 nonabelian) group action, the signature length
must be Ω(λ^{2}/\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 = {507531}, 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}, }  
Verifiable Quantum Advantage without Structure


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 oneway, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPAsecure public key encryption (the latter requiring the assumption of a classically CPAsecure 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 noninteractive, whereas for nonuniform adversaries the proofs are two message public coin. • Our results do not appear to contradict the AaronsonAmbanis 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 = {6974}, publisher = {{IEEE} Computer Society Press}, title = {Verifiable Quantum Advantage without Structure}, year = {2022} }  
To Label, or Not To Label (in Generic Groups)


Generic groups are an important tool for analyzing the feasibility and infeasibility
of groupbased cryptosystems. There are two distinct widespread 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 "multistage" games. • The existing generic group uninstantiability results do not apply to Maurer. We fill this gap with a new uninstantiability result. • We explain how the known black box separations between generic groups and identitybased encryption do not fully apply to Shoup, and resolve this by providing such a separation. • We give a new uninstantiability 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 = {6696}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {To Label, or Not To Label (in Generic Groups)}, volume = {13509}, year = {2022} }  
Augmented Random Oracles


We propose a new paradigm for justifying the security of random oraclebased
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: FiatShamir (FS),
FujisakiOkamoto (FO), and EncryptwithHash (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 = {3565}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Augmented Random Oracles}, volume = {13509}, year = {2022} }  
Redeeming Reset Indifferentiability and Applications to PostQuantum Security


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 postquantum symmetric key cryptography. In particular, we obtain a plausible postquantum random oracle that is a subsetproduct 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 = {518548}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Redeeming Reset Indifferentiability and Applications to PostQuantum Security}, volume = {13090}, year = {2021} }  
Classical vs Quantum Random Oracles


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 FiatShamir noninteractive arguments, FiatShamir signatures, and FullDomainHash 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}oisXavier Standaert}, month = oct, pages = {568597}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Classical vs Quantum Random Oracles}, volume = {12697}, year = {2021} }  
Indifferentiability for Public Key Cryptosystems


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; • Noninteractive 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 singlestage game and can be composed to operate in higherlevel protocols.
@inproceedings{C:ZhaZha20,
author = {Mark Zhandry and Cong Zhang}, booktitle = {CRYPTO~2020, Part~I}, editor = {Daniele Micciancio and Thomas Ristenpart}, month = aug, pages = {6393}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Indifferentiability for Public Key Cryptosystems}, volume = {12170}, year = {2020} }  
How to Record Quantum Queries, and Applications to Quantum Indifferentiability


The quantum random oracle model (QROM) has become the standard model in which to prove
the postquantum security of randomoraclebased 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 MerkleDamgard domain extender for hash functions. Given the threat posed by quantum computers and the push toward quantumresistant cryptosystems, our work represents an important tool for efficient postquantum cryptosystems.
@inproceedings{C:Zhandry19,
author = {Mark Zhandry}, booktitle = {CRYPTO~2019, Part~II}, editor = {Alexandra Boldyreva and Daniele Micciancio}, month = aug, pages = {239268}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {How to Record Quantum Queries, and Applications to Quantum Indifferentiability}, volume = {11693}, year = {2019} }  
The Distinction Between Fixed and Random Generators in GroupBased Assumptions


There is surprisingly little consensus on the precise role of the generator g in
groupbased 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 randomgenerator DDH (resp. CDH) is hard but fixedgenerator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications. • We find that seemingly tight generic lower bounds for the DiscreteLog and CDH problems with preprocessing (CorriganGibbs and Kogan, Eurocrypt 2018) are not tight in the subconstant 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 DDHlike assumptions in which exponents are drawn from lowentropy distributions are particularly sensitive to the fixed vs. randomgenerator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Eurocrypt 2018) used for nonmalleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixedgenerator assumption that suffices for a new construction of nonmalleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixedgenerator, lowentropy 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 = {801830}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {The Distinction Between Fixed and Random Generators in GroupBased Assumptions}, volume = {11693}, year = {2019} }  
Revisiting PostQuantum FiatShamir


The FiatShamir transformation is a useful approach to building noninteractive
arguments (of knowledge) in the random oracle model. Unfortunately, existing proof
techniques are incapable of proving the security of FiatShamir 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 FiatShamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on FiatShamir 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 = {326355}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Revisiting Postquantum {Fiat}{Shamir}}, volume = {11693}, year = {2019} }  
On Finding Quantum Multicollisions


A kcollision 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)(11/(2^k1))}) quantum queries are both necessary and
sufficient to achieve a kcollision with constant probability. This improves on both
the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first
nontrivial 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 = {189218}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {On Finding Quantum Multicollisions}, volume = {11478}, year = {2019}, }  
New Techniques for Obfuscating Conjunctions


A conjunction is a function f(x_{1},...,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 ReedSolomon 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 ReedSolomon 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 = {636666}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {New Techniques for Obfuscating Conjunctions}, volume = {11478}, year = {2019} }  
The MMap Strikes Back: Obfuscation and New Multilinear Maps Immune to CLT13 Zeroizing Attacks


We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et
al., CRYPTO 2013) that captures all known classical polynomialtime attacks on the
maps. We then show important applications of our model. First, we show that in our
model, several existing obfuscation and orderrevealing 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 rerandomization 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 = {513543}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {The {MMap} Strikes Back: Obfuscation and New Multilinear Maps Immune to {CLT13} Zeroizing Attacks}, volume = {11240}, 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} }  
Preventing Zeroizing Attacks on GGH15


The GGH15 multilinear maps have served as the foundation for a number of cuttingedge
cryptographic proposals. Unfortunately, many schemes built on GGH15 have been
explicitly broken by socalled "zeroizing attacks," which exploit leakage from honest
zerotest 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 zerotesting 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 UnAnnihilatability (BPUA) Assumption of Garg et al. [TCC 16B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexitytheoretic pBounded 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 = {544574}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Return of {GGH15}: Provable Security Against Zeroizing Attacks}, volume = {11240}, year = {2018} }  
Secure Obfuscation in a Weak Multilinear Map Model


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 zerotest 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 zerotest procedure. In particular, Miles, Sahai and Zhandry [Crypto'16] recently gave a polynomialtime 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 polynomialtime 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 polynomialtime 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^{1}.
@inproceedings{TCC:GMMSSZ16,
author = {Sanjam Garg and Eric Miles and Pratyay Mukherjee and Amit Sahai and Akshayaram Srinivasan and Mark Zhandry}, booktitle = {TCC~2016B, Part~II}, editor = {Martin Hirt and Adam D. Smith}, month = oct # {~/~} # nov, pages = {241268}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Secure Obfuscation in a Weak Multilinear Map Model}, volume = {9986}, year = {2016} }  
Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13


In this work, we put forward a new class of polynomialtime attacks on the original
multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomialtime attacks
on GGH13 were "zeroizing" attacks that generally required the availability of
lowlevel 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 nonlinear polynomials. Annihilation attacks can work in situations where there are no lowlevel encodings of zero. Using annihilation attacks, we give the first polynomialtime 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 = {629658}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over {GGH13}}, volume = {9815}, year = {2016} }  
PostZeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits


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 postzeroizing 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 genericmodel adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a lessconservative "prezeroizing" 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 postzeroizing 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 JeanS{\'{e}}bastien Coron}, month = may, pages = {764791}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Postzeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits}, volume = {9666}, year = {2016} }  
A Note on the Quantum Collision and Set Equality Problems


The results showing a quantum query complexity of Θ(N^{1/3}) for the
collision problem do not apply to random functions. The issues are twofold. 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 rto1 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 socalled permutationsymmetric 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} }  
Secure IdentityBased Encryption in the Quantum Random Oracle Model


We give the first proof of security for an identitybased 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
identitybased 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 semiconstant
distributions, we argue that the aforementioned cryptosystems are secure against
quantum adversaries.
@inproceedings{C:Zhandry12,
author = {Mark Zhandry}, booktitle = {CRYPTO~2012}, editor = {Reihaneh SafaviNaini and Ran Canetti}, month = aug, pages = {758775}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Secure IdentityBased Encryption in the Quantum Random Oracle Model}, volume = {7417}, year = {2012} }  
Random Oracles in a Quantum World


The interest in postquantum 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 postquantum security one needs to prove security in
the quantumaccessible random oracle model where the adversary can query the random
oracle with quantum state.
We begin by separating the classical and quantumaccessible 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 quantumaccessible random oracle model. We introduce the concept of a historyfree 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 postquantum proposals, including ones based on lattices, can be proven secure using historyfree 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 = {4169}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Random Oracles in a Quantum World}, volume = {7073}, year = {2011} } 