# Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes

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

## Key facts

- Cited by 1 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 28 of its 53 references that are in the map.
- First posted on arXiv 19 Dec 2025.

## 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, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps](https://mlsanity.com/paper/2206.00927/) (2022)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [HiDDeN: Hiding Data With Deep Networks](https://mlsanity.com/paper/1807.09937/) (2018)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [The Stable Signature: Rooting Watermarks in Latent Diffusion Models](https://mlsanity.com/paper/2303.15435/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [StegaStamp: Invisible Hyperlinks in Physical Photographs](https://mlsanity.com/paper/1904.05343/) (2019)
- [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)
- [Gaussian Shading: Provable Performance-Lossless Image Watermarking for Diffusion Models](https://mlsanity.com/paper/2404.04956/) (2024)
- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [WAVES: Benchmarking the Robustness of Image Watermarks](https://mlsanity.com/paper/2401.08573/) (2024)
- [MarkLLM: An Open-Source Toolkit for LLM Watermarking](https://mlsanity.com/paper/2405.10051/) (2024)
- [An Undetectable Watermark for Generative Image Models](https://mlsanity.com/paper/2410.07369/) (2024)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Embarrassingly Simple Text Watermarks](https://mlsanity.com/paper/2310.08920/) (2023)
- [Ideal Pseudorandom Codes](https://mlsanity.com/paper/2411.05947/) (2024)
- [Removing Watermarks with Partial Regeneration using Semantic Information](https://mlsanity.com/paper/2505.08234/) (2025)
- [New constructions of pseudorandom codes](https://mlsanity.com/paper/2409.07580/) (2024)
- [Improved Pseudorandom Codes from Permuted Puzzles](https://mlsanity.com/paper/2512.08918/) (2025)
- [Black-Box Crypto is Useless for Pseudorandom Codes](https://mlsanity.com/paper/2506.01854/) (2025)

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

- [Attribute-based Undetectable Watermarking for Generative AI Models](https://mlsanity.com/paper/2608.03174/) (2026)

## Abstract (arXiv)

Pseudorandom error-correcting codes (PRCs), a novel cryptographic primitive recently proposed at CRYPTO 2024, are primarily applied in undetectable watermarking schemes for large generative models. However, the security of PRCs has not yet been systematically analyzed. To fill this gap, we present the first cryptanalysis of PRCs. Specifically, focusing on LDPC-PRC, the only known practical instantiation of PRCs, we propose three novel attacks that challenge its undetectability and robustness. To rigorously demonstrate the practical threat, we analyze the concrete attack complexity under realistic parameters and validate the attack effectiveness on both real-world large language models and generative image models, including DeepSeek and Stable Diffusion. Our analysis shows that the claimed security guarantees of LDPC-PRC are undermined across all practically feasible regimes. For example, our attacks can detect the presence of a watermark with overwhelming probability at a cost of 222 operations. Beyond attacks, we further propose three defenses: parameter recommendation, implementation suggestion, and a revised key generation function. However, PRC-based watermarking schemes still fail to achieve 128-bit security due to inherent constraints of large generative models, such as the maximum output length of large language models. Overall, our work clarifies the concrete security limits of PRCs in real-world watermarking applications.