三位研究者找到了如何构造一个证明，可以在完全分散信息的同时保持完全秘密。
原文：https://www.quantamagazine.org/computer-scientists-combine-two-beautiful-proof-methods-20241004/
作者：Ben Brubaker
译者：Kurt Pan
你会如何证明某件事是真的？对数学家来说，答案很简单：从一些基本假设开始，逐步前进，直到得出结论。 QED，证明完成了。如果在任何地方有错误，仔细阅读证明的专家应该能够发现它。否则证明就一定是有效的。 2000 多年来，数学家们一直都遵循这一基本方法。
然而，在 20 世纪 80 年代和 90 年代，计算机科学家重新思考了一个证明可以是什么。他们开发了一系列令人眼花缭乱的新方法，当尘埃落定之后，其中的两个发明显得格外重要了：零知识证明，可以让一个充满怀疑的人相信一个陈述是真实的，且无需揭示为什么它是真实的；以及概率可检查证明，可以说服读者相信一个证明的真实性，即使他只看过证明中的一些微小片段。
https://www.quantamagazine.org/how-to-prove-you-know-a-secret-without-giving-it-away-20221011/ https://www.quantamagazine.org/how-computer-scientists-learned-to-reinvent-the-proof-20220523/
“对我来说，这是所有理论计算机科学中最美丽的两个概念，”剑桥大学计算机科学家Tom Gur 说。
没过多久，研究者对将这两种类型的证明结合起来的尝试就开始了。他们在 20 世纪 90 年代末通过使用每种条件的较弱版本取得了部分胜利。几十年来，没有人能够将零知识的理想版本与概率可检查性的理想版本合并起来。
直到现在。在一篇标志着七年工作高峰的论文中，对一类重要的问题，Gur和另外两位计算机科学家最终将两种证明的理想版本结合起来了。
http://arxiv.org/abs/2403.11941
“这是一个非常重要的结果，”理论计算机科学家兼 StarkWare 公司（该公司开发零知识证明的密码学应用）创始人Eli Ben-Sasson 说道。 “它解决了一个非常古老且众所周知的开放问题，这个问题长期以来一直在困扰着包括我在内的研究者。”
请检查
故事始于 20 世纪 70 年代初，当时计算机科学家开始形式化地研究他们要求计算机解决的问题的困难度。其中许多问题都有一个重要的性质：如果有人找到了一个有效的解，他可以很容易地让持怀疑态度的“验证者”相信它确实是有效的。反过来，验证者总是能够发现是否存在错误。具有这种性质的问题属于研究者所称为 NP 的类。
要理解这种验证是如何工作的，考虑这个经典的 NP 问题：给定一张划分为不同区域的地图，是否可以仅使用三种颜色来填充之，满足不给相邻区域以相同的颜色？根据地图的不同，这个问题可能会非常困难。但是如果你设法找到了一个有效的着色，你可以通过向验证者展示正确着色的地图来证明这一点。验证者只需要看一眼每个边界即可。
十年后，两名研究生开创了一种不同的方式来思考数学证明。加州大学伯克利分校的 Shafi Goldwasser 和 Silvio Micali 一直想知道是否有可能防止在线扑克游戏中的作弊行为。这需要以某种方式证明每个玩家手中的牌是随机抽取的，同时又不能透露这些牌是什么。
Goldwasser 和 Micali 在1985 年与多伦多大学计算机科学家 Charles Rackoff 共同撰写的一篇开创性论文中发明了零知识证明，响亮地肯定回答了他们自己的问题。第二年，Micali 和另外两名研究人员发表了一篇论文，表明 NP 中任何问题的解都可以使用一个特定类型的零知识证明来验证。
https://dl.acm.org/doi/10.1145/22145.22178 https://dl.acm.org/doi/10.1145/116825.116852
为了了解这些证明，假设你还是想要说服验证者某个特定的地图是可三着色的 - 但这一次，你不希望验证者学到如何自己为其着色。你可以通过交互式过程来证明，而不是画出一个例子。首先在地图上着色，然后用黑色胶带小心地覆盖每个区域，只留下边界可见。验证者随机选择一个边界，你将打开两侧的区域，显示两种不同的颜色。
现在，重复多次这个过程，在每轮之前随机切换着色方案，以使验证者无法拼凑出有关你的解的任何一致信息。 （比如，交换红色和蓝色区域并保持绿色区域不变。）如果你是在虚张声势，验证者最终会找到地图上颜色不正确的地方。如果你说的是实话，你将能够在与使用标准方法验证证明所需的时间相同的时间内说服一个具有合理怀疑的验证者。
这种零知识证明在两个方面与标准方法显著不同：它是一个交互式过程而不是一个文档，以及每个参与者都依赖随机性以确保其他人无法预测他们的决定。但也由于这种随机性，现在总是有可能使得一个有缺陷的证明被认为是有效的。尽管如此，很容易使这种概率变得极小，计算机科学家也很快就克服了对这种宽松的证明定义的不适感。
正如加州大学洛杉矶分校的计算机科学家 Amit Sahai 所说，“如果某事不正确的概率小于宇宙中粒子数分之一，那么我们称其为一个证明似乎也是合理的。”
非常酷的证明 （PCP)
研究者很快意识到，随机交互式证明的作用不仅仅在于隐藏秘密信息。它们还可以轻松验证比 NP 问题困难得多的问题。交互式证明的一种类型甚至适用于名为 NEXP 的类中的所有问题。如果使用普通的证明，这些问题的解的验证时间可能与解决最难的 NP 问题所需的时间一样长。
https://ieeexplore.ieee.org/document/89520
这场证明革命最终带来了一个令人惊讶的发现：你可以在没有任何交互的情况下仍然拥有交互式证明的全部力量。
原则上，消除交互性很简单。 “证明者列出他可能从验证者那里得到的所有可能的挑战，然后提前写下所有的答案，”Sahai说。问题是，对于像 NEXP 中最难的问题这样的复杂问题，生成的文档将会非常庞大，太长以至于根本无法从头到尾读完。
接着在 1992 年，计算机科学家 Sanjeev Arora 和 Shmuel Safra 定义了一类新的非交互式证明：概率可检查证明（PCP）。他们与其他研究者一起证明了 NEXP 问题的任意一个解都可以用这种特殊形式重写。虽然 PCP 比普通证明更长，但验证者只需读取一些小片段即可对其进行严格检查。这是因为 PCP 有效地成倍增长并分散了普通证明中的任何错误。试图在普通证明中找到错误就像通过啃一片吐司来寻找一小块果酱一样。PCP“将果酱均匀地涂在面包上”，Gur说， “无论你在哪里咬一口，没关系，你总会找到的。”
https://dl.acm.org/doi/10.1145/273865.273901 https://dl.acm.org/doi/10.1145/226643.226652
关键因素还是随机性——验证者对片段的选择必须是不可预测的，以确保不诚实的证明者无法在任何地方隐藏不一致。
Arora、Safra 和其他人表明，PCP 还可以显著加快更平常的 NP 问题的验证速度。不久之后，Arora 和其他四位研究者进一步改进了 PCP，将 NP 证明验证的速度推向了理论极限——这一著名的结果被称为 PCP 定理。
https://dl.acm.org/doi/10.1145/278298.278306
“这被认为是理论计算机科学的重大成就之一，”以色列海法理工学院的密码学家Yuval Ishai 说。
通往 PCP 定理的道路绝非一帆风顺。研究者从使用交互性和随机性的对NP 问题的零知识证明开始。然后他们意识到类似的证明可以用来验证更困难问题的解。最后，他们表明，通过将这些证明转换为非交互式 PCP，他们可以用比阅读证明所需的时间更少的时间来验证一个解。计算机科学家们感到了胜利的喜悦。
然而，在接下来的几年里，一些研究者开始思考在此过程中丢失了什么。事实证明，将证明转换为 PCP 暴露了零知识证明旨在隐藏的一些信息。有什么办法可以两全其美吗？
信息太多
不幸的是，概率可检查性和零知识性之间存在固有的紧张关系。问题始于 PCP 的非交互性。普通的零知识证明依赖交互性来限制验证者对私有信息的访问。一个非交互式证明只是证明者发给验证者的文档，恶意的验证者可能更关心窃取证明者的秘密而不是去检查解。
“这并不像只是掩盖他们应该看到的东西那么简单，”剑桥大学研究生 Jack O'Connor 说，他与 Gur 一起发表了新结果。 “要无论他们如何去检查证明，我们都一点可以掩盖它。”
一个验证者可以从头读到尾的证明是不可能达到零知识的。（除非你假设特定类型的加密是不可被攻破的）。相反，研究者专注于为 NP 之外的超难问题制作 PCP 的零知识版本，因为这些 PCP 尽管太长而无法完整阅读，但仍然是可验证的。这个零知识版本必须在证明的每个部分分散信息，以保持证明者的诚实，但同时以某种方式防止证明除了其正确性之外泄露任何内容，无论验证者读取哪个片段。
https://dl.acm.org/doi/10.1145/62212.62222
1997 年，三名研究者克服了这些挑战，构造了一种零知识 PCP，适用于 NEXP 中的任何问题，但需要付出一定的代价。他们必须在验证者检验证明的方式中添加回一点点交互性——这与 PCP 没有任何交互性的通常情况不同。
https://dl.acm.org/doi/10.1145/258533.258643
“你先看一下，然后思考一下，然后再回去看另一部分，”Sahai 说。而对于普通的 PCP，“你可以在一开始就决定要阅读证明的哪一小部分。”
这个结果还使用了一种达不到理想状态的零知识形式，因为验证者可以了解一些额外信息的机会虽小但非零。这对于密码学中零知识证明的所有实际应用来说已经足够好了。但一些研究者还是无法抗拒“完美零知识”的诱惑——一种即使允许交互式证明也并不总是可能的条件。
绝对零度
在接下来的 20 年里，一些研究者改进了 1997 年论文中的方法，使零知识 PCP 在密码学应用中更加有用。但基本的限制仍然存在。在 2017 年，一位名叫 Nicholas Spooner 的伯克利研究生（现在在康奈尔大学）开始怀疑他帮助为解决一个相关问题开发的技术可能也有助于构造完美零知识 PCP。
https://eprint.iacr.org/2016/988
Spooner向当时在伯克利大学担任博士后的Gur提出了这个想法。Gur 并不相信，而且他在接下来的一年里都在试图证明这是不可能的。但有一天早上，在伯克利的一家咖啡馆里，Spooner 向他展示了一个简单的技巧，消除了新方法中最明显的障碍，之后他改变了主意。
“我有点悲观，而他则比较乐观，”Gur 说。 “他赢了。”
两位研究者聚焦在关于 NP 问题解的数量的“计数问题”，例如“给定一张地图，可能有多少种不同的有效着色？”有一个使用巨大的多维数字表来构造对此类问题的 PCP 的标准方法，验证者可以将某些条目加到一起以得到答案，并将其他条目加到一起以检查证明者是否保持诚实。但单个数字的值揭示了额外的信息，因此这些 PCP 并不是零知识的。在 Spooner 的新方法中，证明者通过在表中添加随机性来隐藏这些值，且验证者将能够检查这种随机性不会扭曲最终的总和。
Gur 和 Spooner 断断续续地合作了五年多，但他们无法解决所有细节问题。O’Connor 于 2023 年加入了该团队，三人意识到关键的缺失部分可能会在他们共同研究的一篇看似无关的论文中找到。经过秋天最后的一次共同努力，三位研究者将所有的内容整合到了他们的新论文中。结果是针对所有计数问题的一个完美零知识 PCP。此外，这些 PCP 的验证过程也是完全非交互式的。
https://eprint.iacr.org/2023/587
“他们同时突破了两个障碍，” Ishai 说。 “我印象极其深刻。”
Spooner、Gur 和 O'Connor 研究的计数问题属于一类称为 #P（发音为“sharp P”）的问题，其难度介于 NP 和 NEXP 之间。三位研究者现在的目标是将他们的新技术扩展到 NEXP 中的所有问题，以匹配 Arora 和 Safra 原始论文中 PCP 的能力。这将是向一个类似于原始 PCP 定理证明，但具有完美零知识作为额外的好处的东西迈出的一大步。 Gur 很乐观，因为他们的新方法相当于一个已经在 PCP 定理中发挥关键作用的技术的零知识版本。
https://dl.acm.org/doi/10.1145/146585.146605
新的证明方法通常还会在计算机科学的其他分支中得到应用——这是研究者对这项新工作感到兴奋的另一个原因。
“这很可能会重新激发起人们对零知识 PCP 的兴趣，”Ishai 说。 “这可能会导致理论计算机科学的其他进展。”事实再次证明，“证明”充满惊喜。
