Unclonable Quantum Cryptography
| ||||

| ||||

Verifiable Quantum Advantage without Structure
| ||||

“Structure” has long played a central role in proposals for super-polynomial quantum
advantage. This is especially true for problems whose solutions can be efficiently
verified, where all prior results require algebraic computational conjectures or
oracles with very specific features. In this talk, I will discuss a new approach for
verifiable quantum advantage which, for a reasonable complexity-theoretic notion of
“structure”, requires no structure at all.
| ||||

The Fundamental Formula of Post-Quantum Cryptography
| ||||

Security proofs in modern cryptography consist of three parts: (1) a security
definition capturing real-world attack scenarios, (2) a computational problem that is
widely regarded to be intractable, and (3) a reduction proving security under the
computational assumption. In this talk, I will discuss various ways in which each of
the three components of this fundamental formula need to be updated to account for
quantum computers, discussing some recent results and interesting open problems.
| ||||

Recent Developments in Quantum Copy Protection
| ||||

Quantum copy protection is a hypothetical tool which uses unclonable quantum states to
prevent programs from being copied. In this talk, I will discuss some recent progress
on building such unclonable programs. Along the way, I will highlight interesting
connections to watermarking software and obfuscating programs.
| ||||

Post-Quantum Cryptography
| ||||

Shor’s algorithms for factoring integers and finding discrete logarithms famously
break much of the cryptography used today. This has led to the field of post-quantum
cryptography, whose goal is to develop cryptosystems secure against quantum attacks.
In this talk, I will survey some of the challenges of post-quantum cryptography. In
particular, I will explain how the emergence of quantum computers requires updating
the entire modern practice of cryptography, including the underlying mathematical
building blocks, the formal definitions of security, and the proofs of security.
| ||||

Security Reductions in a Quantum World
| ||||

| ||||

Local Quantum Cryptography
| ||||

"Quantum cryptography" uses a quantum communication channel to achieve new
functionalities. For example, the unclonability of quantum messages means an attacker
cannot both record quantum communication and also pass it along to the recipient. This
leads to a form of eavesdropping detection that is central to quantum key distribution.
In this talk, I will discuss some recent work in an emerging area that I call "local quantum cryptography." Here, all communication channels remain classical, but the various parties leverage local quantum computing to achieve never-before-possible functionalities. Functionalities we achieve include unclonable cryptographic keys, quantum money with classical communication, rate-limited signatures, and more. The central challenge in this area is to take advantage of features of quantum mechanics such as unclonability, even though all "quantumness" is happening locally on the adversary`s device and therefore is entirely under the adversary`s control. | ||||

Revisiting Post-Quantum Fiat-Shamir
| ||||

The Fiat-Shamir transformation is a useful approach to building non-interactive
arguments (of knowledge) in the random oracle model. Unfortunately, existing proof
techniques are incapable of proving the security of Fiat-Shamir in the quantum
setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the
inability of current techniques to adaptively program random oracles in the quantum
setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications. *Joint work with Qipeng Liu | ||||

Quantum Lightning Never Strikes The Same State Twice
| ||||

Public key quantum money can be seen as a version of the quantum no-cloning theorem
that holds even when the quantum states can be verified by the adversary. In this
work, investigate quantum lightning, a formalization of "collision-free quantum
money" defined by Lutomirski et al. [ICS`10], where no-cloning holds even when the
adversary herself generates the quantum state to be cloned. We then study quantum
money and quantum lightning, showing the following results:• We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local. • We give win-win results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this gives some indication that natural schemes do attain strong security guarantees. • We construct quantum lightning under the assumed multi-collision resistance of random degree-2 systems of polynomials. Our construction is inspired by our win-win result for hash functions, and yields the first plausible standard model instantiation of a \emph{non-collapsing} collision resistant hash function. This improves on a result of Unruh [Eurocrypt`16] that requires a quantum oracle. •We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC`12] with indistinguishability obfuscation that is secure
against quantum computers yields a secure quantum money scheme. This construction can
be seen as an instance of our win-win result for signatures, giving the first
separation between two security notions for signatures from the literature. Thus, we provide the first constructions of public key quantum money from several cryptographic assumptions. Along the way, we develop several new techniques including a new precise variant of the no-cloning theorem. | ||||

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 polynomial-sized 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 polynomially-many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions — for example polynomially-many 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 Diffie-Hellman 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.
| ||||

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 non-trivial 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. | ||||

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

Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
| ||||

In this work, we put forward a new class of polynomial-time attacks on the original
multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks
on GGH13 were "zeroizing" attacks that generally required the availability of
low-level encodings of zero. Most significantly, such zeroizing attacks were not
applicable to candidate indistinguishability obfuscation (iO) schemes. iO has been the
subject of intense study. To address this gap, we introduce annihilation
attacks, which attack multilinear maps using non-linear polynomials. Annihilation
attacks can work in situations where there are no low-level encodings of zero. Using
annihilation attacks, we give the first polynomial-time cryptanalysis of candidate iO
schemes over GGH13. More specifically, we exhibit two simple programs that are
functionally equivalent, and show how to efficiently distinguish between the
obfuscations of these two programs.Given the enormous applicability of iO, it is important to devise iO schemes that can avoid attack. | ||||

Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
| ||||

In a traitor tracing scheme, each user is given a different decryption key. A content
distributor can encrypt digital content using a public encryption key and each user in
the system can decrypt it using her decryption key. Even if a coalition of users
combines their decryption keys and constructs some "pirate decoder" that is capable of
decrypting the content, there is a public tracing algorithm that is guaranteed to
recover the identity of at least one of the users in the coalition given black-box
access to such decoder. In prior solutions, the users are indexed by numbers 1,…,N and the tracing algorithm recovers the index i of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index i with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user`s key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor. The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices i ∈ [N]. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full "broadcast-trace-and-revoke" scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation. * Joint work with Ryo Nishimaki and Daniel Wichs | ||||

Cryptography in the Age of Quantum Computers
| ||||

It is well established that full-fledged quantum computers, when realized, will
completely break many of today`s cryptosystems. This looming threat has led to the
proposal of so-called "post-quantum" 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 end-users implementing the protocols are still running classical devices. Eventually, quantum computers will reach maturity and everyone — even the end-users — will be running quantum computers. In this event, attackers can interact with the end-users 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 re-building 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. | ||||

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 so-called 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, which is the cryptographically interesting setting. I will show how to solve this problem for arbitrary M,N. The idea is to first determine the quantum oracle solvability of the problem for the regime N≥M, after which a simple reduction extends the result to the case N<M (such a reduction does not apply for quantum query complexity). The quantum oracle solvability when N<M implies an optimal quantum query complexity in that regime, thus resolving the quantum query complexity problem for all domain/range sizes. | ||||

Order-Revealing Encryption and the Hardness of Private Learning
| ||||

An order-revealing 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 order-revealing 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 order-revealing 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. *Joint work with Mark Bun | ||||

The Surprising Power of Modern Cryptography
| ||||

Modern cryptography is surprisingly powerful, yielding capabilities such as secure
multiparty computation, computing on encrypted data, and hiding secrets in code.
Currently, however, some of these advanced abilities are still too inefficient for
practical use. The goals of my research are two-fold: (1) continue expanding the
capabilities of cryptography and its applications, and (2) bring these advanced
capabilities closer to practice. In this talk, I will focus on a particular contribution that addresses both of these objectives: establishing a shared secret key among a group of participants with only a single round of interaction. The first such protocols required a setup phase, where a central authority determines the parameters for the scheme; unfortunately, this authority can learn the shared group key and must therefore be trusted. I will discuss how to remove this setup phase using program obfuscation, though the scheme is very impractical due to the inefficiencies of current obfuscators. I will then describe a new technical tool called witness pseudorandom functions and show how to use this tool in place of obfuscation, resulting in a significantly more efficient protocol. | ||||

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. *Joint work with Sanjam Garg, Shai Halevi, and Craig Gentry | ||||

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, polynomially-many hardcore bits for any
one-way 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.
| ||||

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 non-interactive 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 | ||||

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 post-quantum
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. | ||||

Applications of Indistinguishability Obfuscation
| ||||

In a flurry of recent works, a form of program obfuscation called indistinguishability
obfuscation (iO) has proven to be an incredibly useful cryptographic tool. In this
talk, I will cover our recent work that uses iO to build multiparty key exchange,
broadcast encryption, and traitor tracing. Our schemes have several novel features;
for example, our key exchange and broadcast schemes can be instantiated with user's
existing RSA keys.
| ||||

Quantum Computers and Cryptography
| ||||

In a flurry of recent works, a form of program obfuscation called indistinguishability
obfuscation (iO) has proven to be an incredibly useful cryptographic tool. In this
talk, I will cover our recent work that uses iO to build multiparty key exchange,
broadcast encryption, and traitor tracing. Our schemes have several novel features;
for example, our key exchange and broadcast schemes can be instantiated with user's
existing RSA keys.
| ||||

Multilinear Maps and Their Applications
| ||||

| ||||

The Rank Method and Applications to Post-Quantum Cryptography
| ||||

Post-quantum 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 post-quantum 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. | ||||

Beyond Post-Quantum Cryptography
| ||||

Post-quantum 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 post-quantum 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. |