[Zha15] 
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{Zha15, 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} }

[BLR^{+}15] 
Semantically Secure OrderRevealing Encryption: MultiInput Functional Encryption Without Obfuscation
EuroCrypt 2015
[PDF]
[ePrint]

[BMSZ15] 
PostZeroizing Obfuscation: The case of Evasive Circuits
[PDF]
[ePrint]
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.
@misc{BMSZ15, author = {Saikrishna Badrinarayanan and Eric Miles and Amit Sahai and Mark Zhandry}, title = {PostZeroizing Obfuscation: The case of Evasive Circuits}, misc = {Full version available at \url{http://eprint.iacr.org/2015/167}}, year = {2015} }

[SZ14] 
Obfuscating LowRank Matrix Branching Programs
Subsumed by [BMSZ15]
[PDF]
[ePrint]
In this work, we seek to extend the capabilities of the “core obfuscator” from the work of Garg, Gentry, Halevi, Raykova, Sahai,
and Waters (FOCS 2013), and all subsequent works constructing generalpurpose obfuscators. This core obfuscator builds upon
approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of
such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this
limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot
“forget.” At a technical level, this limitation arises in previous work because all previous work relies on Kilian’s statistical
simulation theorem, which is false when applied to matrices not of full rank.
In our work, we build the first core
obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our
obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian’s statistical simulation
theorem. Furthermore, our obfuscator achieves two other notable advances over previous work:
• Our construction allows for nonsquare matrices of arbitrary dimensions. We also show that this flexibility yields
concrete efficiency gains.
• Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit
of output.
Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains
even in applications not directly using obfuscation.
@misc{SZ14, author = {Amit Sahai and Mark Zhandry}, title = {Obfuscating LowRank Matrix Branching Programs}, misc = {Full version available at \url{http://eprint.iacr.org/2014/773}}, year = {2014} }

[Zha14b] 
Adaptively Secure Broadcast Encryption with Small System Parameters
[PDF]
[ePrint]
We build the first publickey broadcast encryption system that simultaneously achieves adaptive security against arbitrary number
of colluders, has small system parameters, and has a security proof based on noninteractive falsifiable assumptions. Our scheme is
built from composite order multilinear maps and enjoys a ciphertext overhead, private key size, and public key size that are are all
polylogarithmic in the total number of users. Previous broadcast schemes with similar parameters are either proven secure in a weaker
static model, or rely on powerful tools such as program obfuscation and involve nonfalsifiable assumptions.
@misc{Zha14b, author = {Mark Zhandry}, title = {Adaptively Secure Broadcast Encryption with Small System Parameters}, misc = {Full version available at \url{http://eprint.iacr.org/2014/757}}, year = {2014} }

[GGHZ14b] 
Fully Secure Functional Encryption without Obfuscation
[PDF]
[ePrint]
Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in
turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but
with an exponential loss in the security reduction. Additionally these schemes are proved in an unrealistic selective security
model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full
security can be obtained but at the cost of an exponential loss in the security reduction.
In this work, we overcome the above limitations and realize a fully secure functional encryption scheme without using indistinguishability
obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on multilinear maps.
@misc{GGHZ14b, author = {Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry}, title = {Fully Secure Functional Encryption without Obfuscation}, misc = {Full version available at \url{http://eprint.iacr.org/2014/666}}, year = {2014} }

[BZ14] 
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
CRYPTO 2014
[PDF]
[ePrint]
[slides]
In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange,
efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting
properties that have not been achievable before:
• Our multiparty noninteractive key exchange protocol does not require a trusted setup. Moreover,
the size of the published value from each user is independent of the total number of users.
• Our broadcast encryption schemes support distributed setup, where users choose their own
secret keys rather than be given secret keys by a trusted entity. The broadcast ciphertext size is
independent of the number of users.
• Our traitor tracing system is fully collusion resistant with short ciphertexts, secret keys,
and public key. Ciphertext size is logarithmic in the number of users and secret key size is independent
of the number of users. Our public key size is polylogarithmic in the number of users. The recent
functional encryption system of Garg, Gentry, Halevi, Raykova, Sahai, and Waters also leads to a traitor
tracing scheme with similar ciphertext and secret key size, but the construction in this paper is simpler
and more direct. These constructions resolve an open problem relating to differential privacy.
• Generalizing our traitor tracing system gives a private broadcast encryption scheme (where broadcast
ciphertexts reveal minimal information about the recipient set) with optimal size ciphertext.
Several of our proofs of security introduce new tools for proving security using indistinguishability obfuscation.
@inproceedings{BZ14, author = {Dan Boneh and Mark Zhandry}, title = {Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation}, booktitle = {Proceedings of CRYPTO 2014}, misc = {Full version available at \url{http://eprint.iacr.org/2013/642}}, year = {2014} }

[BWZ14] 
Low Overhead Broadcast Encryption from Multilinear Maps
CRYPTO 2014
[PDF]
[ePrint]
[slides]
We use multilinear maps to provide a solution to the longstanding problem of publickey broadcast encryption where all
parameters in the system are small. In our constructions, ciphertext overhead, private key size, and public key size are
all polylogarithmic in the total number of users. The systems are fully collusionresistant against any number of colluders.
All our systems are based on an O(log N)way multilinear map to support a broadcast system for N users. We present three
constructions based on different types of multilinear maps and providing different security guarantees. Our systems naturally
give identitybased broadcast systems with short parameters.
@inproceedings{BWZ14, author = {Dan Boneh and Brent Waters and Mark Zhandry}, title = {Low Overhead Broadcast Encryption from Multilinear Maps}, booktitle = {Proceedings of CRYPTO 2014}, misc = {Full version available at \url{http://eprint.iacr.org/2014/195}}, year = {2014} }

[GGHZ14a] 
Fully Secure Attribute Based Encryption from Multilinear Maps
[PDF]
[ePrint]
We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies
expressible as polynomialsize circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic
selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full
security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary's
target string x^*, incurring a 2^{x^*} loss factor in the tightness of the reduction.
At a very high level, our basic ABE scheme is reminiscent of Yao's garbled circuits, with 4 gadgets per gate of the circuit, but
where the decrypter in our scheme puts together the appropriate subset of gate gadgets like puzzle pieces by using a cryptographic
multilinear map to multiply the pieces together. We use a novel twist of Waters' dual encryption methodology to prove the full
security of our scheme. Most importantly, we show how to preserve the delicate informationtheoretic argument at the heart of Waters'
dual system by enfolding it in an informationtheoretic argument similar to that used in Yao's garbled circuits.
@misc{GGHZ14a, author = {Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry}, title = {Fully Secure Attribute Based Encryption from Multilinear Maps}, misc = {Full version available at \url{http://eprint.iacr.org/2014/622}}, year = {2014} }

[HJK^{+}14] 
How to Generate and use Universal Samplers
[PDF]
[ePrint]
The random oracle is an idealization that allows to model a hash function as an oracle that will output a uniformly random
string given an input. We introduce the notion of universal sampler scheme as a method sampling securely from
arbitrary distributions.
We first motivate such a notion by describing several applications including generating
the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal
sampler by showing how they give rise to applications such as identitybased encryption and multiparty key exchange.
We give a solution in the random oracle model based on indistinguishability obfuscation. At the heart of our construction and
proof is a new technique we call "delayed backdoor programming".
@misc{HJKSWZ14, author = {Dennis Hofheinz and Tibor Jager and Dakshita Khurana and Amit Sahai and Brent Waters and Mark Zhandry}, title = {How to Generate and use Universal Samplers}, misc = {Full version available at \url{http://eprint.iacr.org/2014/507}}, year = {2014} }

[Zha14a] 
How to Avoid Obfuscation Using Witness PRFs
[PDF]
[ePrint]
We propose a new cryptographic primitive called witness pseudorandom functions (witness PRFs). Witness PRFs are related to
witness encryption, but appear strictly stronger: we show that witness PRFs can be used for applications such as multiparty key
exchange without trsuted setup, polynomiallymany hardcore bits for any oneway function, and several others that were previously
only possible using obfuscation. Current candidate obfuscators are far from practical and typically rely on unnatural hardness
assumptions about multilinear maps. We give a construction of witness PRFs from multilinear maps that is simpler and much more
efficient than current obfuscation candidates, thus bringing several applications of obfuscation closer to practice. Our construction
relies on new but very natural hardness assumptions about the underlying maps that appear to be resistant to a recent line of attacks.
@misc{Zha14a, author = {Mark Zhandry}, title = {How to Avoid Obfuscation Using Witness PRFs}, misc = {Full version available at \url{http://eprint.iacr.org/2014/301}}, year = {2014} }

[ABG^{+}13] 
DifferingInputs Obfuscation and Applications
[PDF]
[ePrint]

[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} }

[Zha12b] 
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{Zha12b, 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} }

[Zha12a] 
Secure IdentityBased Encryption in the Quantum Random Oracle Model
CRYPTO 2012
[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.
@inproceedings{Zha12a, author = {Mark Zhandry}, title = {Secure IdentityBased Encryption in the Quantum Random Oracle Model}, booktitle = {Proceedings of CRYPTO 2012}, misc = {Full version available at \url{http://eprint.iacr.org/2012/076}}, 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} }
