International Association
for Cryptologic Research

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.

We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key. We build pseudorandom codes that are robust to bit-flip and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either $2^{O(\sqrt{n})}$-hardness of LPN, or polynomial hardness of LPN and the planted XOR problem at low density. As our primary application of pseudorandom codes, we present an undetectable watermarking scheme for outputs of language models that is robust to cropping and a constant rate of random substitutions and deletions. The watermark is undetectable in the sense that any number of samples of watermarked text are computationally indistinguishable from text output by the original model. This is the first undetectable watermarking scheme that can tolerate a constant rate of errors. Our second application is to steganography, where a secret message is hidden in innocent-looking content. We present a constant-rate stateless steganography scheme with robustness to a constant rate of substitutions. Ours is the first stateless steganography scheme with provable steganographic security and any robustness to errors.

Recent progress in large language models (LLMs) has led to demand for measures to detect AI-generated text, as evidenced by Biden's recent executive order, and pledges by several major companies to embed watermarks in the outputs of their models. A promising and popular solution for detecting AI-generated content is watermarking, where a hidden signal is embedded in the LLM's output. Intuitively, desirable properties of LLM watermarks are clear: they should not hurt the quality of the model, and human-generated text should not be falsely flagged as watermarked. However, these properties are challenging to define because of idiosyncracies in human text and a lack of a clear text quality measure, especially when LLMs have a wide variety of downstream applications. In [CGZ23], we show how {cryptography} can be leveraged to formally define these properties of quality and lack of false positives, which we call undetectability and soundness. Undetectability requires that no efficient algorithm can distinguish between the original LLM and the watermarked LLM. Soundness requires that any fixed text is detected as watermarked with negligible probability. [CGZ23] constructs a fairly simple watermarking scheme that achieves these properties. In this talk, we begin by giving background on policy discussion and media coverage surrounding detection of AI-generated text. We then present our work in [CGZ23], in particular covering the model, definitions, and scheme. We conclude by discussing directions for future work, emphasizing interesting cryptographic questions.