前言

翻译一下Crypto 1989最后的一个小故事：How to Explain Zero-Knowledge Protocols to Your Children

特别有趣的一个小故事，打算写一下翻译，可能是之前给小伙伴讲图三染色问题的时候没讲明白，这个故事应该能更好的帮助理解

阿里巴巴的奇怪洞穴

故事发生在很久以前，在巴格达市，住着一位名为阿里巴巴的老人，阿里巴巴每天都会去集市上买卖一些物品

今天要讲的故事，一部分是关于阿里巴巴的，另一部分则关于一个神秘的洞穴，这个神秘洞穴的秘密一直流传至今日

一天，在巴格达的集市上，一个大盗从阿里巴巴那儿抢走了一个钱包，于是阿里巴巴为了抓住大盗追了他一路

但是大盗逃进了一个洞穴，这个洞穴的进去之后在一个岔路分成了两个黑暗的蜿蜒的通道，一条在洞穴左侧，一条在右侧（大概是下面这个图）

但是洞穴太黑，阿里巴巴并没有看清大盗走的是左边还是右边的通道，阿里巴巴不得不选择该走哪条路，于是他选择左边，但是左边的通道是一条死胡同

阿里巴巴从岔路口沿着左侧的通道一直找，找到通道的尽头，都没有找到大盗，此时阿里巴巴心想，大盗可能在另一侧的通道内

于是他又回到岔路口，从右侧的通道开始仔细搜查，但是他发现右侧也是一条死胡同，而且仍然没有发现大盗

阿里巴巴犯愁了，自言自语道：“这个洞穴好奇怪啊，大盗到底跑去哪了呢，会不会是大盗选择的右侧的路，在自己进入左侧后，大盗又从右侧溜出洞穴了呢”

第二天，阿里巴巴和以往一样，来到集市卖东西，但是另一个大盗偷走了阿里巴巴的篮子，和前一天一样，阿里巴巴追着大盗来到了这个古怪的洞穴，但是他又没有看到大盗走的是左侧还是右侧

这次，阿里巴巴决定选择右侧，但是和前一天一样，阿里巴巴从岔路口一直搜查到尽头，都没有发现大盗

阿里巴巴想，今天的大盗可能和昨天一样，大盗运气好，呆在了自己没有选择的那条路，等待自己进到另一条路之后，又偷偷从岔路口溜出去了

日子一天天的过去，阿里巴巴每天都会来到集市买卖物品，但是每天都有大盗从他这儿偷走一些东西，每次阿里巴巴总会追着大盗来到这个古怪的洞穴，但是没有任何一天阿里巴巴抓住了大盗

在第四十天，大盗偷走了阿里巴巴的头巾，和之前的39个大盗一样，这个大盗跑进了这个古怪的洞穴

阿里巴巴还是没有看到大盗选择的哪条路，这次阿里巴巴决定搜查左侧的道路，但是直到道路的尽头，他还是没有找到大盗

这时候阿里巴巴想，可能这第四十个大盗和前面的39个大盗一样，很幸运的选择了另一侧的道路，但是这个解释过于牵强了，以至于阿里巴巴自己都不相信

如果真的是这四十个大盗运气这么好，不太可能，因为这四十个大盗都能成功的逃过阿里巴巴的搜查的概率不足万亿分之一（$\frac{1}{2^{40}}$）

因此阿里巴巴觉得此事必有蹊跷，阿里巴巴开始怀疑这个古怪的洞穴一定有什么不可告人的秘密

于是阿里巴巴决定找到这个洞穴的秘密，另一天，阿里巴巴提前来到了这个古怪的洞穴，并沿着右侧通道走到尽头，躲在了角落的一个大石块后面

经过长时间的等待，他发现有一个大盗进来了，大盗感觉到自己正在被追赶，因此大盗跑到通道的尽头，对着墙壁悄悄地说了一句咒语“芝麻芝麻，请开门”

阿里巴巴惊讶的发现墙壁竟然神奇的移动了，露出了一个狭窄的洞口，大盗穿过洞口之后，墙壁又合上了

等到追赶者到来的时候，追赶者发现这是一条死胡同，除了几个大石块以外什么都没有，于是追赶者非常沮丧地离开了，而大盗又一次的逃走了

虽然大盗逃走了，但是阿里巴巴很是兴奋，因为他发现了这个古怪的洞穴的秘密

在追捕者走了之后，阿里巴巴尝试了大盗使用的咒语，他惊奇地发现，当 墙壁滑开之后，右侧的通道和左侧的通道竟然是相连的，现在阿里巴巴知道之前的四十个大盗是如何逃出来的了

之后阿里巴巴不断地尝试这个咒语，并发现了一个修改咒语的方法，通过修改咒语，阿里巴巴在第二天抓住了一个大盗

阿里巴巴非常激动，用一张手稿记录了这个故事和他的发现，阿里巴巴并没有记录他修改的新的咒语，但是在手稿中记录了一些关于咒语的微妙的线索

手稿的命运

后来，阿里巴巴的手稿在中世纪的意大利出版，之后流传至今，目前保存在美国波士顿，而这个手稿最近引起了几位好奇的研究者的兴趣，通过解密这些阿里巴巴留下的线索，研究者甚至解密了阿里巴巴的新的咒语

经过对巴格达老集市废墟的多次考古发掘，研究者找到了这个古怪的洞穴，尽管过了几个世纪，但是这个神奇的咒语依然有效，好奇的研究人员兴奋的穿过了两个道路尽头之间的墙壁

在这些研究人员中，有一位研究人员叫米克·阿里，他可能是阿里巴巴的后代，他想证明他知道这个洞穴的秘密，但是他并不想透露这个秘密

电视台很快就发觉到巴格达正在发生一件非同凡响的大事件，一家美国的大电视台甚至获得了这个故事的独家报导权，他们来到了巴格达，打算报导这件事

一位电视台的工作人员先用摄像机记录了两条死胡同的内部细节，之后所有人离开洞穴，再由米克·阿里一人独自走进洞穴，并在岔路口按照他的心意选择了一条通道走进去

随后，电视台的工作人员带着摄像机来到了岔路口，并在此投掷一枚硬币，如果是正面朝上，则他会要求米克·阿里从右侧走出来，如果是反面，则要求米克·阿里从左侧走出来

第一次抛硬币的结果是正面，工作人员大声的喊道：“米克，请从右侧通道走出来！”

为了纪念阿里巴巴与这四十个大盗的故事，米克·阿里与工作人员重复了四十次，每次都是所有人退到洞穴入口，然后米克独自走进其中一条通道，再由摄影师走到岔路口，通过抛硬币的方式命令米克走出来的道路，因为米克的确知道咒语，因此他成功的完成了这四十次试验

因为米克知道咒语，因此对于摄影师的任何要求，米克都可以顺利的完成，但是如果是一个不知道咒语的人，在第一次失败之后就会被发现

嫉妒的记者

另一家电视台的记者知道这件事情之后，也想拍摄这个古怪的洞穴的故事，他找到了米克，但是米克拒绝了他，因为米克已经将这个故事的独家转播权给了第一家电视台

但是调皮的米克给了记者一个建议，就是这个故事可以在不掌握咒语的情况下拍摄出来，嫉妒的记者思考了一下，似乎想通了，同时记者想到，他甚至认识一个身材和外貌都与米克非常相似的朋友，如果找他来拍摄，观众很可能会误以为这就是米克本人

于是嫉妒的记者开始准备拍摄，在拍摄过程中，因为替身米克并不知道这个洞穴的咒语，因此对于记者的要求，替身米克不知道如何从洞穴的一侧穿到另一侧，从而导致这次拍摄失败

但是嫉妒的记者非常聪明，他编辑了拍摄的磁带，只保留了那些成功的拍摄结果，直到他们成功拍摄了四十次为止

这两个故事由两个相互竞争的电视台在同一时间播出，后来这件事情被高尚了法庭，并提供了两个故事拍摄时的录像带作为证据，然而法官和专家们都无法区分这两份磁带，到底是谁抄袭了谁，仅凭磁带还不足以判断

对于嫉妒的记者所拍摄的磁带，并没有透露出任何关于这个洞穴的秘密，但是它仍然和真正的原版拍摄的磁带无法区分，所以真正的磁带也没有透露出关于这个洞穴的秘密，即便是获得独家转播权的电视台确信米克·阿里知道这个洞穴的秘密，但是他仍然不能在法庭上为这个嫉妒的记者定罪

无论评判结果如何，米克·阿里都已经达成了他的目标，事实上他的目标就是在不透露洞穴秘密的情况下，证明自己拥有洞穴的秘密，也就是石墙的咒语

并行试验

与此同时，以色列的一些研究人员观察到，通过使用几个秘密并同时进行测试，可以减少录像磁带中场景的数量（换句话说就是身份验证的长度）

他们想象了一栋高高的公寓，公寓的每一层内都包含着一个有秘密的洞穴，对于这个特殊的公寓，他们需要为每一层的洞穴额外招募一位演员，但是拍摄的时候，所有的楼层（也就是所有的拍摄场景）可以同时进行拍摄，和之前一样，观察演员出现的位置，后来这些研究人员甚至提出了一种算术解决方案，也就是用一个数字作为证明的回答来取代多个演员，这样就不用招募多个演员了

然而，在秘密的数量和拍摄场景之间存在一个权衡，因为当秘密数量变得越来越多的时候，连续尝试变得越来越不实用，因为秘密的增加会导致错误概率越来越高，当我们不能连续尝试的时候，我们就没有秘密的传递了吗？

预先协定

以上的所有都引起了一些欧洲有研究者的兴趣，他们设计了一个可以顺序观察和并行观察的版本，为了节省拍摄时间，嫉妒的记者和替身米克会变得很聪明，他们考虑提前商定一份包含四十个随机选择的列表，在拍摄过程中，嫉妒的记者假装在脑海中随机选择问题，而事先知道将要被问到的问题的替身米克不需要知道秘密，仍然可以通过接连的测试

通过上述方法，可以在只保留成功拍摄场景的连续拍摄过程中，添加了一种证明者（替身米克）和验证者（记者）之间的先验一致性的技术

一次测试，一个秘密

为此，我们构建了一个新的洞穴，在岔路口有更多的分叉，就像下面这样

显然，当通道的数量增加的时候，洞穴的物理结构也会进行相应的变化，虽然说建造一个具有一万亿条通道的洞穴极其不现实，但是无论有多少通道，都可以通过事先约定的协定进行

一个更加算术的方案将允许验证者从一万亿个问题中选择一个问题，通过一次测试，使得其直接做到与在洞穴中通过两次通道进行四十次成功测试相同的安全级别

后记

读完这篇小故事，受益匪浅，之前本科的时候没学过零知识相关的东西，至少没有很系统的学习过，只是知道密码学中有这样的工具，但是实际上并不知道它是基于什么难题构建的，也不知道其到底如何安全的应用以及通过这个零知识证明来构建一些更多的协议

相对系统的入门零知识协议之后，发现这篇故事讲了三个零知识协议中比较核心的概念

一个是零知识证明，也就是米克向电视台证明自己知道洞穴的咒语，但是不告诉电视台

第二个是模拟的概念，模拟实际上和嫉妒的记者的做法很类似，虽然嫉妒的记者和替身米克并不知道洞穴的咒语，但是依然可以通过减掉失误的录像带来呈现一个，或者说假装一个我知道咒语的假象

第三个就是承诺，实际上承诺的目的是为了减少模拟的时间，因为每次都抛一次硬币很浪费时间，通过承诺的方式可以大大缩短时间，放到实际协议执行中就意味着可以缩短协议执行的时间，以此来降低通信量和开销

这些概念打算在以后认真在博客里面写一下，但是可能会有表述不到位的地方，还请大佬多多指出

参考文章

$[1]$ Jean-Jacques Quisquater, Myriam Quisquater, Muriel Quisquater, Michaël Quisquater, Louis C. Guillou, Marie Annick Guillou, Gaïd Guillou, Anna Guillou, Gwenolé Guillou, Soazig Guillou, Thomas A. Berson:How to Explain Zero-Knowledge Protocols to Your Children. CRYPTO 1989: 628-631