阿里巴巴与四十大盗介绍

阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个地图三染色游戏才能获得宝藏，阿里巴巴知道地图如何三染色，四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道地图三染色的方法呢？

阿里巴巴先将红绿蓝随机分配三个数字，之后将数字写在纸片上，面朝下盖在地图上。阿里巴巴可以让四十大盗随机选择两个临近的区域进行检验（Verify），翻开盖着的纸片，查看纸片上的数字是否不同。然后阿里巴巴重新给红绿蓝分配三个数字，重复上述的步骤。最后，阿里巴巴可以向四十大盗证明，如果他不知道染色方案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗地图如何染色的情况下，向四十大盗证明了自己知道染色方案。

阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个数独游戏才能获得宝藏，阿里巴巴知道数独的答案，而四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道数独的答案呢？（为了让四十大盗不要伤害自己）

假设黑色是数独的题面，红色是数独的解。阿里巴巴先制作81张数字1～9的卡片，黑色位置数字朝上，红色位置数字朝下，这样四十大盗并不能看到具体的解。阿里巴巴可以让四十大盗选择，是按行、按列还是按格子检验（Verify），假设四十大盗选择按行检验，阿里巴巴将每行的卡片放到一个袋子里，把卡片打乱，然后打开让四十大盗查看数字是否为1～9，这样按行、按列和按格子的检验可以重复进行多次。最后，阿里巴巴可以向四十大盗证明，如果他不知道数独的答案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗数独答案的情况下，向四十大盗证明了自己知道数独的答案。

这个故事就是一个典型的「交互式zk」，也称作「IZK」，阿里巴巴和四十大盗经过多轮的交互，最后阿里巴巴除了向四十大盗证明自己确实知道数独的答案，没有透露一点关于答案的知识，四十大盗到最后依然对数独的答案一无所知。

《阿里巴巴与四十大盗》里讲的'是阿里巴巴无意中发现了强盗的财宝，强盗得知此事前来报仇，却被阿里巴巴用智慧除掉了的故事。