# New constructions of pseudorandom codes

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

## Key facts

- Cited by 4 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 6 of its 36 references that are in the map.
- First posted on arXiv 11 Sep 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, 6 of 6)

- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)

## Built on by (most cited first, 4 of 4)

- [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)
- [Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2512.17310/) (2025)
- [Can we Watermark Low-Entropy LLM Outputs?](https://mlsanity.com/paper/2604.12051/) (2026)

## Abstract (arXiv)

Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random for an adversary that does not have the secret key, but anyone with the secret key is able to efficiently decode corrupted codewords. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a polynomial number of codewords from random with better than o(1) advantage. 2. We revisit the construction of [CG24] and show that it can be based on a wider range of assumptions than presented in [CG24]. To do this, we introduce a weakened version of the planted XOR assumption which we call the weak planted XOR assumption and which may be of independent interest. 3. We initiate the study of PRCs which are secure against space-bounded adversaries. We show how to construct secret-key PRCs of length O(n) which are textitunconditionally indistinguishable from random by poly(n) time, O(n1.5-varepsilon) space adversaries.