如何向我的7岁堂兄解释零知识证明？ [重复]

#1 楼

在我的解释中，我将使用Bertie Bott的《 Harry Potter的Every Flavor Beans》。如果您的堂兄还没有读过《哈利波特》，那么您可以参考《果冻豆》。你的堂兄声称他只看豆子就能分辨它们。您不相信他，但他不想告诉您哪一个是菠菜。

相反，您都将菠菜藏在了背后并随机选择其中之一并显示给您的表弟。然后，将其放回原处，并以一种使您知道是否选择了相同bean的方式再次随机选择（例如，将bean交换x次）。然后，您再次将其显示给您的表弟，后者将不得不告诉您它是否与您之前显示的那个豆相同。重复此过程，直到您确定他确实能够区分豆子（或他不能）。哪种豆子最美味。

最后，在这种情况下，有两种侧通道攻击：豆，所以不要太明显。
你可以给他一种豆，当他拒绝的时候，可能是菠菜。

#2 楼

几年前，我得到一个谜语，我认为它很好地解释了这个概念-七岁的孩子很容易理解。

我们假设，一百个打开的锁，编号从1到100。谜题如下：我按住一把打开其中一个锁的钥匙。但是，钥匙也有编号：如果我向您展示钥匙，并告诉我可以用它打开锁，您将确切知道我拥有哪把钥匙。

如何说服您拿着我打开一把锁的钥匙，但没有向您透露它是哪把钥匙？还有，什么都没有透露，除了我可以打开至少一个锁？

解决方案如下：


您创建两个交织在一起的“ 50个锁圈”。即，将锁1附加到锁2，还将其附加到锁3 ...，将其附加到锁49，将其附加到锁50，将其附加到锁1。这使您绕入50个锁一条链。您对锁51到100所做的操作完全相同，只是该圆圈穿过了锁的第一圈。为了说服您，我必须将两个锁圈分开，但又分开。此锁将圆圈分开。因此，这表明我可以打开至少一个锁，但不透露有关哪个锁的任何信息。

#3 楼

几年前，此问题已在信息安全StackExchange上提出，我将带给您Rahil Arora的答案（已接受），因为我认为它在解释方面做得很好。


在我的研究生
学校的一次客座演讲中，我听到了这个例子。我认为这很简单，因为我本人已经多次使用它来向对加密/数学知识几乎为零的人解释ZKP。想要说服您我有超能力
在几秒钟内计算出树上的确切叶子数。我
想要说服您而又不实际透露确切数字，并且
而不要透露我的超能力。我可以设计一个简单的协议：

我闭上眼睛，给你一个选择，从那棵树上摘下一片叶子。由于这只是一个选择，因此您可以将其拉出，也可以
。除了用我的超能力再次快速计算出叶子数之外，我别无其他方法来知道您是否做到了。现在，当我看着树时，你会问我是不是真的摘下了树？


如果我给你一个错误的答案，你就是我会立即知道我的
超级大国是假的，我的知识也是如此。但是，如果我的回答是正确的，您可能会认为我很幸运。在这种情况下，我们可以
重复上述步骤。我们可以继续重复这些步骤，直到您对我实际上拥有
超级大国并知道确切数字的事实感到满意为止。

#4 楼

考虑一本“ Wall's Wally”（或“ Wald's Waldow在哪里？”）书。 （请参见此处的示例，单击“向内看”）。

读者的目标是找到一个特定角色Wally。

假设Alice知道Wally在特定位置中的位置图片，她想在不透露Wally位置的情况下向Bob证明。她在硬纸板中间切了一个小孔，和沃利一样大。当鲍勃不看时，她把书放到纸板后面，这样就可以从洞中看到沃利。知道Wally在页面中的位置。

Alice可以通过携带另一个Wally插图并将其放在纸板后面进行作弊。为了防止这种情况，鲍勃可以在实验前搜寻她，以确保她不会随身携带微小的沃利图像。

资料来源：www.wisdom.weizmann.ac.il/~naor/PUZZLES/ waldo.html

#5 楼

我发现阿里巴巴（Ali Baba）的Cave案例是解释零知识证明的好例子：https://youtu.be/0Sy6nb72gCk?t=3m46s

维基百科上有很好的摘要：https：// en。 wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_Baba_cave


[...]在这个故事中，佩吉（Peggy）发现了用来打开魔法门的秘密单词洞穴。洞穴的形状像一个环，入口在一侧，魔术门挡住了另一侧。维克多想知道佩吉是否知道这个秘密词。但是佩吉（Peggy）是一个非常私人的人，不想向维克多（Victor）透露自己的知识（秘密词）或向整个世界透露自己的知识事实。
它们标记了从首先，当佩吉（Peggy）进入时，维克多（Victor）在山洞外面等候。佩吉（Peggy）走A或B路线；维克多（Victor）不允许她走哪条路。然后，维克多（Victor）进入山洞，大喊他想让她用来返回的路径名称（随机选择的A或B）。只要她确实知道魔术单词，这很容易：她会在必要时打开门，然后沿着所需的路径返回。然后，如果维克多（Victor）给出与她输入的路径相同的路径的名称，则她只能按命名路径返回。由于Victor会随机选择A或B，因此她有50％的机会正确猜测。如果他们要重复多次（连续说20次），成功地预测Victor的所有请求的机会就会越来越小（大约百万分之一）。
因此，如果Peggy反复出现在退出Victor的名字，他可以得出结论，佩吉确实很可能（从天文学角度来看）确实知道这个秘密词。 [...]



-图片由Dake〜commonswiki

#6 楼

我知道的零知识证明的最简单示例是图同构。根据Babai的拟多项式结果，它有点有趣，但是出于教育目的，我们将忽略它。零知识证明仍然存在。我不确定对于7岁的孩子来说这是否足够简单，但是可以这样：

我们有两个图，其中节点的名称不同，我们想证明它们本质上是相同的图。意味着在图的节点之间存在一对一的映射，该映射保留了边。或者，我们可以重命名一个图的节点以接收第二个图。我们想证明这种映射的存在而不揭露它。

这可以通过选择其中一张图并将节点重命名为随机名称（以随机顺序提供边）来完成。我们将此新图发送给验证者，验证者要求揭示该图与他选择的两个原始图之一之间的映射。证明者提供了这样的映射。重复直到达到所需的置信度。

对于一个七岁的孩子来说，它可能还不够简单，但由于它不使用任何加密原语，因此比大多数替代方法都更简单。

#7 楼

免责声明这并不是一个罐头答案，您可以重新加热并直接给表弟服务；这不是教学的方式，尤其是在那个年龄。您应该能够使其适应他或她的性格和能力，并回答他或她可能遇到的任何问题（尝试进行预测是徒劳的）。这尤其意味着您需要自己理解该主题；您不能希望仅通过重复您所讲的内容来解释自己不了解的内容。他们从普通的证明。该属性是可模拟的，这意味着即使不能通过规定的证明协议证明陈述的真实性的人，也可以通过其他方式产生与实际证明没有区别的东西。戈尔德里希（Goldreich）在他的开创性著作中给出了一个可以解释这一点的论述，其内容如下（出于记忆而改写，因为我现在手边没有这本书）。


Peggy想向Victor证明迷宫的两个末端之间存在一条路径（更准确地说，迷宫的每个点都可以从任一末端访问），但是没有向他透露该路径（因此这排除了例如指导他完成任务）。他们进行如下。佩吉神奇地传送到迷宫内部的一个随机位置，维克多（从迷宫外部）指示她通过他随机选择的一个肢体离开它。如果Peggy确实通过Victor指定的末端退出迷宫，则Victor确信存在路径。


此协议具有三个所需的属性：



完整性。如果确实存在一条路径，那么无论Peggy在迷宫中被传送到什么地方，无论Victor选择哪个出口，Peggy都将始终能够按照指示退出。如果不存在路径，则佩吉传送的位置将恰好连接到一个出口。因此，如果概率为$ 1/2 $（如果Victor选择另一个出口），Peggy将无法按照指示退出。

可移植性。如果有通过迷宫的路径，那么Victor（或其他任何人）可以通过以下步骤执行“看上去”像Peggy在协议期间所做的事情，即使不知道该路径也是如此。 Victor首先随机选择一个出口，通过该出口进入迷宫，然后在内部随机走动，使用线程标记其路径。如果他走的路足够长，他将到达一个随机的位置，然后可以按照自己的思路离开，从而“模拟”了一个证据。在协议期间，即使她不知道路径，也可以完成关于路径（或其他任何东西）的信息，因为她所做的（从随机位置到随机出口）。

#8 楼

佩吉（Peggy）可以像其他人一样系好漂亮的蝴蝶结

佩吉（Peggy）知道如何系好漂亮的蝴蝶结。如果您将任何一根细绳送给佩吉，她都会为您系蝴蝶结，并将其还给您。

每个人都知道Peggy可以绑漂亮的蝴蝶结，而且他们也知道每次弓箭看起来都一样。不管您给Peggy戴什么样的绳子，弓的外观都一样。只有佩吉（Peggy）知道如何以那种看起来那样的方式系弓。而且弓是如此的复杂，以至于您不能试图解开弓并弄清楚弓是怎么做的，因为那会花费很长时间。 ，我是佩吉！”。维克多说：“哦，是吗？好吧，如果您是佩吉（Peggy），那么您可以为我系一条特别漂亮的蝴蝶结，对吗？”。
“哦，可以，”佩吉说，“给我一根绳子，我会向你证明的！”

维克多给佩吉（Peggy）一根绳子。佩吉接过它，转过身，使维克多看不到她在做什么，然后系好弓。然后，她向Victor鞠躬。

维克多看着弓。首先，他检查该字符串是否是他送给Peggy的正确字符串（否则，这可能是冒名顶替者，他偷了Peggy给其他人的漂亮弓）。

维克多说：“你能再做一次吗？”。佩吉说：“当然！给我一个新的弦！”。

Victor和Peggy做了几次，每次Victor都要检查一下弓的外观是否完全一样。然后Victor很高兴，并且知道Peggy确实可以用任何绳子系这种弓。

因此...

Peggy知道一个秘密：如何在弓上系弓一种特殊的方式。 Victor可以看着弓箭，发现它是被Peggy绑住的，但是Victor自己也不知道该怎么做

这有什么用？

如果每个人（不仅是Peggy）都知道如何系上漂亮的蝴蝶结，但每个人都以不同的方式系上它们，那么我们就可以编制目录。目录中说爱丽丝系这种弓，鲍勃系这种弓...卡罗尔，戴夫，艾琳...我们知道的每个人都在这个目录中，以及他们系的弓。

所以过了一段时间，佩吉回到维克多，说：“嗨，我是佩吉！”

维克多看着佩吉，说道：“你知道吗……我的脸真的很糟糕。但是我有弓的目录！这是一根绳子。你能帮我系弓我？”。

“当然！”佩吉（Peggy）说，拿起绳子，转过身，系上特殊的蝴蝶结，只有她知道怎么打结。她把弓交给了维克多。 >