Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes
For researchers and practitioners using PRC-based watermarking in large generative models, this work reveals fundamental security limitations and provides defenses, though the primitive remains insecure at standard security levels.
The paper presents the first cryptanalysis of LDPC-based pseudorandom error-correcting codes (PRCs), demonstrating that their claimed security guarantees are undermined in all practical regimes. For instance, attacks can detect watermarks with overwhelming probability at a cost of 2^22 operations, and PRC-based watermarking fails to achieve 128-bit security due to constraints of large generative models.
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 $2^{22}$ 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.