阿里巴巴和四十大盗在寻宝途中遇到了难题,他们需要完成一个地图三染色游戏才能获得宝藏,阿里巴巴知道地图如何三染色,四十大盗不知道,阿里巴巴该如何在不告诉四十大盗答案的情况下,向四十大盗证明自己知道地图三染色的方法呢?
阿里巴巴先将红绿蓝随机分配三个数字,之后将数字写在纸片上,面朝下盖在地图上。阿里巴巴可以让四十大盗随机选择两个临近的区域进行检验(Verify),翻开盖着的纸片,查看纸片上的数字是否不同。然后阿里巴巴重新给红绿蓝分配三个数字,重复上述的步骤。最后,阿里巴巴可以向四十大盗证明,如果他不知道染色方案,那么每次都能满足四十大盗检验的概率无限趋向于0,这样阿里巴巴就在不告诉四十大盗地图如何染色的情况下,向四十大盗证明了自己知道染色方案。
阿里巴巴和四十大盗在寻宝途中遇到了难题,他们需要完成一个数独游戏才能获得宝藏,阿里巴巴知道数独的答案,而四十大盗不知道,阿里巴巴该如何在不告诉四十大盗答案的情况下,向四十大盗证明自己知道数独的答案呢?(为了让四十大盗不要伤害自己)
假设黑色是数独的题面,红色是数独的解。阿里巴巴先制作81张数字1~9的卡片,黑色位置数字朝上,红色位置数字朝下,这样四十大盗并不能看到具体的解。阿里巴巴可以让四十大盗选择,是按行、按列还是按格子检验(Verify),假设四十大盗选择按行检验,阿里巴巴将每行的卡片放到一个袋子里,把卡片打乱,然后打开让四十大盗查看数字是否为1~9,这样按行、按列和按格子的检验可以重复进行多次。最后,阿里巴巴可以向四十大盗证明,如果他不知道数独的答案,那么每次都能满足四十大盗检验的概率无限趋向于0,这样阿里巴巴就在不告诉四十大盗数独答案的情况下,向四十大盗证明了自己知道数独的答案。
这个故事就是一个典型的「交互式zk」,也称作「IZK」,阿里巴巴和四十大盗经过多轮的交互,最后阿里巴巴除了向四十大盗证明自己确实知道数独的答案,没有透露一点关于答案的知识,四十大盗到最后依然对数独的答案一无所知。
《阿里巴巴与四十大盗》里讲的'是阿里巴巴无意中发现了强盗的财宝,强盗得知此事前来报仇,却被阿里巴巴用智慧除掉了的故事。
易书科技
【每周五更新】 粉色阿拉伯童话系列之阿里巴巴与四十大盗是阿拉伯最脍炙人口的童话故事,阿里巴巴的机智勇敢无不牵动着读者的心,故事节奏明快,一个个奇特诡异的想象撑起了一幅幅色彩斑斓的阿拉伯风情画卷,变幻莫测的神奇故事,东方式的哲理和隐喻都在其中巧妙的体现。
其他