一个密码学证明可以通过让缺失的模拟器难以被证明来隐藏其秘密

诀窍不在于证明秘密被隐藏了

从零知识最简单的版本开始。

Alice 想让 Bob 相信一道数独题有解。如果她把答案发给 Bob，Bob 会被说服，但谜题也就毁了。她想要的是更奇妙的东西：证明答案存在，却不透露答案。

这就是零知识证明所作出的承诺。证明者（Alice）让验证者（Bob）相信某个陈述为真，同时除了该陈述为真的事实之外什么也不透露。

问题在于，这个承诺是有代价的。普通数学证明有两个令人安心的特点。它是一条消息：你把证明写下来，交出去，然后离开。它还具有完美可靠性：错误的陈述根本不存在有效证明。经典的不可能性结果表明，零知识必须放弃这两个特点——而且不是只能同时放弃两个；单独保留其中任何一个也不行。

首先，零知识证明需要对话。如果 Alice 发送一条消息，且事先没有安排可信设置，那么零知识保证就会崩溃——无论你愿意用多少可靠性来交换它，这一点都成立。

其次，零知识证明需要对错误保留一点小小的容忍度。事实证明，要求完美可靠性会悄悄摧毁交互性：一个无论验证者作出哪种随机选择都永远不会被骗的验证者，不妨事先固定这些选择——而一旦验证者变得可预测，Alice 就能用一条消息回答所有问题，这恰恰又回到了已经导致问题的情形。

Rahul Ilango 的论文讨论的是绕开这两重限制的一种方法。它既不假装限制不存在，也不试图在不可能的设置中制造经典零知识。这个转折更微妙：削弱“什么也不透露”的含义，但以一种保留密码学家实际能够检验的安全性质的方式削弱它。

结果被称为有效零知识（effectively zero-knowledge）。

旧测试：模拟器存在

形式化零知识的经典方法使用了一个虚构的助手，叫作模拟器。

想法是这样的：设想 Jane，她不知道 Alice 的秘密。如果 Jane 完全靠自己就能生成看起来与 Bob 从 Alice 那里收到的证明一样的证明，那么 Alice 的证明就没有教给 Bob 任何新东西。即使没有 Alice 的秘密，Jane 也能伪造出同样的体验。

所以经典零知识要求一个真正存在的模拟器。必须有一种高效算法，在不知道秘密——术语称为见证；对于数独而言，见证就是填好的网格——的情况下，生成看似真实的伪造证明。

这个定义很强，但旧有的不可能性恰恰也从这里下手。直观地说，真正非交互的证明只是一串字符串。Bob 得到这串字符串后，可以把它展示给别人：他获得了向其他人证明该陈述的能力，这听起来已经超过了“什么也没有”。经典定理把这种直觉精确化为前面那些不可能性结果。

超级数独版本的差异

下面用一种刻意简化的方式来感受这种差异。

在类比中，不要把普通的 9×9 数独用于严肃部分。它太小，也太有限：计算机可以直接解出来，或者证明它无解。相反，设想一族 MegaSudoku(n) 谜题。把通常的规则放大：选择一个区块大小 n，令 N = n^2，构造一个 N×N 的网格，将其分成 n×n 的区块，并使用 N 个符号。普通数独只是很小的 n = 3、N = 9 情形：9×9 网格、3×3 区块和九个符号。只有当允许 n 增长，并且网格能够携带额外组件，使其表现得像披着数独外衣的 SAT 公式时，证明复杂度的故事才真正开始。SAT 公式不过是一列真假约束：能否给变量赋予真/假值，使每个约束都得到满足？

这个见证仍然很容易想象。Alice 知道超级数独的一份完整有效填法。Bob 想确信这样的填法存在，但 Alice 不想透露它。如果她把完整填法发送出去，Bob 会被说服，但秘密也就消失了。

在经典零知识版本中，Alice 和 Bob 会进行交互。一种老式的直观模型使用盖住的牌片。Alice 把解好的网格藏起来，在每一轮开始前秘密重命名符号，然后让 Bob 检查一个随机选出的局部约束：一行、一列、一个区块或一个组件。如果打开的单元格显示的符号彼此不同，Bob 就更有信心。然后所有内容重新盖住，符号也重新随机命名。（有一个小问题：题目给出的提示需要额外技巧，因为重命名也会把提示隐藏起来。下面的说明会解释经典协议如何解决这一点；对于接下来的内容，这个玩具模型已经够用了。）

这不是论文中的协议，而是经典零知识的思维模型：

• Alice 和 Bob 来回交互。
• Bob 选择随机检查项。
• Alice 只揭示局部一致性，而不是整个解。
• 隐私证明的方式是说明：Bob 所看到的内容可以在没有 Alice 的秘密解的情况下生成。

因此，经典零知识围绕一个正面事实构建：

模拟器确实存在。

现在去掉那些令人安心的部分。Alice 发送一条证明字符串，然后离开。没有可信设置，没有预先准备好的共享随机字符串，而且 Bob 绝不能接受错误的谜题。这正是经典零知识无法存活的设置。

在这个诀窍出现之前，还需要再介绍一个角色。固定一套规则手册：在逻辑学意义上的形式证明系统——一组固定公理，加上检查书面数学证明的机械规则。ZFC，即数学的标准公理，是典型例子。从这里开始，所有内容都相对于一套预先选定的规则手册来陈述，而且选择很灵活：无论你固定哪套规则手册，构造都能运行，包括 ZFC。

（关于措辞，沿用论文自身的一条说明：“证明系统”在这里始终指这套规则手册——检查数学证明的形式系统——绝不指 Alice 发送的消息。Alice 和 Bob 所使用的机制称为“证明者和验证者”。）

Gödel 式版本保留超级数独的故事，但改变证明方式。

选取第二个表示规模相同的约束系统，称为 D。在这个故事里，S 和 D 是同一格式的两道 MegaSudoku(n) 谜题。在幕后，D 可能源自一个规模不同的困难逻辑公式；如果需要，可以用无害的虚拟约束把它补齐，使其适合相同网格。D 来自一个实际不可满足的逻辑公式：不存在任何赋值能让它的全部约束为真，就像一道损坏的谜题没有合法完成网格。一个玩具例子是同时要求“X 为真”和“X 为假”的公式。因此 D 没有有效填法。

但 D 不能是一道很容易被揭穿的坏谜题。上面的玩具例子就不行：任何规则手册都能用一行证明反驳“X 且非 X”。D 必须是假的，却不能让所选规则手册用简短论证证明它为假。如果规则手册能用短证明反驳 D，下面的故事就会崩溃：那条本来可能在不知道 Alice 秘密的情况下产生证明的替代路径，就能被形式地排除，隐私保证也会随之消失。因此，D 要从这样一族公式中选取：所选规则手册无法高效反驳它们；在该规则手册内，没有短证明能证明 D 无解。

于是，Alice 的单消息证明针对的是一个二选一陈述：

要么真正的超级数独 S 有解，要么诱饵 D 有解。

这就是逻辑连接。D 不是通过某种神奇方式生成的，使得 S 因而为真。证明并不是在论证“D 无解，因此 S 有解”，而是在证明析取式 S 或 D。完美可靠性意味着错误的析取式不可能有有效证明。由于 D 在现实中为假——它没有解——析取式为真的唯一可能就是 S 为真。因此，如果证明被接受，S 就必须有解。诱饵不能让一个错误的 S 变成真的。

但对于零知识风格的部分，要问的是：如果 D 确实有解，会发生什么？那份诱饵解会充当替代见证。它能让某人在不知道 Alice 的真实超级数独解的情况下生成证明——换句话说，就是一个模拟器。在现实中 D 没有解，所以这条模拟路径被关闭了。关键在于，规则手册无法高效证明它已经关闭。

因此 D 有两个任务。对于可靠性，D 是假的，所以“ S 或 D”的有效证明会迫使 S 为真。对于有效零知识，D 很难被反驳，所以规则手册无法迅速排除那条本来会使模拟成为可能的诱饵路径。

所以安全测试不再是：

我们能证明模拟器确实存在吗？

而变成：

你的规则手册能高效证明模拟器不可能存在吗？

如果答案是否定的，就会得到一个出人意料的强结论：任何安全保证，只要（a）可以通过运行测试观察到，且（b）能在该规则手册内证明会由模拟器的存在推出，就确实成立。因为，若能成功攻破其中任何一项，本身就等于给出了那份不存在的短反驳。这正是“有效零知识”中“有效”的含义。

因此，课堂式的对比是：

经典零知识： 因为模拟器存在，所以证明是安全的。

Gödel 式有效零知识： 对于可观察的安全测试，因为规则手册无法高效证明模拟器不可能存在，所以证明被视为安全。

第二种说法更弱。这也正是论文能够保留那三个让经典版本陷入困境的特征的原因：一条消息、无设置和完美可靠性。

新测试：你无法证明模拟器不存在

Ilango 的放宽改变了问题。

经典零知识问的是：

模拟器存在吗？

有效零知识问的是一个更弱的问题：

你选定的规则手册能高效证明不存在模拟器吗？

这听起来像技术性迂回，但它正是核心思想。这个构造处在一种奇怪状态：模拟器实际上并不存在——论文对此说得很明确——但你固定的规则手册无法高效证明它不存在。如果你关心的每个坏后果都需要这样一份反驳，那么对于这些后果，系统仍然表现得像零知识。

Gödel 就是在这里登场的。他不是装饰，也不是“Gödel 让密码学变得安全”。这种联系是证明论意义上的。若一套规则手册在精确定义下是可能的最佳规则手册，就称其为最优：每当任何规则手册能够用短证明反驳某类相关公式时，最优规则手册也能做到，而且证明长度至多多项式倍增长。Krajíček 和 Pudlák 在 1989 年猜想，不存在最优证明系统：无论固定哪套规则手册，都会有另一套规则手册能把某族真陈述证明得简洁得多。这是证明复杂度的核心开放猜想之一，也是 Gödel 不完备性定理在有限、复杂度理论中的近亲：某些真陈述在你固定的规则手册中没有短证明——并非因为它们原则上不可证明，而是因为每套固定规则手册都会留下一些表述很短、却没有短证明的真命题。

论文假设这个猜想成立（采用密码学中使用猜想时的标准、略强的“无穷多次”形式）。根据 Krajíček 和 Pudlák 的定理，其具体收益是：对于每套规则手册，都存在一族确实不可满足、规则手册无法用短证明反驳的公式——更关键的是，还存在一种高效算法能够生成它们。后一性质称为统一生成性（uniformity），也就是由同一个高效过程生成整族公式。它把整个想法从存在性主张变成了 Alice 真能运行的算法：她的诱饵 D 来自流水线，而不是凭空出现。

密码学的转折在于利用这种证明能力的不足。

构造在做什么

下面保留论文构造的骨架。

固定一套规则手册——比如 ZFC。在证明复杂度假设下，存在一列能够高效生成的公式，它们实际上不可满足，但规则手册没有关于其不可满足性的短证明。

现在构造一种如下形式的单消息证明：

要么真实陈述可满足，要么这个特殊的困难公式可满足。

特殊困难公式并不可满足。因此，如果底层证明机制具有完美可靠性，接受该消息仍然意味着真实陈述为真。这就给出了完美可靠性。

但对于类似零知识的安全性，设想特殊困难公式假如可满足。它的见证就可以用来模拟证明，而不需要知道真实见证。公式在现实中并不可满足——但规则手册无法高效证明这一点。因此，它也无法高效证明模拟器不可能存在。

这就是关键。系统不是靠产生经典模拟器来隐藏秘密，而是对于一大类可观察的安全测试，利用规则手册无法证明模拟器不存在这一点来隐藏秘密。

论文声称了什么

主定理分为几层。核心结果是：

在一个标准密码学假设——存在非交互见证不可区分证明，这类经过充分研究的构造可以由若干已经建立的假设推出——以及“不存在（无穷多次的）最优证明系统”这一证明复杂度猜想下，论文对每套规则手册都构造了一个用于 NP/SAT 的单消息证明者和验证者：它具有完美可靠性、无设置，并且相对于该规则手册是有效零知识的。（各类谜题问题通常都可以归结为 NP/SAT 这个标准的困难核心；超级数独只是它的一种外观。）

对于关于保留可证伪安全性质的更宽泛主张，论文又增加了一个标准假设，即去随机化信念 P = BPP（粗略地说，随机性不会给算法带来本质上的额外能力）。

脱离定理语言后，可以这样说：

• 证明只有一条消息。
• 没有可信设置。
• 错误陈述无法被证明。
• 证明者不是经典零知识的——它没有模拟器。
• 但经典零知识的每一种可证伪、基于博弈的安全后果，都能在这种设置下实现。

“可证伪”很重要。它意味着安全失败可以通过在一个博弈中运行攻击者来测试。许多密码学安全定义都是这种形式：攻击者能否区分两条密文、求逆某个函数、恢复见证，或赢得某个指定实验？定理针对每个可证伪性质分别给出一个证明者。一个同时享有所有可证伪性质的单一证明者很可能不可能存在——旧有的可复用性攻击（“Bob 可以把证明展示给别人”）本身就是一种可证伪性质，而它在这里确实失败。论文提出的是：单个证明者或许可以覆盖所有自然的可证伪性质——即密码学实践中实际出现的那些性质——但这一部分是建立在“自然”这一非形式化概念及一个明确猜想之上的条件性结论。该保证针对的是可观察的失败，而不是每一种哲学意义上或基于模拟的保密含义。

有一个具体推论值得点名：该构造产生了首批具有统一证明者的非交互见证隐藏证明——这里的统一证明者，是指由同一套高效程序处理整族实例；也就是说，“关于一道谜题的证明不会帮助你找到它的解”，而且无交互、无设置——这是一个听起来并不惊天动地、却几十年来一直难以构造的对象。

这并没有说什么

这一节是为了让文章保持诚实。

它没有说旧的不可能性定理错了。这个构造是通过改变定义来绕开它们的。

它没有给出无交互、无设置且完美可靠的普通经典零知识。论文明确说，构造出的证明者没有模拟器。

它不意味着证明无法复用。单消息证明仍然可以展示给其他人；论文没有保留类似可否认性的性质。（带可信设置的非交互零知识也有同样限制。）

它不意味着这是可以立即部署的实用协议。这是复杂度理论和密码学基础研究。结果依赖证明复杂度和密码学中的重大假设，构造讨论的是原则上什么能够实现。

它没有把“Gödel”变成神奇的安全原语。Gödel 的联系来自证明系统、最优证明系统以及不完备性的有限类比。可用的直觉不是“不完备性保护你的密码”，而是：如果规则手册无法高效证明模拟器不可能存在，那么需要这份证明的攻击就能在安全定义层面被阻断。

为什么它仍然有趣

密码学经常把困难转化为安全性。因式分解很难，所以 RSA 式假设变得有用。格问题很难，所以格密码学变得有用。这里的困难更奇特：不是“计算秘密很难”，而是“证明某个证明对象不存在很难”。

这就是论文让人觉得不寻常的原因。它几乎把公理和规则手册当成了密码学资源。通常的不可能性结果说，可靠性和模拟之间存在张力。Ilango 的做法是把这种张力放到证明论的帷幕后面：模拟器并不存在，但形式系统无法高效揭露它的不存在。

对读者来说，令人惊讶的地方不在于它会取代今天的零知识系统。至少不会直接取代。令人惊讶的是，数学逻辑中的一种限制可以被建设性地利用：它不只是墙，也可以是一种遮蔽物。

证据有多强？

这是一篇定理论文，所以“证据”的含义不同于生物学或天文学论文。问题不是实验是否得到复现，而是定义、假设和证明链是否支持这一主张。

证明是形式化的，论文也明确列出了自己的假设。这些假设并不随意。非交互见证不可区分证明是密码学中经过充分研究的标准构造，可以由若干已经建立的假设推出。“不存在最优证明系统”是证明复杂度中的核心猜想。P = BPP 是一种标准去随机化信念，论文只在关于可证伪性质的更宽泛定理中使用它。

论文还论证了这些假设是合理的代价，而非随意搭设的脚手架：它证明了一个逆向结论，说明这些假设在本质上是必要的——如果这类构造确实存在，那么非交互见证不可区分证明必须存在，而且（假设标准的单向函数存在）最优证明系统不能存在。并且这些假设具有“双赢”性质：反驳其中任何一个，都将本身成为证明复杂度、密码学或复杂度理论中的里程碑发现。

但由于结果是有条件的，对它的信心也必须是有条件的。如果这些假设不成立，定理的解释就会改变。即使假设成立，这一保证也不是完整的经典零知识，而是论文所提出的、基于证明论的放宽版本。

因此，恰当的信心程度是：对于论文确立了一种连贯的条件性可能性结果，我们有较高信心；对于这些假设是否描述了我们实际生活的密码学世界，我们有中等信心；对于任何眼下的实用后果，我们的信心较低。

为什么重要

论文打开了一条本来被认为已经关闭的道路。

经典理论说：没有设置时，完整零知识不可能只有一条消息，也不可能具有完美可靠性。Ilango 的论文说：如果我们只要求那些能够在安全博弈中测试的零知识后果，并允许安全定义依赖于规则手册能够或不能高效反驳的内容，那么许多有用行为都可以恢复——同时保留一条消息、无设置和完美可靠性。

这不是一个微小的定义调整，而是思考密码学保证的一种不同方式。不要只问什么存在，也问你的规则手册能够排除什么。不要把不可证性当成哲学上的麻烦，而要把它当成一种结构。

现实世界明天或许不会改变。但概念地图变了。现在有一种形式化意义上的说法：对于我们希望从“秘密没有泄露”中得到的许多基于博弈的保护，“没人能高效证明秘密已经泄露”可能已经足够强。

这就是为什么 Gödel 会出现在标题里。

简明总结

零知识证明让证明者能够在不透露见证的情况下，使验证者相信某个陈述为真。经典不可能性结果表明，零知识无法在无设置的情况下压缩成一条消息，也无法具有完美可靠性。Rahul Ilango 的论文没有反驳这些不可能性。它定义了一个较弱的概念，即有效零知识：它不要求模拟器确实存在，而要求一个选定的证明系统——像 ZFC 这样的形式规则手册——无法高效证明不存在模拟器。在密码学的重要假设（非交互见证不可区分证明）和证明复杂度假设（不存在最优证明系统）下，论文为 NP/SAT 构造了无设置、完美可靠的单消息证明者，并且逐一实现零知识性质的可证伪、基于博弈的后果。一个覆盖所有“自然”此类性质的单一证明者，是更进一步、部分依赖猜想的扩展——而覆盖字面意义上的每个可证伪性质很可能不可能，因为证明仍然可以复用。这个结果是理论性的、有条件的，不是已经部署的原语；但它展示了把证明论上的不可证性当作密码学资源的一种新方式。

不忽悠检查

论文展示了什么： 在给定假设下，可以构造用于 NP/SAT 的单消息、无设置、完美可靠证明者；相对于任意选定的证明系统，它们是有效零知识的，并实现经典零知识的每一种可证伪、基于博弈的后果。

合理但尚未无条件证明的内容： 所需的证明复杂度和密码学假设确实成立。这些是严肃且经过充分研究的假设——论文也说明它们既基本必要又足够——但它们仍然是假设。

它没有展示什么： 无交互、无设置且完美可靠的经典零知识；可立即部署的实用系统；证明的可否认性或不可复用性；或者 Gödel 不完备性定理本身就能保护密码学。

主要局限： 这一保证是零知识的放宽版本；最宽泛的版本依赖多个假设；关于单一通用证明者的主张仍有一部分属于猜想；而且这一结果主要是基础性的。

普通读者应有多大信心？ 如果接受这些定义，应当高度相信这是一个重要的条件性理论结果；对这些假设是否符合现实，保持中等信心；对立即实际部署，保持低信心。稳妥的结论是：论文没有打破零知识不可能性，而是找到了一条新的证明论路径，绕过其中与许多安全博弈有关的部分。