静园5号院前沿讲座 | Silvio Micali谈证明、私密与计算
关键词：密码学，证明系统
编者按
2019年6月12日，麻省理工学院Ford讲席教授、2012年图灵奖获得者Sivio Micali受邀在静园五院做了题为“交互式证明系统、零知识证明与计算能力”的主题报告，详细介绍了交互式证明和零知识证明的相关内容，最后提出了一些做科研的建议。报告由中心讲席教授邓小铁主持，听众包括来自北京大学信息学院、数学学院，以及清华大学、中国科学院等单位的师生和科研人员。
Micali教授报告中
证明由数学符号和推理组成，是理论计算机学家关注的重点。很多数学问题需要复杂的符号定义和非常长的证明。如何设计更简单的机制验证证明的正确性，是一个重要问题。
证明由证明者（Prover）和验证者（Verifier）构成。假设证明者有无穷计算能力，而验证者只有多项式时间的计算能力。我们认为，多项式时间可以被验证的证明都相对高效。以图同构为例，两张图中点的对应关系构成了图同构问题的证明，并且它能在线性时间内验证。
定义NP为能在多项式时间证明解的存在性的问题的集合。类似地，co-NP描述了证明NP问题无解的问题集合；#P描述了计算NP问题解的个数的问题集合；PSPACE描述了能用多项式空间验证的问题集合。后面这三类问题用传统方法很难解决。以计算解的个数为例，我们如果列举出所有解，这将会需要指数时间。
这就需要我们引入新的证明系统。交互式证明系统描述了证明者和验证者通过相互传递信息来验证证明。在课堂上，老师可以解答同学的问题，这种交流促进了知识的流通，这说明了信息交互的作用。
下面以图同构为例描述交互式证明：给定两图G,H，想要证明G,H不同构，只需要
Verifier随机选G,H中一张图（假设选择了G），再从G的同构图中随机选一张图C交给Prover；
Prover计算得到C与G同构，把G返还给Verifier。
如果G与H不同构，Prover总会选择正确的图。如果G与H同构，那么Prover在一次实验中有一半的几率选择错误的图，重复试验多次就能提高Prover有至少一次选错的概率，从而以高概率发现两图同构。上述例子可以让我们看到交互式证明的优势，实际上它的计算能力与PSPACE相等。
交互式证明在实际中有很大用处。以云计算为例，用户将计算任务交给运行商，为了防止运行商不计算而随便返回一个结果，运营商需要用交互式证明的方法让用户验证答案的正确性。
在很多情形下，我们不仅要向对方证明答案的正确性，还不能将答案告诉对方，即验证者除了“正确”这个性质之外没有得到任何信息。这样的证明被称为零知识证明。
依然以图同构为例，想要零知识地证明G,H同构，只需要
Prover随机生成G的同构图（也是H的同构图）C交给Verifier；
Verifier随机选择G,H之一（假设为G），要求Prover给出G,C的同构对应关系；
Prover将对应关系交给Verifier。
如果G,H不同构，那么Prover有一半的几率不能在第三步中给出对应关系，重复试验即可发现G,H不同构。而如果G,H同构，无论Verifier在第二步中选择哪个图，Prover都能给出对应关系。
为什么说这是零知识的呢？因为Verifier可以模拟两人间的对话，即模拟出所有的信息交流。更具体来说，如果Verifier自己不会算G,H的同构关系，那么它动用自己的算力（即模拟双方交流）也不可能得到这个对应关系的。所以这个证明没有泄露额外信息。
Micali教授报告现场
随后，Micali教授分享了自己的科研故事。在他刚刚提出交互式证明时，由于文章的想法非常超前，没有会议接收这篇文章。直到三年之后，文章才成功发表。到今天，交互式证明已经成为理论计算机、密码学非常重要的研究领域。由此可见做科研中善于思考、敢于坚持的重要性。
文字整理 | 霍明佳
现场照片 | 曹倩倩
往 期 报 告
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转报告信息