💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

本文引入了一种基于置换码猜想的新型伪随机码构造方法，该方法同时实现了亚指数级安全性、针对二进制字母表最坏情况编辑的鲁棒性，以及对持有检测密钥的攻击者的抵抗力，从而克服了以往水印方案的关键局限性。

原作者： Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

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

想象一下，你是一位著名的作家，正在创作一部小说。你想证明某一段落是由你写的，而不是由模仿者或人工智能编写的，但你又不想改变故事的内容或让它看起来很奇怪。你需要一种方法，在文本内部隐藏一个只有你能找到的秘密“签名”，即使有人试图编辑、删除或打乱这些词句，该签名依然有效。

这篇论文旨在构建一个更强大的版本，这种系统被称为伪随机码（Pseudorandom Code, PRC）。可以将 PRC 想象成一台神奇的加密机器，它能将一条秘密信息转化为一长串看似毫无意义的乱码。如果你拥有密钥，就可以将这些乱码还原回原始信息，即使它们已经被弄乱了。

以下是使用简单类比对该论文成就进行的分解：

1. 问题所在：旧有的签名太容易被破解了

以前，研究人员确实构建了这些签名系统，但它们存在三个重大缺陷：

“拟多项式”缺陷： 想象一把锁，计算机需要大约一百万年才能破解。这很好，对吧？但旧的锁实际上可以在“拟多项式”时间内被破解——这意味着对于计算机来说，这可能只需要几天时间而不是一百万年。它的长期安全性不够高。
“字母表”缺陷： 旧系统如果能够改变整个字母表（比如把所有的 'A' 换成 'Z'）效果会很好。但真实的文本（如英语）拥有一个较小的、固定的字母表（26个字母）。旧系统无法处理仅改变少数字母或删除一个单词的情况，否则签名就会失效。
“密钥”缺陷： 如果黑客知道了你的秘密密钥，他们可以轻易地通过微小的改动来移除你的签名。旧系统假设黑客是蒙着眼睛的；如果黑客戴上了眼镜，这些系统就失效了。

2. 解决方案：“置换拼图”

作者创建了一个基于他们称之为**“置换码猜想”（Permuted Codes Conjecture）**的概念的新系统。

想象你拥有一幅美丽而复杂的马赛克图案（即代码）：

打乱瓷砖： 你随机打乱瓷砖的位置（索引置换/Index Permutation）。
重绘瓷砖： 你拿起画笔，随机重新涂抹每块瓷砖的颜色（字母表置换/Alphabet Permutation）。
撒上尘埃： 你在整个图案上撒上一层随机的尘埃（噪声/Noise）。

作者声称，如果你执行了这三个步骤，结果看起来就像一堆随机的、毫无意义的尘埃。对于没有密钥的人来说，他们无法分辨这堆“打乱的马赛克”与“随机尘埃”之间的区别。这使得签名具有不可检测性（它不会破坏文本的质量）。

3. 三大突破

该论文声称同时解决了上述所有三个问题：

超强安全性： 他们声称他们的新锁非常坚固，即使是运行了很长时间的超级计算机也无法分辨他们的打乱马赛克与随机尘埃之间的区别。
对编辑具有鲁棒性（“编辑”问题）： 这是最大的突破。他们的系统可以承受编辑。如果黑客删除了一个单词、增加了一个错别字或调换了句子的顺序，系统仍然可以找到签名。
- 类比： 想象一条写在长纸条上的信息。如果有人剪掉几个词、粘入新词或打乱顺序，旧系统就会失效。新系统则像是一个即使碎片受到轻微损坏或移动，依然可以被解开的谜题。
对“知晓密钥”的黑客具有鲁棒性： 即使黑客知道秘密密钥，他们的系统依然有效。
- 类比： 通常情况下，如果小偷知道了保险箱的密码，他们就可以打开并取出里面的东西。作者建造了一个即便小偷知道组合键也无法取出隐藏物品的保险箱，因为一旦尝试取出，保险箱本身就会被破坏。这使得任何人都可以验证水印，而不仅仅是受信任的第三方，且不会破坏系统。

4. 他们是如何做到的（“折叠”技巧）

为了使该系统适用于真实的文本（这类文本的每个单词具有较低的“熵”或随机性），他们使用了一种特殊的数学代码，称为折叠里德-索罗蒙尼代码（Folded Reed-Solomon codes）。

类比： 想象你正试图发送一条秘密信息，但你只能发送短促、断续的数据流。旧的方法是一个字母一个字母地发送。新方法则是“折叠”你的信息。与其发送“A, B, C”，不如发送一个代表“A, B 且 C”的单一数据块。这使得系统能够将更多信息打包进文本中，而不需要文本本身具有高度的随机性或混沌性。

5. “代价”（一个假设）

作者承认他们正在做一个重大的假设。他们赌的是这个“置换拼图”（打乱的马赛克）确实是无法与随机尘埃区分开的。

他们并没有从数学上证明这是绝对无法破解的（目前还没有人能证明这种特定类型的拼图是绝对无法破解的）。
然而，他们展示了：
1. 它是通过另一个著名且经过深入研究的密码学假设（置换拼图）推导出来的。
2. 他们尝试用许多不同类型的攻击手段（例如尝试寻找尘埃中的模式）来破解它，但都失败了。
3. 他们证明了如果你漏掉了这三个步骤中的任何一个（打乱、重绘或撒尘），系统就会变得容易破解。这表明这三个步骤都是必不可少的，并且系统是稳健的。

总结

这篇论文引入了一种全新的、超安全的 AI 生成文本水印技术。它声称是第一个实现的系统，具备以下特点：

几乎无法被检测到（看起来就像普通的文本）。
能在重度编辑（错别字、删除、重写）下幸存。
即使攻击者知道秘密密钥也能正常工作。

他们通过将文本转化为一个“打乱的拼图”来实现这一点，这个拼图依赖于一个新的数学假设，他们根据大量的测试以及与其他既定数学理论的联系，认为这个假设极有可能是正确的。

技术摘要：基于置换谜题（Permuted Puzzles）的改进型伪随机码

问题陈述

人工智能生成内容的激增使得识别来源的鲁棒水印方案变得至关重要。近期的研究表明，伪随机码（Pseudorandom Codes, PRCs） 等同于具有强鲁棒性和质量保证的水印方案。PRC 是一种秘密密钥加密方案，其密文在计算上与均匀分布不可区分（确保不可检测性/质量），且解密算法能够容忍高比例的错误（确保鲁棒性）。

然而，现有的 PRC 构建方法存在三个关键局限性：

安全性弱： 所有先前的构建方案都易受到拟多项式时间区分攻击（quasipolynomial-time distinguishing attacks）。它们依赖于隐藏 $(\log n)$ -稀疏结构，这使得暴力搜索攻击成为可能。
字母表鲁棒性有限： 虽然某些构建方案可以处理编辑错误，但它们需要多项式大小的字母表。现实中的文本（例如来自大语言模型）具有低熵特性（约每词 1 bit），因此需要一种对常数大小（理想为二进制）字母表上的编辑具有鲁棒性的 PRC。
对抗模型较弱： 先前的研究假设对手是计算受限的，或者缺乏检测密钥。目前尚不清楚 PRC 是否能在面对拥有检测密钥的计算无界对手时依然保持鲁棒（即强自适应鲁棒性）。

核心开放性问题在于：是否有一种单一的构建方式能同时实现亚指数级安全性、二进制字母表上的编辑鲁棒性，以及针对持有密钥的对手的鲁棒性。

方法论

1. 置换码猜想（The Permuted Codes Conjecture）

作者引入了一种新的计算硬度假设——置换码猜想。该猜想认为，一组“打乱”的含噪码字分布在计算上与均匀分布是不可区分的。

分布 $D_{n,\Sigma,C,\eta,T}$ 的生成过程如下：

采样一个随机索引置换 $\sigma \in S_n$ 和字母表置换 $\pi_1, \dots, \pi_n \in S_\Sigma$ 。
从线性码 $C \subseteq \Sigma^n$ 中均匀采样 $T$ 个码字 $c_1, \dots, c_T$ 。
对于每个码字，通过 $\sigma$ 置换索引，并通过 $\pi_j$ 置换每个位置的符号，得到 $\hat{c}$ 。
对 $\hat{c}$ 应用噪声率为 $\eta$ 的替换信道。

核心洞察： 作者证明了该猜想由置换谜题猜想（Permuted Puzzles Conjecture）（此前用于双效私密信息检索）所蕴含。他们提供了统计证据，表明对于常数大小的字母表和具有高对偶距离的码，极少量的样本在统计上是均匀的。此外，他们还论证了所有三个组成部分（索引置换、字母表置换和噪声）都是必要的；若省略字母表置换（如在“玩具”版本中），则会导致 Reed-Solomon 码可以通过低度多项式攻击被区分出来。

2. 构建编辑鲁棒的 PRC

为了实现二进制字母表上的编辑鲁棒性，作者基于折叠 Reed-Solomon (FRS) 码构建了 PRC。

编码： 秘密密钥由置换和一次性填充（one-time pad）组成。进行编码时，将底层码的一个随机码字进行置换、加噪，然后选择其中一部分符号。关键在于，每个选定的符号都作为包含符号值及其索引的二进制字符串输出。
解码： 解码器接收一个可能被编辑（插入/删除）破坏的字符串。它会扫描所有特定长度的子串，尝试通过“暴力破解”编辑距离来恢复潜在的（索引, 符号）对。这些候选对象构成了每个位置的列表。随后，对这些列表应用底层码的**列表恢复算法（list-recovery algorithm）**以恢复原始码字。
鲁棒机制： 通过在输出中包含索引，解码器即使在位置因插入或删除而发生偏移的情况下，也能恢复正确的符号，只要编辑数量在限定范围内。使用 FRS 码使得系统即使在字母表实际上是二进制的情况下（通过转换），也能容忍常数比例的编辑。

3. 水印转换

利用 Christ 和 Gunn (CRYPTO '24) 建立的框架，作者将其 PRC 转换为自回归语言模型的水印方案。该方案通过将 token 选择偏向于 PRC 码字位来生成带水印的文本。PRC 对编辑的鲁棒性直接转化为水印在面对对抗性文本修改时的能力，前提是模型具有足够的单 token 熵。

核心贡献与结果

1. 具备三种属性的新型 PRC 构建

本文提出了第一个同时满足以下条件的 PRC 构建方案：

合理的亚指数安全性： 基于置换码猜想，避免了易受拟多项式攻击的稀疏结构。
二进制字母表编辑鲁棒性： 该构建方案能容忍常数比例的最坏情况编辑（插入、删除、替换）。
强自适应鲁棒性： 即使对手已知检测密钥且计算能力无界，该方案依然保持鲁棒。

2. 理论保证

定理 5.6： 在置换码猜想下，存在一个具有亚指数安全性、对常数比例编辑具有强自适应性的二进制字母表 PRC。
定理 5.14： 在针对 Folded Reed-Solomon 码的变体猜想下，存在一个不可检测的 LLM 水印，该水印在仅需常数单 token 熵率 $\alpha$ 的情况下，能对常数比例的编辑（ $\tilde{O}(\alpha^7)$ ）保持鲁棒。这是第一个在现实熵约束下同时具备不可检测性和最坏情况编辑鲁棒性的水印。

3. 密码分析与证据

字母表置换的必要性： 作者证明，如果没有字母表置换，即使存在索引置换和噪声，Reed-Solomon 码也会被高效地从随机分布中区分出来。
先前工作的拟多项式攻击： 他们展示了很大一类先前的 PRC 构建（那些依赖于植入稀疏结构或噪声容忍谓词的方案）本质上容易受到拟多项式时间攻击。
统计均匀性： 他们证明了对于常数大小的字母表，少量置换后的码字在统计上与均匀分布不可区分，这为该猜想的有效性提供了证据。

重要意义

本文声称解决了此前被认为在理论上无法同时实现的三个 PRC 理想属性之间的矛盾。通过形式化 置换码猜想 并利用 Folded Reed-Solomon 码，作者为水印方案提供了理论基础，使其具备：

不可检测性： 与真实的语言模型输出无法区分。
鲁棒性： 能够抵御文本的对抗性编辑（插入/删除）。
安全性： 对持有检测密钥的攻击者具有韧性，从而在不损害鲁棒性的情况下实现公开验证。

这项工作确立了实现这些属性需要超越稀疏结构，转而拥抱“区分置换、含噪码字与随机字符串之难度”这一核心。虽然安全性依赖于一个新的猜想，但作者提供了强有力的证据证明其有效性，并展示了其在实现实用的、鲁棒的 AI 生成文本水印方面的潜力。