Dec 2016 
Quantum Oracle Classification: The Case of Group Structure
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.
Princeton PACM Seminar

Nov 2016 
The Magic of ELFs
We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a
polynomialsized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary),
the adversary cannot distinguish the injective case from the case of image size r.
We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show
how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomiallymany hardcore bits for any oneway function. Such applications were
previously known from strong knowledge assumptions — for example polynomiallymany hardcore bits were only know from differing inputs obfuscation, a notion whose
plausibility has been seriously challenged. We also use ELFs to build a simple hash function with output intractability, a new notion we define that may be useful for
generating common reference strings.
Next, we give a construction of ELFs relying on the exponential hardness of the decisional DiffieHellman problem, which is plausible in elliptic curve groups. Combining
with the applications above, our work gives several practical constructions relying on qualitatively different — and arguably better — assumptions than prior works.
TCS+

Nov 2016 
Obfuscation and Weak Multilinear Maps
Given the significance of obfuscation to cryptography, it is crucial to understand its security. Obfuscation is currently constructed using an object called multilinear maps.
Unfortunately, multilinear maps have been subject to many attacks, leaving almost all applications of multilinear maps completely broken. One of the main holdouts is program
obfuscation, though in light of these attacks all previous arguments for the security of obfuscation are unconvincing. Is obfuscation not yet broken simply because it is
complicated and hard to analyze? Or is there some fundamental reason why known attacks cannot be applied to obfuscation?
In this talk, I will discuss two recent works
that show, in the case of obfuscation using GGH13 multilinear maps, the answer is somewhere in the middle. First, I will show a polynomial attack that applies to several
existing obfuscation candidates, even those proven secure in the "generic multilinear map model." Then, I will demonstrate a simple fix that blocks our attacks. Moreover,
I will prove the new scheme secure in a new abstract model for multilinear maps which captures all known attacks. Thus, we obtain the first obfuscation candidate with a
convincing argument for security in light of recent attacks.
* Based on joint work with Saikrishna Badrinarayanan , Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, and Akshayaram Srinivasan
DIMACS/CEF Workshop on Cryptography and Software Obfuscation
New York Area CryptoDay

Apr 2016 
Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
MIT Cryptography and Information Security Seminar

Dec 2015 
Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
Princeton Theory Seminar
UCLA Obfuscation Seminar
UC Berkeley Theory Lunch

Sep 2015 
Cryptography in the Age of Quantum Computers
It is well established that fullfledged quantum computers, when realized, will completely break many of today`s
cryptosystems. This looming threat has led to the proposal of socalled "postquantum" systems, namely those that
appear resistant to quantum attacks. We argue, however, that the attacks considered in prior works model only the
near future, where the attacker may be equipped with a quantum computer, but the endusers implementing the protocols
are still running classical devices.
Eventually, quantum computers will reach maturity and everyone — even the
endusers — will be running quantum computers. In this event, attackers can interact with the endusers over quantum
channels, opening up a new set of attacks that have not been considered before. In this talk I will put forward new security
models and new security analyses showing how to ensure security against such quantum channel attacks. In particular,
these analyses allow for rebuilding many core cryptographic functionalities, including pseudorandom functions, encryption, digital signatures,
and more, resulting in the first protocols that are safe to use in a ubiquitous quantum computing world. Along the way,
we resolve several open problems in quantum query complexity, such as the Collision Problem for random functions, the
Set Equality Problem, and the Oracle Interrogation Problem.
Maryland Cybersecurity Center

Sep 2015 
Quantum Query Solvability: A Refinement of Quantum Query Complexity and Applications
The standard notion of “difficulty” for quantum oracle problems is that of quantum query complexity, which measures how many quantum queries to an oracle
are required to solve a given problem. In this talk, I will argue that quantum query complexity results typically hide important relationships between quantum
queries and the ability to solve problems. Instead, I will argue for a more refined notion of difficulty, called quantum query solvability, which measures how
easy it is to solve a given problem using a prescribed number of queries.
To motivate this notion, I will then describe several settings arising from
cryptography where quantum query solvability is important/useful. One such setting is that of finding collisions in a function f:[M]—>[N]. The quantum query
complexity of the socalled quantum collision problem has been established in the setting where N>=M, but it is unclear how to extend these results to the case
N=M, after which a simple reduction extends the result to the case N
QuICS Frontiers Workshop

May 2015 
OrderRevealing Encryption and the Hardness of Private Learning
An orderrevealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying
plaintexts. We show how to use orderrevealing encryption to separate computationally efficient PAC learning from efficient (ε,δ)differentially
private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially
private. This answers a question of Kasiviswanathan et al. (FOCS `08, SIAM J. Comput. `11).
To prove our result, we give a generic transformation from an orderrevealing encryption scheme into one with strongly correct comparison, which enables the
consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.
MIT Cryptography and Information Security Seminar

Sep 2014 
Fully Secure Functional Encryption without Obfuscation
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.
*Join work with Sanjam Garg, Shai Halevi, and Craig Gentry
DC Area Crypto Day
MIT Cryptography and Information Security Seminar

Jul 2014 
How to Avoid Obfuscation Using Witness PRFs
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.
Oberwolfach Workshop
New York Area CryptoDay
UCLA Obfuscation Seminar
MIT Cryptography and Information Security Seminar

Jun 2014 
Multiparty Key Exchange from Obfuscation
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.
Columbia Seminar

Apr 2014 
Multiparty Key Exchange, Efficient Traitor Tracing, and More
from Indistinguishability Obfuscation
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
UT Austin Algorithms and Computational Theory Seminar
Princeton Theory Seminar
Harvard Theory of Computation Seminar
NYU Cryptography Seminar

Apr 2014 
Multiparty Key Exchange and Broadcast Encryption from Software Obfuscation
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
Stanford Security Workshop

Nov 2013 
Classical Cryptosystems in a Quantum World
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.
IBM Watson

Oct 2013 
Quantum Computers and Cryptography
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.
Quantum Computing Seminar at Hacker Dojo

May 2013 
The Rank Method and Applications to PostQuantum Cryptography
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.
Waterloo IQC Colloquium

Apr 2013 
Beyond PostQuantum Cryptography
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.
MIT Cryptography and Information Security Seminar
New York Area CryptoDay
