💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

This paper introduces a new construction of pseudorandom codes based on the permuted codes conjecture that simultaneously achieves subexponential security, robustness against worst-case edits on a binary alphabet, and resistance to adversaries possessing the detection key, thereby overcoming the critical limitations of prior watermarking schemes.

Original authors: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a famous author writing a novel. You want to prove that a specific paragraph was written by you and not by a copycat or an AI, but you don't want to change the story or make it look weird. You need a way to hide a secret "signature" inside the text that only you can find, even if someone tries to edit, delete, or scramble the words.

This paper is about building a much better version of that secret signature system, called a Pseudorandom Code (PRC). Think of a PRC as a magical encryption machine that turns a secret message into a long string of gibberish. If you have the key, you can turn the gibberish back into the message, even if someone has messed it up.

Here is the breakdown of the paper's achievements using simple analogies:

1. The Problem: The Old Signatures Were Too Easy to Break

Previously, researchers built these signature systems, but they had three big flaws:

The "Quasipolynomial" Flaw: Imagine a lock that takes a computer about a million years to break. That's good, right? But these old locks could actually be broken in a "quasipolynomial" time—think of it as a lock that takes a computer a few days instead of a million years. It wasn't secure enough for the long term.
The "Alphabet" Flaw: The old systems worked well if you could change the entire alphabet (like swapping every 'A' for a 'Z'). But real text (like English) has a small, fixed alphabet (26 letters). The old systems couldn't handle just changing a few letters or deleting a word without the signature breaking.
The "Key" Flaw: If a hacker knew your secret key, they could easily find tiny changes to remove your signature. The old systems assumed the hacker was blindfolded; they didn't work if the hacker had the glasses on.

2. The Solution: The "Permuted Puzzle"

The authors created a new system based on a concept they call the "Permuted Codes Conjecture."

Imagine you have a beautiful, complex mosaic (the code).

Shuffle the Tiles: You take the mosaic and randomly shuffle the positions of the tiles (Index Permutation).
Paint the Tiles: You take a brush and randomly repaint the color of each tile (Alphabet Permutation).
Sprinkle Dust: You sprinkle some random dust over the whole thing (Noise).

The authors claim that if you do all three steps, the result looks exactly like a pile of random, meaningless dust. To anyone without the key, it's impossible to tell the difference between the "scrambled mosaic" and "random dust." This makes the signature undetectable (it doesn't ruin the quality of the text).

3. The Three Big Wins

The paper claims to solve all three problems mentioned above simultaneously:

Super Strong Security: They claim their new lock is so strong that even a supercomputer running for a very long time (sub-exponential time) couldn't tell the difference between their scrambled mosaic and random dust.
Robust to Edits (The "Edit" Problem): This is the biggest breakthrough. Their system can survive edits. If a hacker deletes a word, adds a typo, or swaps a sentence around, the system can still find the signature.
- Analogy: Imagine a message written on a long strip of paper. If someone cuts out a few words, glues in new ones, or shuffles the order, the old system would fail. The new system is like a puzzle that can still be solved even if the pieces are slightly damaged or moved around.
Robust to the "Key-Knowing" Hacker: Their system works even if the hacker knows the secret key.
- Analogy: Usually, if a thief knows your safe's combination, they can open it and remove the contents. The authors built a safe where even if the thief knows the combination, they can't remove the hidden item without destroying the safe itself. This allows anyone to verify the watermark, not just a trusted party, without breaking the system.

4. How They Did It (The "Folded" Trick)

To make this work for real text (which has low "entropy" or randomness per word), they used a special type of math code called Folded Reed-Solomon codes.

Analogy: Imagine you are trying to send a secret message, but you can only send short, choppy bursts of data. The old way was to send one letter at a time. The new way is to "fold" the message. Instead of sending "A, B, C," you send a single block that represents "A, B, and C" all at once. This allows the system to pack more information into the text without needing the text to be highly random or chaotic.

5. The "Catch" (The Assumption)

The authors admit they are making a big assumption. They are betting that the "Permuted Puzzle" (the scrambled mosaic) is truly impossible to distinguish from random dust.

They didn't prove this is mathematically impossible to break (no one has proven that for this specific type of puzzle yet).
However, they showed that:
1. It is implied by another famous, well-studied assumption in cryptography (Permuted Puzzles).
2. They tried to break it with many different types of attacks (like trying to find patterns in the dust) and failed.
3. They proved that if you leave out any of the three steps (shuffling, repainting, or dusting), the system becomes easy to break. This suggests all three steps are necessary and the system is robust.

Summary

This paper introduces a new, super-secure way to watermark AI-generated text. It claims to be the first system that:

Is nearly impossible to detect (it looks like normal text).
Survives heavy editing (typos, deletions, rewrites).
Works even if the attacker knows the secret key.

They achieve this by turning the text into a "scrambled puzzle" that relies on a new mathematical assumption, which they argue is very likely to be true based on extensive testing and connections to other established math theories.

Technical Summary: Improved Pseudorandom Codes from Permuted Puzzles

Problem Statement

The proliferation of AI-generated content necessitates robust watermarking schemes to identify provenance. Recent work established that Pseudorandom Codes (PRCs) are equivalent to watermarking schemes with strong robustness and quality guarantees. A PRC is a secret-key encryption scheme where ciphertexts are computationally indistinguishable from uniform (ensuring undetectability/quality) and the decryption algorithm tolerates a high rate of errors (ensuring robustness).

However, existing PRC constructions suffer from three critical limitations:

Weak Security: All prior constructions are vulnerable to quasipolynomial-time distinguishing attacks. They rely on hiding $(\log n)$ -sparse structures, which allows brute-force search attacks.
Limited Alphabet Robustness: While some constructions handle edit errors, they require a polynomial-sized alphabet. Realistic text (e.g., from Large Language Models) has low entropy (approx. 1 bit per word), necessitating a PRC robust to edits over a constant-sized (ideally binary) alphabet.
Weak Adversarial Models: Prior works assume adversaries are computationally bounded or lack the detection key. It was unclear if PRCs could remain robust against computationally unbounded adversaries who possess the detection key (strongly-adaptive robustness).

The central open question was whether a single construction could achieve subexponential security, edit-robustness over a binary alphabet, and robustness against key-holding adversaries simultaneously.

Methodology

1. The Permuted Codes Conjecture

The authors introduce a new computational hardness assumption, the Permuted Codes Conjecture. This conjecture posits that a distribution of "scrambled" noisy codewords is computationally indistinguishable from a uniform distribution.

The distribution $D_{n,\Sigma,C,\eta,T}$ is generated as follows:

Sample a random index permutation $\sigma \in S_n$ and alphabet permutations $\pi_1, \dots, \pi_n \in S_\Sigma$ .
Sample $T$ codewords $c_1, \dots, c_T$ uniformly from a linear code $C \subseteq \Sigma^n$ .
For each codeword, permute the indices via $\sigma$ and the symbols at each position via $\pi_j$ , yielding $\hat{c}$ .
Apply a substitution channel with noise rate $\eta$ to $\hat{c}$ .

Key Insight: The authors prove that this conjecture is implied by the Permuted Puzzles Conjecture (previously used for doubly efficient Private Information Retrieval). They provide statistical evidence that for constant-sized alphabets and codes with high dual distance, a logarithmic number of samples are statistically uniform. Furthermore, they demonstrate that all three components (index permutation, alphabet permutation, and noise) are necessary; omitting the alphabet permutation (as in a "toy" version) renders Reed-Solomon codes distinguishable via low-degree polynomial attacks.

2. Construction of Edit-Robust PRCs

To achieve edit-robustness over a binary alphabet, the authors construct a PRC based on Folded Reed-Solomon (FRS) codes.

Encoding: The secret key consists of the permutations and a one-time pad. To encode, a random codeword from the underlying code is permuted, noisy, and then a subset of symbols is selected. Crucially, each selected symbol is output as a binary string containing both the symbol value and its index.
Decoding: The decoder receives a string potentially corrupted by edits (insertions/deletions). It scans all substrings of a specific length, attempting to "brute-force" the edit distance to recover potential $(index, symbol)$ pairs. These candidates form a list for each position. A list-recovery algorithm for the underlying code is then applied to these lists to recover the original codeword.
Robustness Mechanism: By including indices in the output, the decoder can recover the correct symbol even if the position has been shifted by insertions or deletions, provided the number of edits is bounded. The use of FRS codes allows the system to tolerate a constant fraction of edits even when the alphabet is effectively binary (via the transformation).

3. Watermarking Transformation

Using the framework established by Christ and Gunn (CRYPTO '24), the authors transform their PRC into a watermarking scheme for autoregressive language models. The scheme generates watermarked text by biasing token selection toward the PRC codeword bits. The robustness of the PRC against edits directly translates to the watermark's ability to survive adversarial text modifications, provided the model has sufficient per-token entropy.

Key Contributions and Results

1. New PRC Construction with Three Properties

The paper presents the first PRC construction that simultaneously satisfies:

Plausible Subexponential Security: Based on the Permuted Codes Conjecture, which avoids the sparse structures vulnerable to quasipolynomial attacks.
Binary Alphabet Edit-Robustness: The construction tolerates a constant rate of worst-case edits (insertions, deletions, substitutions) over a binary alphabet.
Strongly-Adaptive Robustness: The scheme remains robust even against adversaries who know the secret detection key and are computationally unbounded.

2. Theoretical Guarantees

Theorem 5.6: Under the Permuted Codes Conjecture, there exists a binary-alphabet PRC that is strongly-adaptive to a constant rate of edits with subexponential security.
Theorem 5.14: Under a variant of the conjecture for Folded Reed-Solomon codes, there exists an undetectable LLM watermark that is robust to a constant rate of edits ( $\tilde{O}(\alpha^7)$ ) requiring only a constant per-token entropy rate $\alpha$ . This is the first such watermark that is both undetectable and robust to worst-case edits under realistic entropy constraints.

3. Cryptanalysis and Evidence

Necessity of Alphabet Permutation: The authors prove that without alphabet permutations, Reed-Solomon codes are efficiently distinguishable from random, even with index permutations and noise.
Quasipolynomial Attacks on Prior Work: They show that a broad class of previous PRC constructions (those relying on planted sparse structures or noise-tolerant predicates) are inherently vulnerable to quasipolynomial-time attacks.
Statistical Uniformity: They prove that for constant-sized alphabets, a small number of permuted codewords are statistically indistinguishable from uniform, providing evidence for the conjecture's validity against simple distinguishers.

Significance

The paper claims to resolve the tension between the three desirable properties of PRCs that were previously thought to be mutually exclusive or unattainable. By formalizing the Permuted Codes Conjecture and leveraging Folded Reed-Solomon codes, the authors provide a theoretical foundation for watermarking schemes that are:

Undetectable: Indistinguishable from the true language model output.
Robust: Capable of withstanding adversarial edits (insertions/deletions) to the text.
Secure: Resilient against attackers who possess the detection key, enabling public verification without compromising robustness.

The work establishes that achieving these properties requires moving beyond sparse structures and embracing the hardness of distinguishing permuted, noisy codewords from random strings. While the security relies on a new conjecture, the authors provide strong evidence for its validity and demonstrate that it implies the existence of practical, robust watermarks for AI-generated text.