[GGHZ14b] 
Fully Secure Functional Encryption without Obfuscation
By Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry
[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
By Dan Boneh and Mark Zhandry
In 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
By Dan Boneh, Brent Waters, and Mark Zhandry
In 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
By Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry
[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 Parameters
By Dennis Hofheinz, Tibor Jager, Dakshita Khurana, Amit Sahai, Brent Waters, and Mark Zhandry
[PDF]
[ePrint]
We introduce the notion of universal parameters as a method for generating the trusted parameters for many schemes from just
a single trusted setup. In such a scheme a trusted setup process will produce universal parameters U. These parameters can then
be combined with the description, d(·) of any particular cryptographic setup algorithm to produce parameters pd that can be used
by the cryptographic system associated with d. We give a solution in the random oracle model based on indistinguishability
obfuscation.
We demonstrate the versatility of universal parameters by showing how they give rise to applications such as
identitybased encryption and noninteractive identitybased key exchange. More generally, we observe that universal parameters
can also be seen as universal samplers, allowing a user to sample from arbitrary efficiently sampleable distributions.
@misc{HJK^{+}14, 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 Parameters}, misc = {Full version available at \url{http://eprint.iacr.org/2014/507}}, year = {2014} }

[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}, misc = {Full version available at \url{http://eprint.iacr.org/2014/301}}, 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 and Set Equality Problems}, misc = {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]

[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}, 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
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}, 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
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}, 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
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 2012}, misc = {Full version available at \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{BDF^{+}11, 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} }
