Jul 2014 
How to Avoid Obfuscation Using Witness PRFs
Oberwolfach Workshop
[slides]
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.

Jun 2014 
How to Avoid Obfuscation Using Witness PRFs
New York Area CryptoDay
[slides]
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.

Jun 2014 
Multiparty Key Exchange from Obfuscation
Columbia Seminar
[slides]
In this talk, we consider the problem of building noninteractive multiparty key exchange from obfuscation. Existing
protocols based on multilinear maps all require a trusted setup phase; in contrast, we seek to build key exchange without
trusted setup. We first give a simple protocol using obfuscation that achieves a static notion of security. When
moving to adaptive notions of security, however, the basic protocol is completely broken. The attack works by forcing
honest users to run malicious programs on their secrets, thus leaking the secrets to the adversary. We show how to modify
our protocol to maintain security even in the presence of such adaptive attacks.

May 2014 
How to Avoid Obfuscation Using Witness PRFs
UCLA Obfuscation Seminar
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.

Apr 2014 
How to Avoid Obfuscation Using Witness PRFs
Cryptography and Information Security Seminar at MIT
[slides]
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.

Apr 2014 
Multiparty Key Exchange, Efficient Traitor Tracing, and More
from Indistinguishability Obfuscation
UT Austin Algorithms and Computational Theory Seminar
[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.
* Joint Work with Dan Boneh

Apr 2014 
Multiparty Key Exchange and Broadcast Encryption from Software Obfuscation
Stanford Security Workshop
[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.
* Joint Work with Dan Boneh

Feb 2014 
Multiparty Key Exchange, Efficient Traitor Tracing, and More
from Indistinguishability Obfuscation
Harvard Theory of Computation Seminar and Princeton Theory Seminar
[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.
* Joint Work with Dan Boneh

Nov 2013 
Multiparty Key Exchange, Efficient Traitor Tracing, and More
from Indistinguishability Obfuscation
NYU Cryptography Seminar
[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.
Our proof of security for private broadcast encryption and traitor tracing introduces a new tool for iO
proofs: the construction makes use of a keyhomomorphic symmetric cipher which plays a crucial role in the
proof of security.
*Joint work with Dan Boneh.

Nov 2013 
Classical Cryptosystems in a Quantum World
IBM Watson
[slides]
Shor [Sho`96] demonstrated the power of quantum computing by showing how a quantum computer could break many of
the cryptosystems used today. The goal of postquantum cryptography is to protect classical cryptosystems from such
quantum computing attacks. In this talk, we go a step further and explore a world where all parties are using quantum
computers. Now the adversary may be able to mount an even stronger quantum channel attack, where he exchanges quantum
information with the honest parties. In this setting, we demonstrate that even schemes secure against the computational
power of a quantum computer may not be safe. I will discuss new security models associated with these kinds of attacks,
the difficulties faced when trying to construct secure schemes, and some of our techniques for overcoming these challenges.
*Joint work with Dan Boneh.

Oct 2013 
Quantum Computers and Cryptography
Quantum Computing Seminar at Hacker Dojo
[slides]
Quantum computers will have farreaching impacts on cryptography. Shor showed that many of the cryptosystems
used today can be broken using a quantum computer, and I will begin my talk by describing Shor's algorithm for
factoring integers. Next, I will give an overview of my research on attacking classical cryptosystems over a
quantum channel, showing that even schemes resistant to Shor's algorithm may be vulnerable to other forms of
quantum attack. On the positive side, quantum computing gives rise to the possibility of quantum key distribution
with unparalleled security guarantees, which I will cover at the end of the talk.

May 2013 
The Rank Method and Applications to PostQuantum Cryptography
Institute for Quantum Computing Colloquium at the University of Waterloo
[slides]
We present a new general quantum lowerbound technique called the Rank Method, and use it to solve certain
cryptographic problems in a quantum world. We define a new quantity for quantum algorithms, called the Rank,
and show how to bound the success probability of any quantum algorithm using its Rank. We then give exact
bounds for the Rank of quantum query algorithms. Combining these two bounds, we give an exact characterization
of the difficulty of the Quantum Oracle Interrogation Problem: given q quantum queries to a random oracle H,
produce k distinct input/output pairs of H, where k is greater than q.
We use this characterization
to construct classical cryptographic schemes that are secure, even when implemented on a quantum computer. In
this setting, a quantum adversary may be able to establish a quantum channel to attack the scheme. Proving
security then becomes much more difficult than in the classical case. Our characterization of the Quantum Oracle
Interrogation Problem allows us to give new quantum security proofs for message authentication codes and digital
signatures that were previously not known to be secure in our setting.
*Join work with Dan Boneh.

Apr 2013 
Beyond PostQuantum Cryptography
Cryptography and Information Security Seminar at MIT
[slides]
Postquantum cryptography attempts to build classical cryptosystems that are secure, even against a quantum
adversary. The security definitions are left mostly unchanged from the classical setting, keeping the
adversary’s interaction with the cryptosystem classical. This models a world where the adversary has a quantum
computer, but the honest parties remain classical.
In this talk, we look beyond postquantum
cryptography to a world where all parties have a quantum computer. Now an adversary may interact with the
honest parties in a quantum way, necessitating new security definitions that model these interactions. We
demonstrate how to construct pseudorandom functions, message authentication codes, signatures, and encryption
in the setting where the adversary can issue quantum queries to the parties involved. We develop new security
definitions for these settings and new proof techniques for arguing the security of our schemes.
*Join
work with Dan Boneh.

Dec 2012 
Beyond PostQuantum Cryptography
New York Area CryptoDay
[slides]
Postquantum cryptography attempts to build classical cryptosystems that are secure, even against a quantum
adversary. The security definitions are left mostly unchanged from the classical setting, keeping the
adversary’s interaction with the cryptosystem classical. This models a world where the adversary has a quantum
computer, but the honest parties remain classical.
In this talk, we look beyond postquantum
cryptography to a world where all parties have a quantum computer. Now an adversary may interact with the
honest parties in a quantum way, necessitating new security definitions that model these interactions. We
demonstrate how to construct pseudorandom functions and message authentication codes in the setting where the
adversary can issue quantum queries to the parties involved. We develop new security definitions for these
settings and new proof techniques for arguing the security of our schemes.
*Join work with Dan Boneh.
