Technical Summary: Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes

Problem Statement

Pseudorandom Error-Correcting Codes (PRCs), introduced at CRYPTO 2024, represent a novel cryptographic primitive designed to enable undetectable watermarking for Large Generative Models (LLMs) and Generative Image Models (GIMs). The primary instantiation of PRCs, known as LDPC-PRC, relies on Low-Density Parity-Check codes and claims security based on the hardness of the Learning Parity with Noise (LPN) and planted XOR problems.

Despite strong theoretical asymptotic guarantees, the concrete security of LDPC-PRC under practical parameter settings remains unexplored. Existing literature suggests that PRCs may be vulnerable to quasipolynomial-time distinguishing attacks, yet no rigorous analysis has been conducted to quantify these vulnerabilities in real-world deployment scenarios. This gap leaves the undetectability and robustness of PRC-based watermarking schemes unverified against practical adversaries.

Methodology

This work presents the first concrete cryptanalysis of LDPC-PRC, focusing on two specific watermarking schemes: $\Pi_{LLM}$ (for text generation) and $\Pi_{GIM}$ (for image generation). The authors propose three novel attacks targeting the scheme's undetectability and robustness, analyzing their complexity under realistic parameter configurations derived from state-of-the-art models (DeepSeek and Stable Diffusion).

1. Novel Cryptographic Attacks

The authors design three attacks with varying goals:

• Attack-I (Partial Secret Key Recovery): This attack targets the undetectability property. By adapting Information Set Decoding (ISD) algorithms using a Meet-in-the-Middle (MITM) approach, the adversary recovers a subset of the secret key's row vectors from the public key. These recovered vectors allow the adversary to distinguish between PRC-encoded codewords and random vectors with overwhelming probability, effectively breaking undetectability.
• Attack-II (Weak Key Distinguisher): This attack exploits a vulnerability in the key generation procedure ($KeyGen$). The authors observe that in current implementations, the public key matrix $G$ may contain identical rows with non-negligible probability (a "weak key"). An adversary can detect these statistical non-uniformities to distinguish watermarked content from random noise in linear time, bypassing the need for complex key recovery.
• Attack-III (Noise Overlay Attack): This attack targets the robustness property. By recovering the original Bernoulli noise vector $e$ via Syndrome Decoding, an adversary constructs a malicious overlay vector $e'$. This vector is designed such that when added to the codeword, the total noise weight exceeds the decoder's correction threshold, causing decoding failure (watermark removal). Crucially, this attack exploits the gap between theoretical noise bounds and the lower concrete noise rates observed in practical implementations.

2. Concrete Complexity Analysis

The authors analyze the time and data complexity of these attacks using specific parameter sets for $\Pi_{LLM}$ and $\Pi_{GIM}$. They derive theoretical bounds (Theorems 1–3) and validate them against concrete parameters, calculating the bit-security levels (e.g., $2^{46}$, $2^{60}$) rather than relying solely on asymptotic notation.

3. Real-World Evaluation

To validate practical threats, the authors implemented $\Pi_{LLM}$ and $\Pi_{GIM}$ on DeepSeek (LLM) and Stable Diffusion (GIM). They evaluated the success rates of the attacks and the impact on content quality. Notably, they found that for $\Pi_{LLM}$, achieving detectable watermarks requires high token entropy, which severely degrades text readability, rendering the scheme impractical for high-quality text generation.

Key Contributions and Results

1. Breaking Undetectability

• Attack-I: Demonstrated that partial secret key recovery is feasible. For $\Pi_{GIM}$, the security level remains below 46 bits across all parameter choices. For $\Pi_{LLM}$, the attack succeeds with overwhelming probability.
• Attack-II: Revealed that weak keys occur with nearly 100% probability for specific parameters (e.g., $t=3, 4$) in both LLM and GIM schemes. This allows for polynomial-time distinguishing attacks, completely undermining undetectability in these regimes.

2. Breaking Robustness

• Attack-III: Proved that the security level of $\Pi_{LLM}$ cannot exceed 75 bits for $n \le 2^{17}$ under noise overlay attacks. For $\Pi_{GIM}$, the concrete security level is below 60 bits due to the low concrete noise rate ($\eta \ll \rho$).
• Experimental Validation: On Stable Diffusion, the authors achieved watermark removal success rates of 67% to 96% depending on the perturbation bound ($\delta$), demonstrating that robustness is easily compromised.

3. Practical Limitations of $\Pi_{LLM}$

The evaluation on DeepSeek revealed a fundamental trade-off: to satisfy the error-correction bounds of LDPC-PRC, the LLM must generate high-entropy (low-confidence) tokens. This results in text that is either undetectable (low entropy) or unreadable (high entropy). Consequently, the authors conclude that $\Pi_{LLM}$ is impractical for real-world watermarking of high-quality text.

4. Proposed Defenses

The paper proposes three mitigation strategies:

• Parameter Recommendations: Increasing code length $n$ and row weight $t$ can raise attack complexity. However, achieving 128-bit security requires $n > 2^{24}$, which exceeds the maximum output length of current state-of-the-art LLMs ($2^{15}$).
• Revised Key Generation: A modified $KeyGen$ algorithm (Algorithm 2) using Gaussian elimination is proposed to eliminate the probability of generating weak keys, mitigating Attack-II.
• Implementation Adjustments: For GIMs, increasing the weight of the added noise vector is suggested to close the gap between theoretical and concrete noise rates, thereby increasing the complexity of Attack-III.

Significance and Claims

The paper claims to provide the first systematic security evaluation of PRCs, bridging the gap between asymptotic theory and practical deployment. The authors assert that:

1. Security Guarantees are Undermined: The claimed security of LDPC-PRC is insufficient across all practically feasible regimes. Attacks can detect watermarks with overwhelming probability at costs significantly lower than 128 bits.
2. Practical Impossibility for LLMs: Due to inherent constraints of large generative models (specifically output length and token entropy), achieving 128-bit security for LLM watermarking via LDPC-PRC is currently impractical.
3. Need for Rigorous Evaluation: The work highlights that theoretical hardness assumptions (LPN/planted XOR) do not automatically translate to concrete security when specific implementation details (like key generation heuristics and noise rates) are considered.

The authors conclude that while PRC-based image watermarking may still admit practical instantiations with acceptable quality, the current state of PRCs for LLMs requires significant re-evaluation of parameters and implementation strategies before widespread deployment.