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.

A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. 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: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as Ghentiyala and Guruswami (2024) observed that pseudorandom codes tolerating any sub-constant rate of random errors exist assuming just one-way functions. The key technical ingredient in our proof is the hypercontractivity theorem for Boolean functions, which we use to prove our impossibility in the random oracle model. It turns out that this easily extends to a separation of pseudorandom codes tolerating a constant rate of random errors from ``crypto oracles,'' a notion introduced and shown to be capable of implementing all the primitives mentioned above by Lin, Mook, and Wichs (EUROCRYPT 2025).

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.