Sam Gunn

ICLR Conference 2025 Conference Paper

An Undetectable Watermark for Generative Image Models

• Sam Gunn
• Xuandong Zhao
• Dawn Song

We present the first undetectable watermarking scheme for generative image models. _Undetectability_ ensures that no efficient adversary can distinguish between watermarked and un-watermarked images, even after making many adaptive queries. In particular, an undetectable watermark does not degrade image quality under any efficiently computable metric. Our scheme works by selecting the initial latents of a diffusion model using a pseudorandom error-correcting code (Christ and Gunn, 2024), a strategy which guarantees undetectability and robustness. We experimentally demonstrate that our watermarks are quality-preserving and robust using Stable Diffusion 2.1. Our experiments verify 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 https://github.com/XuandongZhao/PRC-Watermark.

STOC Conference 2025 Conference Paper

Classical Commitments to Quantum States

• Sam Gunn
• Yael Tauman Kalai
• Anand Natarajan 0001
• Ági Villányi

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.

STOC Conference 2025 Conference Paper

Ideal Pseudorandom Codes

• Omar Alrabiah
• Prabhanjan Ananth
• Miranda Christ
• Yevgeniy Dodis
• Sam Gunn

STOC Conference 2024 Conference Paper

Approaching the Quantum Singleton Bound with Approximate Error Correction

• Thiago Bergamaschi
• Louis Golowich
• Sam Gunn

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? In this work, 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 . Specifically, for every R ∈ (0,1) and γ>0, we construct codes of rate R , message length k , and alphabet size 2 O (1/γ 5 ) , that are efficiently decodable against a (1− R −γ)/2 fraction of adversarial errors and recover the message up to inverse-exponential error 2 −Ω( k ) . At a technical level, we use classical robust secret sharing and quantum purity testing to reduce approximate quantum error correction to a suitable notion of quantum list decoding. We then instantiate our notion of quantum list decoding by (i) introducing folded quantum Reed-Solomon codes, and (ii) applying a new, quantum version of distance amplification.

STOC Conference 2024 Conference Paper

How to Use Quantum Indistinguishability Obfuscation

• Andrea Coladangelo
• Sam Gunn

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.

STOC Conference 2023 Conference Paper

Commitments to Quantum States

• Sam Gunn
• Nathan Ju
• Fermi Ma
• Mark Zhandry

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.