阿里巴巴的零知识证明

奥卡姆剃刀

战争中你被俘了，敌人拷问你情报. 你是这么想的：如果我把情报都告诉他们，他们就会认为我没有价值了，就会杀了我省粮食;但如果我死活不说，他们也会认为我没有价值而杀了我. 怎样才能做到既让他们确信我知道情报，但又一丁点儿情报也不泄露给他们呢？

这的确是一个令人纠结的问题，但阿里巴巴想到了一个好办法，当强盗向他拷问打开山洞石门的咒语时，他对强盗说：“你们离我一箭之地，用弓箭指着我，你们举起右手我就念咒语打开石门，举起左手我就念咒语关上石门，如果我做不到或逃跑，你们就用弓箭射死我. ”

强盗们当然会同意，因为这个方案不仅对他们没有任何损失，而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题. 阿里巴巴也没有损失，因为处于一箭之地的强盗们听不到他念的咒语，不必担心泄露了秘密，而且他确信自己的咒语有效，也不会发生被射死的悲剧.

强盗举起了右手，只见阿里巴巴的嘴动了几下，石门果真打开了;强盗举起了左手，阿里巴巴的嘴动了几下后石门又关上了. 强盗还是有点不信，说不准这是巧合呢，他们不断地变换着节奏举右手、举左手，石门跟着他们的节奏开开关关，最后强盗们想，如果还认为这只是巧合，自己未免是一个傻瓜，那还是相信阿里巴巴吧！

“零知识证明”说的是示证者向验证者表明他知道某种秘密，不仅能使验证者完全确信他的确知道这个秘密，同时还保证一丁点儿秘密也不泄露给验证者. 阿里巴巴的这个方案，就是认证理论“零知识证明”的一个重要协议.

除了被俘后如何靠情报保命这个问题，零知识证明在社会领域中还有着很多应用场合. 例如你证明了一个世界级的数学难题，但在发表出来之前，总得找个泰斗级的数学家审稿吧？于是你将证明过程发给了他. 他看懂后却动了歪心思，他把你的稿子压住，把你的证明用自己的名义发表，他名利双收，你郁闷至死. 你去告他也没用，因为学术界更相信的是这位泰斗，而不是你这个无名之辈.

这并不是天方夜谭，而是学术界常见的难题，前些年有个博士生状告他的泰斗级导师剽窃他的成果，但除了令师生关系恶化外没有任何效果，最后他使出了撒手锏，称他在给导师审阅的论文的关键公式中，故意标错了一个下标，而这会导致整个推导失败. 学术委员会一查果真如此，但还是有倾向于泰斗的声音，有人说那是泰斗的笔误，只不过让你发现了而已，并不能证明那公式就是你推导出来的.

这个博士生故意标错下标，不能说他没有心眼，但他没有把“零知识证明”理论用好，以至于落到这种地步. “零知识证明”早在1986年就被A. Fiat和A. Shamir用数学的方法给出了解决方案，并在同年申请了美国专利，但由于该理论可能被用于军事领域，专利局被军方密令搁置，6个月后，军方命令“该申请发表后会有害于国家安全……所有美国人的研究未经许可而泄露将会被判刑罚款”. 看来军方认为作者肯定是美国人了，但作者实际上是在美国申请专利的以色列人，研究也是在以色列的大学里做的，军方这个命令摆了个大乌龙，虽然两天后撤销了，但已经成为了学术界的笑柄.

这个笑柄也说明了一个问题，即“零知识证明”非常重要. 基于数学的推理虽然非常复杂，但思路却很简单，上述的阿里巴巴方案就是其中之一. 其他的一些方案，也都是像这样遵循着“分割和选择协议“的.

例如数学中有个“哈密尔顿回路问题”， 其大意是在任意给定的一个图中，能不能找到这样的路径，即从一点出发，不重复地走过所有的结点（不必通过图中每一条边），最后又回到原出发点. 如果“科学松鼠会”（一个科学传播公益团体，试图通过自己的努力使科学传播并流行开来）贴了一张全连通图（命名为A图）悬赏哈密尔顿回路，而且任命我作为评审官，你幸运地找到了一条这样的回路，那该怎么办呢？将结果直接发给我吗？千万不要！因为说不准我会将你的成果让给我的亲信. 那你该怎么办呢？应该这么做：

1. 你将A图的顶点弄乱，并生成一张新图，只是顶点的位置变了，而新图顶点之间的连线关系与A图是完全一致的. 这时，你清楚新图中每个顶点与A图中每个顶点的对应关系，而且你也知道新图中的哈密尔顿回路.

2. 你将这张新图发给我（没错，就是仅仅一张新图），上面并没有画着你发现的精彩回路.

3. 我收到后，对你提出两个问题中的一个：一是证明新图就是从A图变形过来的，所有顶点和连线的关系完全一致;二是画出新图中的哈密尔顿回路.

4. 如果你真的找到了A图的哈密尔顿回路，这两个问题当然都能轻松回答. 需要注意的是，你只需要回答第3步的其中一个问题，千万不要两个问题一并回答，否则我就知道你关于A图的哈密尔顿回路了.

5. 我还是不相信你，因为有可能你只是将A图变了形，却根本不知道A图的哈密尔顿回路，而我在第3步时恰好要求你证明新图就是从A图变形过来的，你当然能证明. 或者有可能你找了个你知道哈密尔顿回路的图，但这张图跟A图一点关系都没有，而我在第3步恰好要求你画出这张图的哈密尔顿回路.

6. 我要求你从第1步开始重复这个验证过程，随着次数的增加，第5步那种巧合的可能性就越来越低，如果你多次能回答对第3步中的问题，那我还不相信你已经找到了A图的哈密尔顿回路，那我就是一个傻瓜.

7. 为了表明我不是傻瓜，我会在“科学松鼠会”群博里宣布你找到了A图的哈密尔顿回路，而这时我并没有看到你所画的A图的哈密尔顿回路.

现在，我们回到你证明了世界级的数学难题这个问题上来，你可以用这种分割和选择协议来进行零知识证明，从而保护你的权利. 你公开声称你解决了这个数学难题后，验证者会给你出一个其他的题，而能做出这道题的前提条件是已经解决了那个数学难题，否则的话无解，而且这个条件是学术界所公认的，这个题就是所谓的平行问题. 不出所料，你靠着已经解开数学难题的基础把这个平行问题做出来了，但验证者还是不相信，他又出了一道平行问题，你又做出来了，多次较量后，验证者就确信了你已经解决了那个数学难题，虽然他并没有看到具体的解法.

大家已经看出来了，零知识证明需要示证者和验证者的密切配合，但如果你只是一个数学界的无名之辈，即使你宣称解决了数学难题，也不会有人跟你配合着玩零知识证明，那你该怎么办呢？

我告诉你一个可以在法庭上都能当作有效证据的招数. 你将证明打印好，选择一个最可靠、最权威的邮政公司，把它寄给自己，当你收到这个盖着邮戳的包裹后，不要打开，把它放好，然后就可以把证明寄给数学泰斗了. 如果他用自己的名义发表了，不必着急，等他依靠其影响力把这个证明炒热后再出手. 你上法庭控告他，他当然不承认，在法庭上你就将那个没开封的包裹拿出来，上面清清楚楚地盖着时间戳，这就证明了包裹里的证明是发生在那个时间戳之前的，加上之后的你邮给泰斗论文的邮件存根，和泰斗以自己名义发表论文的时间，三者就构成了一个完整的证据链，泰斗灰头土脸名声扫地，而你则会大获全胜名利双收.endprint