# Pseudorandom Error-Correcting Codes

arXiv: https://arxiv.org/abs/2402.09370 · HTML: https://mlsanity.com/paper/2402.09370/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 13 of 13)

- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [The Science of Detecting LLM-Generated Texts](https://mlsanity.com/paper/2303.07205/) (2023)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [Mark My Words: Analyzing and Evaluating Language Model Watermarks](https://mlsanity.com/paper/2312.00273/) (2023)
- [Perfectly Secure Steganography Using Minimum Entropy Coupling](https://mlsanity.com/paper/2210.14889/) (2022)
- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)

## Built on by (most cited first, 30 of 44)

- [An Undetectable Watermark for Generative Image Models](https://mlsanity.com/paper/2410.07369/) (2024)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [Watermarking Language Models for Many Adaptive Users](https://mlsanity.com/paper/2405.11109/) (2024)
- [VideoMark: A Distortion-Free Robust Watermarking Framework for Video Diffusion Models](https://mlsanity.com/paper/2504.16359/) (2025)
- [A Watermark for Black-Box Language Models](https://mlsanity.com/paper/2410.02099/) (2024)
- [GaussMarker: Robust Dual-Domain Watermark for Diffusion Models](https://mlsanity.com/paper/2506.11444/) (2025)
- [PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints](https://mlsanity.com/paper/2509.21057/) (2025)
- [Edit Distance Robust Watermarks via Indexing Pseudorandom Codes](https://mlsanity.com/paper/2406.02633/) (2024)
- [Provably Robust Watermarks for Open-Source Language Models](https://mlsanity.com/paper/2410.18861/) (2024)
- [Watermarking Language Models with Error Correcting Codes](https://mlsanity.com/paper/2406.10281/) (2024)
- [Radioactive Watermarks in Diffusion and Autoregressive Image Generative Models](https://mlsanity.com/paper/2506.23731/) (2025)
- [Verifying LLM Inference to Detect Model Weight Exfiltration](https://mlsanity.com/paper/2511.02620/) (2025)
- [Secure and Robust Watermarking for AI-generated Images: A Comprehensive Survey](https://mlsanity.com/paper/2510.02384/) (2025)
- [Tool Use Enables Undetectable Steganography in Multi-Agent LLM Systems](https://mlsanity.com/paper/2606.28425/) (2026)
- [New constructions of pseudorandom codes](https://mlsanity.com/paper/2409.07580/) (2024)
- [Multi-Designated Detector Watermarking for Language Models](https://mlsanity.com/paper/2409.17518/) (2024)
- [Mitigating Watermark Forgery in Generative Models via Randomized Key Selection](https://mlsanity.com/paper/2507.07871/) (2025)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)
- [Innamark: A Whitespace Replacement Information-Hiding Method](https://mlsanity.com/paper/2502.12710/) (2025)
- [Towards A Correct Usage of Cryptography in Semantic Watermarks for Diffusion Models](https://mlsanity.com/paper/2503.11404/) (2025)
- [ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport](https://mlsanity.com/paper/2602.07235/) (2026)
- [SIGMark: Scalable In-Generation Watermark with Blind Extraction for Video Diffusion](https://mlsanity.com/paper/2603.02882/) (2026)
- [Disclosure By Design: Identity Transparency as a Behavioural Property of Conversational AI Models](https://mlsanity.com/paper/2603.16874/) (2026)
- [The Coding Limits of Robust Watermarking for Generative Models](https://mlsanity.com/paper/2509.10577/) (2025)
- [OSI: One-step Inversion Excels in Extracting Diffusion Watermarks](https://mlsanity.com/paper/2602.09494/) (2026)
- [Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking](https://mlsanity.com/paper/2605.00348/) (2026)
- [Watermarking Should Be Treated as a Monitoring Primitive](https://mlsanity.com/paper/2605.13095/) (2026)
- [SAMark: A Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness](https://mlsanity.com/paper/2605.25796/) (2026)
- [SWA-LDM: Toward Stealthy Watermarks for Latent Diffusion Models](https://mlsanity.com/paper/2502.10495/) (2025)
- [Ideal Attribution and Faithful Watermarks for Language Models](https://mlsanity.com/paper/2512.07038/) (2025)

## Abstract (arXiv)

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 substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either 2^O(√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.