Sam Gunn

How does the choice of training data influence an AI model? This broad question is of central importance to interpretability, privacy, and basic science. At its technical core is the data deletion problem: after a reasonable amount of precomputation, quickly predict how the model would behave in a given situation if a given subset of training data had been excluded from the learning algorithm.

We present a data deletion scheme capable of predicting model outputs with vanishing error ε and failure probability δ in the deep learning setting. Our precomputation and prediction algorithms are only Õ(log(1/δ)/ε²) factors slower than regular training and inference, respectively. The storage requirements are those of Õ(log(1/δ)/ε²) models.

Our proof is based on an assumption that we call stability. In contrast to the assumptions made by prior work, stability appears to be fully compatible with learning powerful AI models. In support of this, we show that stability is satisfied in a minimal set of experiments with microgpt. Our code is available at this URL.

At a technical level, our work is based on a new method for locally sketching an arithmetic circuit by computing higher-order derivatives in random complex directions. Forward-mode automatic differentiation allows cheap computation of these derivatives.

We show that, assuming the existence of one-way functions, it is possible to watermark LLM outputs without incurring any detectable change to the output distribution. That is, watermarks can be detected only with the knowledge of a secret key; without the secret key, it is computationally intractable to distinguish watermarked outputs from those of the original model. We call a watermark satisfying this property undetectable.

We define a pseudorandom code as an error-correcting code family for which codewords appear random to any computationally-bounded observer. It is possible to efficiently decode from noisy codewords with the help of a decoding key. We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on the assumption that LPN is hard for 2^O(√n)-time algorithms.

We show that the problem of constructing robust, undetectable watermarks for generative AIs is essentially equivalent to the problem of constructing pseudorandom codes. In particular, our ideas yield the first undetectable watermark for LLMs that is robust to the popular ``emoji'' or ``pineapple'' attack.

We show that pseudorandom codes can be made to tolerate adversarial low-weight errors, even when the adversary is allowed to choose the error after making queries to encoding and decoding oracles.

Prior constructions of pseudorandom codes are all vulnerable to quasipolynomial-time distinguishing attacks. We introduce a new cryptographic assumption, called permuted codes, which can be used to build pseudorandom codes that are plausibly subexponentially secure. For sufficiently large block lengths—such as those which arise in image watermarks—this can significantly improve the practical security.

The permuted codes conjecture says that, for any linear code C over (𝔽_q)ⁿ with dual distance poly(n) and any T = poly(n), the following distribution is pseudorandom.

1. Sample an index permutation π : [n] → [n] and alphabet permutations π₁, …, π_n : 𝔽_q → 𝔽_q.
2. Sample random codewords c₁, …, c_T from C. For each i, let ĉ_i be the string obtained from c_i by permuting the indices according to π and the alphabet at index j according to π_j.
3. Output E(ĉ₁), …, E(ĉ_T), where E(x) outputs x with probability 1 − p and a random string from 𝔽_qⁿ otherwise.

We provide several lines of evidence for our permuted codes conjecture:

• It is implied by the permuted puzzles conjecture which was used previously to construct doubly efficient private information retrieval.
• Permuted codes fool simple distinguishers including read-once branching programs.
• Natural attacks on the conjecture fail.

We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive, such as random oracles, generic multilinear groups, and virtual black-box obfuscation.

We use pseudorandom codes to watermark a diffusion model. The pseudorandom code is used to select the initial latent noise, and existing algorithms are used to recover this noise during watermark detection. Our experiments with Stable Diffusion 2.1 show that, in contrast to every prior scheme we tested, our watermark does not degrade image quality. Our experiments also demonstrate robustness: existing watermark removal attacks fail to remove our watermark from images without significantly degrading the quality of the images. Finally, we find that we can robustly encode 512 bits in our watermark, and up to 2500 bits when the images are not subjected to watermark removal attacks. Our code is available at this URL.

We present an overview of the desired properties of watermarks and the techniques that exist to fulfill them. We aim to guide researchers in advancing watermarking methods and applications, and to support policymakers in addressing the broader implications of AI.

We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018).

We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work).

Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption.

Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.

The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time.

In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models.

We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol.

Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.

It is well known that no quantum error correcting code of rate R can correct adversarial errors on more than a (1 − R)/4 fraction of symbols. But what if we only require our codes to approximately recover the message? We construct efficiently-decodable approximate quantum codes against adversarial error rates approaching the quantum Singleton bound of (1 − R)/2, for any constant rate R. Moreover, the size of the alphabet is a constant independent of the message length and the recovery error is exponentially small in the message length. Central to our construction is a notion of quantum list decoding and an implementation involving folded quantum Reed-Solomon codes.

Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs. As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs.

We show that applying qsiO to a program immediately achieves best-possible copy protection. Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs — significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE).

While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection. Finally, we construct qsiO relative to an efficient quantum oracle.

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender’s view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages.

We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities.

Our flagship application of a succinct QSC is a quantum-communication version of Kilian’s succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.