[Zha19c] 
How to Record Quantum Queries, and Applications to Quantum Indifferentiability
CRYPTO 2019, QCrypt 2019 (Invited)
[PDF]
[ePrint]
[slides]
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{Zha19c, author = {Mark Zhandry}, title = {How to Record Quantum Queries, and Applications to Quantum Indifferentiability}, booktitle = {Proceedings of QCrypt 2019}, misc = {Full version available at \url{https://eprint.iacr.org/2018/276}}, year = {2019} }

[LZ19b] 
Revisiting PostQuantum FiatShamir
By  Qipeng Liu and Mark Zhandry 
CRYPTO 2019
[PDF]
[ePrint]
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{LZ19b, author = {Qipeng Liu and Mark Zhandry}, title = {Revisiting PostQuantum FiatShamir}, booktitle = {Proceedings of CRYPTO 2019}, misc = {Full version available at \url{https://eprint.iacr.org/2019/262}}, year = {2019} }

[LZ19a] 
On Finding Quantum Multicollisions
By  Qipeng Liu and Mark Zhandry 
EUROCRYPT 2019
[PDF]
[arXiv]
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{LZ19a, author = {Qipeng Liu and Mark Zhandry}, title = {On Finding Quantum Multicollisions}, booktitle = {Proceedings of EUROCRYPT 2019}, misc = {Full version available at \url{https://arxiv.org/abs/1811.05385}}, year = {2019} }

[Zha19b] 
Quantum Lightning Never Strikes the Same State Twice
EUROCRYPT 2019 (Best Paper Award)
[PDF]
[ePrint]
[slides]
Public key quantum money can be seen as a version of the quantum nocloning theorem that holds even when the quantum states can be verified by the adversary. In this work,
investigate quantum lightning, a formalization of "collisionfree quantum money" defined by Lutomirski et al. [ICS`10], where nocloning holds even when the
adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results:
• We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of
entropy, to completely decentralized cryptocurrency without a blockchain, where transactions is instant and local.
• We give winwin results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of
security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this gives some indication that natural schemes do attain
strong security guarantees.
• We construct quantum lightning under the assumed multicollision resistance of random degree2 systems of polynomials. Our construction is inspired by our winwin
result for hash functions, and yields the first plausible standard model instantiation of a \emph{noncollapsing} collision resistant hash function. This improves on a
result of Unruh [Eurocrypt`16] that requires a quantum oracle.
•We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC`12] with indistinguishability obfuscation that is secure against quantum
computers yields a secure quantum money scheme. This construction can be seen as an instance of our winwin result for signatures, giving the first separation between two
security notions for signatures from the literature.
Thus, we provide the first constructions of public key quantum money from several cryptographic assumptions. Along the way, we develop several new techniques including a
new precise variant of the nocloning theorem.
@inproceedings{Zha19b, author = {Mark Zhandry}, title = {Quantum Lightning Never Strikes the Same State Twice}, booktitle = {Proceedings of EUROCRYPT 2019}, misc = {Full version available at \url{https://eprint.iacr.org/2017/1080}}, year = {2019} }

[GYZ17] 
New Security Notions and Feasibility Results for Authentication of Quantum Data
QCrypt 2016, CRYPTO 2017
[PDF]
[arXiv]
We give a new class of security definitions for authentication in the quantum setting. Our definitions capture and strengthen several existing definitions,
including superposition attacks on classical authentication, as well as full authentication of quantum data. We argue that our definitions resolve some of
the shortcomings of existing definitions.
We then give several feasibility results for our strong definitions. As a consequence, we obtain several interesting results, including:
(1) the classical CarterWegman authentication scheme with 3universal hashing is secure against superposition attacks, as well as adversaries with quantum
side information;
(2) quantum authentication where the entire key can be reused if verification is successful;
(3) conceptually simple constructions of quantum authentication; and
(4) a conceptually simple QKD protocol.
@inproceedings{GYZ17, author = {Sumegha Garg and Henry Yuen and Mark Zhandry}, title = {New Security Notions and Feasibility Results for Authentication of Quantum Data}, booktitle = {Proceedings of CRYPTO 2017}, misc = {Full version available at \url{https://arxiv.org/abs/1607.07759}}, year = {2017} }

[Zha16c] 
A Note on QuantumSecure PRPs
[PDF]
[ePrint]
We show how to construct pseudorandom permutations (PRPs) that remain secure even if the adversary can query the permutation on a quantum superposition of inputs.
Such PRPs are called quantumsecure. Our construction combines a quantumsecure pseudorandom function together with constructions of classical
format preserving encryption. By combining known results, we obtain the first quantumsecure PRP in this model whose security relies only on the existence of oneway
functions. Previously, to the best of the author`s knowledge, quantum security of PRPs had to be assumed, and there were no prior security reductions to simpler
primitives, let alone oneway functions.
@misc{Zha16c, author = {Mark Zhandry}, title = {A Note on QuantumSecure PRPs}, misc = {Full version available at \url{https://eprint.iacr.org/2016/1076}}, year = {2016} }

[Zha15c] 
Quantum Oracle Classification: The Case of Group Structure
[PDF]
[arXiv]
The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining
the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems.
In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which
induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space.
Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation;
polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have
other applications.
We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is,
we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality.
Unfortunately, solving this counting problem in general is a nontrivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the
existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic
message authentication codes in the quantum setting.
@misc{Zha15c, author = {Mark Zhandry}, title = {Quantum Oracle Classification: The Case of Group Structure}, misc = {Full version available at \url{http://arxiv.org/abs/1510.08352}}, year = {2015} }

[Zha15b] 
Secure IdentityBased Encryption in the Quantum Random Oracle Model
CRYPTO 2012, International Journal of Quantum Information
[PDF]
[ePrint]
[slides]
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.
@article{Zha15b, author = {Mark Zhandry}, title = {Secure IdentityBased Encryption in the Quantum Random Oracle Model}, journal = {International Journal of Quantum Information}, volume = {13}, number = {4}, misc = {Full version available at \url{http://eprint.iacr.org/2012/076}}, year = {2015} }

[Zha15a] 
A Note on the Quantum Collision and Set Equality Problems
Quantum Information and Computation
[PDF]
[arXiv]
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{Zha15a, author = {Mark Zhandry}, title = {A Note on the Quantum Collision and Set Equality Problems}, journal = {Quantum Information and Computation}, volume = {15}, number = {7\& 8}, misc = {Full version available at \url{http://arxiv.org/abs/1312.1027}}, year = {2015} }

[BZ13b] 
Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World
CRYPTO 2013
[PDF]
[ePrint]
[slides]
We initiate the study of quantumsecure digital signatures and quantum chosen ciphertext
security. In the case of signatures, we enhance the standard chosen message query model by allowing the
adversary to issue quantum chosen message queries: given a superposition of messages, the adversary
receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary
to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary
receives a superposition of their decryptions. These adversaries model a natural postquantum environment
where endusers sign messages and decrypt ciphertexts on a personal quantum computer.
We construct
classical systems that remain secure when exposed to such quantum queries. For signatures we construct two
compilers that convert classically secure signatures into signatures secure in the quantum setting and apply
these compilers to existing postquantum signatures. We also show that standard constructions such as Lamport
onetime signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving
signatures whose quantum security is based on generic assumptions. For encryption, we define security under
quantum chosen ciphertext attacks and present both publickey and symmetrickey constructions.
@inproceedings{BZ13b, author = {Dan Boneh and Mark Zhandry}, title = {Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World}, booktitle = {Proceedings of CRYPTO 2013}, misc = {Full version available at \url{http://eprint.iacr.org/2013/088}}, year = {2013} }

[BZ13a] 
QuantumSecure Message Authentication Codes
EUROCRYPT 2013
[PDF]
[ePrint]
[slides]
We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against
a quantum chosen message attack. These chosen message attacks model a quantum adversary's
ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a
quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder
to prove than its classical analogue. Next, we show that a variant of CarterWegman MACs can be proven to
be quantum secure. Unlike the classical settings, we present an attack showing that a pairwise independent
hash family is insufficient to construct a quantum secure onetime MAC, but we prove that a fourwise
independent family is sufficient for onetime security.
@inproceedings{BZ13a, author = {Dan Boneh and Mark Zhandry}, title = {QuantumSecure Message Authentication Codes}, booktitle = {Proceedings of EUROCRYPT 2013}, misc = {Full version available at \url{http://eprint.iacr.org/2012/606}}, year = {2013} }

[Zha12] 
How to Construct Quantum Random Functions
FOCS 2012
[PDF]
[ePrint]
[slides]
In the presence of a quantum adversary, there are two possible definitions of security for a
pseudorandom function. The first, which we call standardsecurity, allows the adversary to be
quantum, but requires queries to the function to be classical. The second, quantumsecurity, allows
the adversary to query the function on a quantum superposition of inputs, thereby giving the adversary
a superposition of the values of the function at many inputs at once. Existing proof techniques for
proving the security of pseudorandom functions fail when the adversary can make quantum queries. We
give the first quantumsecurity proofs for pseudorandom functions by showing that some classical
constructions of pseudorandom functions are quantumsecure. Namely, we show that the standard
constructions of pseudorandom functions from pseudorandom generators or pseudorandom synthesizers are
secure, even when the adversary can make quantum queries. We also show that a direct construction from
lattices is quantumsecure. To prove security, we develop new tools to prove the indistinguishability of
distributions under quantum queries.
In light of these positive results, one might hope that all
standardsecure pseudorandom functions are quantumsecure. To the contrary, we show a separation: under
the assumption that standardsecure pseudorandom functions exist, there are pseudorandom functions secure
against quantum adversaries making classical queries, but insecure once the adversary can make quantum queries.
@inproceedings{Zha12, author = {Mark Zhandry}, title = {How to Construct Quantum Random Functions}, booktitle = {Proceedings of FOCS 2012}, misc = {Full version available at \url{http://eprint.iacr.org/2012/182}}, year = {2012} }

[BDF^{+}11] 
Random Oracles in a Quantum World
AsiaCrypt 2011
[PDF]
[ePrint]
[slides]
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{BDFLSZ11, author = {Dan Boneh and Özgür Dagdelen and Marc Fischlin and Anja Lehmann and Christian Schaffner and Mark Zhandry}, title = {Random Oracles in a Quantum World}, booktitle = {Proceedings of AsiaCrypt 2011}, misc = {Full version available at \url{http://eprint.iacr.org/2010/428/}}, year = {2011} }
