💻 computer science

Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes

本文通过对基于 LDPC 的伪随机纠错码（PRC）进行的首次密码分析，通过新颖的攻击手段和现实世界的实验，证明了其声称的安全保证在实际的生成模型水印应用中被从根本上削弱，同时还提出了具体的防御措施并阐明了其固有的安全极限。

原作者： Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

原作者： Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：有缺陷的隐形墨水

想象一种为人工智能（AI）设计的全新“隐形墨水”。这种墨水旨在为 AI 生成的文本和图像盖上一个秘密且不可移除的印记（即水印）。其目标是证明某件内容是由特定的 AI 生成的，且任何人都无法看到这个印记或将其洗掉。

这种“隐形墨水”被称为 PRC（伪随机纠错码）。其创造者声称它是从数学上不可破解的。

然而，来自清华大学和山东大学的研究团队决定扮演“安全测试员”的角色。他们试图破解这种墨水。他们的结论是：这种墨水正在“泄漏”。 他们发现了三种不同的方法，可以要么看穿这个隐形印记，要么将其洗掉，这证明了这项技术的当前版本并不像宣传的那样安全。

他们破解墨水的三种方式

研究人员针对制造这种墨水的特定配方——LDPC-PRC 进行了研究。他们发现了配方中的三个不同“漏洞”：

1. “部分密钥”劫持 (攻击-I)

类比： 想象隐形墨水的秘密密钥是一个拥有数千个转轮的巨大、复杂的组合锁。公钥是关于这个锁的一个提示。研究人员发现了一种方法，只需撬开其中几个转轮（恢复部分秘密密钥）。
含义： 即使你没有整个密钥，只要拥有其中的一小部分，就足以分辨出一段内容是“带有水印的”图像/文本，还是正常的。这就像通过看到某扇窗户微开，就能判断出一栋房子是否被锁上了。
结果： 他们利用相对较小的计算能力，就能以近乎完美的准确度检测出水印。

2. “重复页面”错误 (攻击-II)

类比： 想象制作这个锁的配方涉及通过洗牌一副扑克牌来创建一个独特的图案。研究人员注意到洗牌机坏了。有时，它会不小心在牌堆中连续打印出完全相同的卡牌图案两次。
含义： 由于“洗牌”（密钥生成）不够随机，导致一些“锁”（密钥）非常脆弱。如果攻击者找到了这些弱锁，他们就能瞬间识别出水印。
结果： 在创造者建议的许多设置中，这些“弱锁”几乎 100% 会出现。这就像是在试图把一个秘密藏进一本书，而作者却不小心在每一页都写了相同的句子。

3. “噪声叠加” (攻击-III)

类比： 这种隐形墨水旨在抵御一点点“雨水”（噪声）。如果你在纸上喷一点水，墨水依然清晰可见。研究人员意识到，他们可以喷洒一种特定类型的水，这种水虽然在肉眼看来量很正常，但能抵消掉墨水被读取的能力。
含义： 他们发现了一种方法，可以在文本或图像中添加极少量的、经过计算的“静态噪声”。这种噪声不会破坏图片或故事的内容，但会让解码器产生严重的混乱，使其认为水印不存在。
结果： 他们可以完全移除水印，且不会让图像看起来模糊或让文本看起来像乱码。

现实世界测试：它在真正的 AI 上有效吗？

研究人员不仅在纸面上做数学题，他们还在真实的 AI 模型上进行了测试：

针对文本 (LLMs)： 他们尝试对名为 DeepSeek 的模型生成的文本进行水印处理。他们发现了一个重大问题：为了让水印可检测，AI 必须以一种非常随机且低质量的方式进行写作（就像机器人在产生幻觉一样）。如果 AI 写出高质量、自然的文本，水印就会消失；如果水印存在，文本则变得无法阅读。结论： 这对于高质量文本来说几乎是毫无用处的。
针对图像 (GIMs)： 他们在 Stable Diffusion 上进行了测试。在这里，攻击非常奏效。他们可以成功检测到水印并高成功率地移除它，证明了安全性的主张是虚假的。

“修复方案”以及为什么它们很难

研究人员提出了三种修复这些漏洞的方法：

改变数值： 让“锁”变得更大、更复杂。
修复洗牌： 重写生成密钥的代码，使其不再产生重复项。
增加更多噪声： 让系统能够承受更多的“雨水”，从而使“噪声叠加”攻击失效。

难点在于：
为了实现真正的安全（即 128 位安全性，这是行业金标准），研究人员计算得出，该“水印”的长度将需要超过目前任何 AI 一次性能生成的最大文本量。

类比： 这就像试图把一份 100 页的合同塞进一张明信片里。目前的 AI 模型（如 GPT-4）根本没有足够的“空间”（输出长度）来承载一个真正不可破解的水印。

总结

这篇论文是对一种新型 AI 水印技术进行的“压力测试”。

好消息： 研究人员发现了缺陷，并提出了修复建议。
坏消息： 当前版本的这项技术并不安全。它很容易被检测到或被移除。
现实检查： 即便有了修复方案，这项技术仍面临物理极限：目前的 AI 模型太短了，无法承载一个真正不可破解的水印。

作者得出结论：虽然这个想法很有前景，但在进行重大改进之前，我们目前还不能信任这种特定的“隐形墨水”来保护 AI 内容。

技术摘要：基于 LDPC 的伪随机纠错码的密码分析

问题陈述

伪随机纠错码（PRC）在 CRYPTO 2024 上提出，这是一种新型密码原语，旨在为大型生成模型（LLMs）和生成图像模型（GIMs）提供不可检测的水印技术。LDPC-PRC 作为 PRC 的主要实例化形式，依赖于低密度奇偶校验（LDPC）码，并声称其安全性基于学习带噪声问题（LPN）和植入异或（planted XOR）问题的难度。

尽管具有强大的理论渐近保证，但在实际参数设置下，LDPC-PRC 的具体安全性（concrete security）仍未得到探索。现有文献表明，PRC 可能容易受到拟多项式时间区分攻击的影响，但尚未进行严格的分析来量化这些漏洞在现实世界部署场景中的影响。这一差距使得基于 PRC 的水印方案在面对实际对手时的不可检测性和鲁棒性未经证实。

研究方法

本研究对 LDPC-PRC 进行了首次具体密码分析，重点关注两种特定的水印方案： $\Pi_{LLM}$ （用于文本生成）和 $\Pi_{GIM}$ （用于图像生成）。作者提出了三种针对该方案不可检测性和鲁棒性的新型攻击，并在源自最先进模型（DeepSeek 和 Stable Diffusion）的现实参数配置下分析了它们的复杂度。

1. 新型密码攻击

作者设计了三种具有不同目标的攻击：

攻击-I（部分秘密密钥恢复）： 该攻击针对不可检测性属性。通过使用中间相遇（MITM）方法改进信息集解码（ISD）算法，对手可以从公钥中恢复出秘密密钥的部分行向量。这些恢复的向量使对手能够以极高的概率区分 PRC 编码的码字与随机向量，从而有效地破坏了不可检测性。
攻击-II（弱密钥区分器）： 该攻击利用了密钥生成过程（$KeyGen $）中的漏洞。作者观察到，在当前的实现中，公钥矩阵$ G$ 包含相同行的概率是非忽略的（即“弱密钥”）。对手可以通过检测这些统计上的非均匀性，在处理线性时间内区分带水印的内容与随机噪声，从而绕过复杂的密钥恢复过程。
攻击-III（噪声叠加攻击）： 该攻击针对鲁棒性属性。通过利用伴随式解码（Syndrome Decoding）恢复原始伯努利噪声向量 $e$ ，对手构造一个恶意叠加向量 $e'$ 。该向量的设计使得当其与码字相加时，总噪声权重超过解码器的纠错阈值，从而导致解码失败（移除水印）。至关重要的是，该攻击利用了理论噪声界限与实际实现中观察到的较低具体噪声率之间的差距。

2. 具体复杂度分析

作者使用针对 $\Pi_{LLM}$ 和 $\Pi_{GIM}$ 的特定参数集分析了这些攻击的时间和数据复杂度。他们推导了理论界限（定理 1–3），并利用具体参数对这些界限进行了验证，计算出比特安全水平（例如 $2^{46}$ 、 $2^{60}$ ），而非仅仅依赖渐近表示法。

3. 现实世界评估

为了验证实际威胁，作者在 DeepSeek（LLM）和 Stable Diffusion（GIM）上实现了 $\Pi_{LLM}$ 和 $\Pi_{GIM}$ 。他们评估了攻击的成功率以及对内容质量的影响。值得注意的是，他们发现对于 $\Pi_{LLM}$ ，实现可检测的水印需要高 Token 熵，这会严重降低文本的可读性，使得该方案在高质量文本生成方面变得不切实际。

核心贡献与结果

1. 破坏不可检测性

攻击-I： 证明了部分秘密密钥恢复是可行的。对于 $\Pi_{GIM}$ ，在所有参数选择下，安全水平均低于 46 位。对于 $\Pi_{LLM}$ ，该攻击以极高的概率成功。
攻击-II： 揭示了在特定参数（如 $t=3, 4$ ）下，弱密钥在 LLM 和 GIM 方案中出现的概率几乎为 100%。这使得多项式时间内的区分攻击成为可能，完全破坏了这些情形下的不可检测性。

2. 破坏鲁棒性

攻击-III： 证明了在噪声叠加攻击下， $\Pi_{LLM}$ 的安全水平对于 $n \le 2^{17}$ 不会超过 75 位。对于 $\Pi_{GIM}$ ，由于较低的具体噪声率（ $\eta \ll \rho$ ），其具体安全水平低于 60 位。
实验验证： 在 Stable Diffusion 上，作者实现的实现水印移除成功率在 67% 到 96% 之间（取决于扰动界限 $\delta$ ），证明了鲁棒性极易受到破坏。

3. $\Pi_{LLM}$ 的实际局限性

对 DeepSeek 的评估揭示了一个根本性的权衡：为了满足 LDPC-PRC 的纠错界限，LLM 必须生成高熵（低置信度）的 Token。这导致生成的文本要么是不可检测的（低熵），要么是不可读的（高熵）。因此，作者得出结论， $\Pi_{LLM}$ 对于高质量文本的现实世界水印是不切实际的。

4. 提出的防御措施

论文提出了三种缓解策略：

参数建议： 增加码长 $n$ 和行权重 $t$ 可以提高攻击复杂度。然而，要达到 128 位安全性需要 $n > 2^{24}$ ，这超过了当前最先进 LLM 的最大输出长度（ $2^{15}$ ）。
修订密钥生成： 提出了一种使用高斯消元法的改进版 $KeyGen$ 算法（算法 2），用以消除生成弱密钥的可能性，从而缓解攻击-II。
实现调整： 对于 GIM，建议增加所添加噪声向量的权重，以缩小理论噪声率与具体噪声率之间的差距，从而提高攻击-III 的复杂度。

重要性与主张

本文声称提供了对 PRC 的首次系统性安全评估，弥合了渐近理论与实际部署之间的鸿沟。作者断言：

安全保证被削弱： LDPC-PRC 所声称的安全性在所有实际可行的区间内都是不足的。攻击者可以以远低于 128 位的成本，以极高的概率检测出水印。
LLM 的实际不可能实现： 由于大型生成模型固有的约束（特别是输出长度和 Token 熵），通过 LDPC-PRC 实现 128 位安全性的 LLM 水印目前是不切实际的。
需要严格评估： 本研究强调，当考虑到特定的实现细节（如密钥生成启发式算法和噪声率）时，理论上的硬度假设（LPN/planted XOR）并不会自动转化为具体安全性。

作者总结道，虽然基于 PRC 的图像水印可能仍有可接受质量的实际应用案例，但目前用于 LLM 的 PRC 需要在广泛部署前，对参数和实现策略进行重新评估。