I give a brief overview about the various known approaches for constructing quantum money, quantum lightning, and one-shot signatures, giving my thoughts on the benefits and limitations of each approach

Quantum money is a form of currency where the inability to counterfeit is derived from the no-cloning principle of quantum mechanics. An important feature of quantum money is public verification, allowing anyone to verify banknotes while still ensuring that only the mint can create new notes. Unfortunately, convincing realizations of publicly verifiable quantum money have remained elusive. In this talk, I will survey the literature on quantum money, explain what makes public verification so difficult, and describe some very recent progress toward overcoming these challenges.

An old result in classical computing due to Bennett shows that any irreversible circuit can be made reversible with only a small blow-up in both space and time. In quantum computing, the primary irreversible operation is a measurement, and so the analogous quantum question is whether intermediate quantum measurements can be eliminated from quantum computation. Prior work on eliminating measurements requires either space Ω(T) or time 2^Ω(S), where S,T are the space and time of the original circuit with measurements. For circuits with intermediate space (log(T) ≪ S ≪ T), prior work therefore incurs a large blow-up in either space or time. In this talk, I will give evidence that such a blow-up is potentially inherent, by showing a tight lower-bound for a natural class of “black-box” quantum circuit transformations which encompasses the prior works.

One-way functions are often referred to as the “minimal” cryptographic assumption. Recent revelations that objects “below” one-way functions may be possible quantumly have sparked a scramble to find a new minimal quantum assumption. In this talk, I take a step back and explore what makes one-way functions minimal in the first place and what we should be searching for quantumly.

Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. In this talk, I will discuss some recent work giving both attacks and new approaches to building publicly verifiable quantum money.

** based on joint work with Jiahui Liu and Hart Montgomery

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

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.

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.

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.

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

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

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.

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.

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.

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

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.

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

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.

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.

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

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.

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

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.

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

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.

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.

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.

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.

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.