[Zha14] 
How to Avoid Obfuscation Using Witness PRFs
By Mark Zhandry
[PDF]
[ePrint]
Recently, program obfuscation has proven to be an extremely powerful tool and has been used to construct a variety of
cryptographic primitives with amazing properties. However, current candidate obfuscators are far from practical and
rely on unnatural hardness assumptions about multilinear maps. In this work, we bring several applications of obfuscation
closer to practice by showing that a weaker primitive called witness pseudorandom functions (witness PRFs) suffices.
Applications include multiparty key exchange without trusted setup, polynomiallymany hardcore bits for any oneway
function, and more. We then show how to instantiate witness PRFs from multilinear maps. Our witness PRFs are simpler and
more efficient than current obfuscation candidates, and involve very natural hardness assumptions about the underlying maps.
@misc{Zha14, author = {Mark Zhandry}, title = {How to Avoid Obfuscation Using Witness PRFs}, note = {Full version available at \url{http://eprint.iacr.org/2014/301}}, year = {2014} }

[BWZ14] 
Low Overhead Broadcast Encryption from Multilinear Maps
By Dan Boneh, Brent Waters, and Mark Zhandry
In CRYPTO 2014
[PDF]
[ePrint]
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}, booktitle = {Proceedings of Crypto}, title = {Efficient Broadcast Encryption from Multilinear Maps}, note = {Full version available at \url{http://eprint.iacr.org/2014/195}}, year = {2014} }

[Zha13] 
A Note on the Quantum Collision and Set Equality Problems
By Mark Zhandry
[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.
@misc{Zha13, author = {Mark Zhandry}, title = {A Note on the Quantum Collision Problem for Random Functions}, note = {Full version available at \url{http://arxiv.org/abs/1312.1027}}, year = {2013} }

[ABG^{+}13] 
DifferingInputs Obfuscation and Applications
By Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry
[PDF]
[ePrint]

[BZ14] 
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
By Dan Boneh and Mark Zhandry
In CRYPTO 2014
[PDF]
[ePrint]
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}, booktitle = {Proceedings of Crypto}, title = {Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation}, note = {Full version available at \url{http://eprint.iacr.org/2013/642}}, year = {2014} }

[BZ13b] 
Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World
By Dan Boneh and Mark Zhandry
In 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}, booktitle = {Proceedings of Crypto}, title = {Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World}, note = {Full version available at the Cryptology ePrint Archives: \url{http://eprint.iacr.org/2013/088}}, year = {2013} }

[BZ13a] 
QuantumSecure Message Authentication Codes
By Dan Boneh and Mark Zhandry
In 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}, booktitle = {Proceedings of Eurocrypt}, title = {QuantumSecure Message Authentication Codes}, note = {Full version available at the Electronic Colloquium on Computational Complexity: \url{http://eccc.hpiweb.de/report/2012/136}}, year = {2013} }

[Zha12b] 
How to Construct Quantum Random Functions
By Mark Zhandry
In 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}, booktitle = {Proceedings of FOCS}, title = {How to Construct Quantum Random Functions}, note = {Full version available at the Cryptology ePrint Archives: \url{http://eprint.iacr.org/2012/182/}}, year = {2012} }

[Zha12a] 
Secure IdentityBased Encryption in the Quantum Random Oracle Model
By Mark Zhandry
In 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}, note = {Full version available at the Cryptology ePrint Archives: \url{http://eprint.iacr.org/2012/076/}}, year = {2012} }

[BDF^{+}11] 
Random Oracles in a Quantum World
By Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry
In 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 {\"O}zg{\"u}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}, note = {Full version available at the Cryptology ePrint Archives: \url{http://eprint.iacr.org/2010/428/}}, year = {2011} }
