哈希是零知识证明吗？

#1 楼

您的提案中有三​​个问题，我将一一讨论。我希望这可以澄清这个概念。

第一个问题是，零知识证明的目的不仅在于在不披露某些信息的情况下证明某些信息的知识，还在于其功能强大得多：目的是证明您了解某些信息$ ^ 1 $，而不会透露您知道该信息的事实。这里的要点是，您不知道对手将如何处理泄露的有关秘密价值的信息。很有可能即使是一些无害的泄漏也会使您的对手做出意想不到的坏事。考虑您建议的带有散列函数$ H $的身份验证协议：在此，给定秘密值$ v $，则泄漏$ H（v）$。这显然不是“没有信息”，并且您不能保证此$ H（v）$不能用于做不好的事情。因此，我们定义零知识证明的方式旨在预测每种可能的情况，如下所示：我们说该协议为零知识，如果存在一种有效的算法，该算法可以与验证者产生交互，而这与诚实交互是无法区分的，但不知道其秘密价值。此定义之间的直觉是，如果无法在不知道秘密值的情况下将交互记录与可能产生的内容区分开，那么它就无法向验证者传达有关此值的任何有用信息（当然，正式定义一些照顾）。您的协议显然不满足此要求。

第二个问题是我们通常要考虑的功能的通用性。在您的示例中，您实际上假设您只是证明自己知道与对手已经拥有的值相同的值（因为她必须自己散列该值才能进行比较）。但这通常不是一个非常有用的情况。例如，一个更通用的设置如下：某些公共密文$ c $是已知的，并且您想向对手证明您知道其明文，但没有公开实际的明文。在这里，您的散列然后发送的简单方法显然根本不起作用。实际上，零知识证明处理的情况甚至比这种情况还要复杂得多，从而可以证明有关秘密值的各种语句，这些值可以被哈希，提交，加密，签名或任何您喜欢的东西。 />最终，第三个问题是知识的零知识证明必须证明知识。如果给定证明者的代码，则协议可以证明该值的知识，实际上可以有效地提取该值（这是密码术中“知识”的正式定义）。在您的示例中，这显然也是不可能的。实际上，您的协议根本无法证明对秘密值$ v $的了解，因为证明者只需要知道$ H（v）$即可完成它-正如您所指出的那样，并不意味着知道$ v $，因为$ H $是单向的。

让我们看一个实际的例子，使所有这些变得更具体。

拿有限阶素数$ p $ G $$$（我在这里假设对基本代数有所了解）。修复生成器$ g $。现在考虑另一个组元素$ h $。证明者的目的是向验证者证明他知道一个秘密值$ x $，从而$ h = g ^ x $（请注意，由于$ g $是生成器，所以存在这样的$ x $，但是找到给定$ h $可能很难-这是离散的对数问题）。这对于身份验证非常有用：$ h $将成为证明者的“公共身份”，并演示$ x $的知识，以便可以使用$ g ^ x = h $来将他认证为“私有”的所有者。与$ h $相关联的“身份”（其指数以$ g $为基数）。花一秒钟的时间说服自己，没有简单的“基于哈希的”解决方案在这里起作用。

以下是一个实际有效的协议：


证明者选择了一个随机指数$ r $并将$ R = g ^ r $发送给验证者。
验证者选择一个随机指数$ e $（挑战）并将其发送给证明者。
证明者计算并向验证者发送$ d = ex + r $。
验证者检查$ h ^ e \ cdot R = g ^ d $。

花费几秒钟时间检查协议是正确的，也就是说，如果证明者诚实地进行，验证者的检查将成功。

为什么这个零知识$ ^ 2 $？因为一个人可以生成与该协议的诚实笔录完全没有区别的笔录，但是却不了解$ x $：所以随机选择$（e，d）$，然后设置$ R \ get g ^ d / h ^ e $，并输出成绩单$（R，e，d）$。注意，这可以容易地检查以给出在所有满足$ h ^ e \ cdot R = g ^ d $的成绩单上均匀分布的成绩单-即，在所有诚实成绩单上均匀分布的成绩单。因此，在此协议中与证明者进行交互根本不会传达有关$ x $的任何信息（因为在不知道$ x $的情况下可能会生成完全相同的分布之后的记录）。

为什么这证明了$ x $的知识？为了说明这一点，我必须证明给定证明者的代码成功通过该证明，我可以有效地恢复$ x $-因此表明该证明者实际上知道$ x $。我这样做如下：我运行证明者代码，以获得$ R $。然后，我在代码中放置一个断点，对其进行分叉，然后在我选择的两个随机的不同挑战$（e_0，e_1）$上运行两次。代码的第一个副本输出$ d_0 $，代码的第二个副本输出$ d_1 $。由于这是成功证明者的代码，因此我知道支票通过了$ ^ 3 $，因此我有$（R，e_0，e_1，d_0，d_1）$这样：

$ h ^ {e_0} \ cdot R = g ^ {d_0} $

$ h ^ {e_1} \ cdot R = g ^ {d_1} $

一些简单的操作$ g ^ {（d_0-d_1）\ cdot（e_0-e_1）^ {-1}} = h $

因此，我们要寻找的值$ x $只是$ （d_0-d_1）\ cdot（e_0-e_1）^ {-1} $，我们已经成功提取了它。这证明了结论。

（1）实际上，这仅适用于知识的零知识证明的特定情况。总体而言，零知识证明有两种变体，可以用来表明某些陈述是正确的（存在证明），或者您知道某种陈述的证明（知识证明）。我专注于后者，因为它似乎是您所了解的。

（2）实际上，它并不是真正的零知识，形式上，它仅满足一个较弱的定义，即诚实验证者零-

（3）我再次在这里隐藏了一些技术知识，因为通常我们只能假设证明者以一定的概率成功了，但是并不能使证明者成功主要区别。


编辑-从评论中回答问题

来自MechMK1：


也许我对这件事的理解还不够好，但是我被问到“为什么爱丽斯不能简单地进入隧道的另一端而又从隧道的另一端出来？”这个问题引起了我的兴趣。据我所知，这并不能直接得到回答。


首先，请注意，这个洞穴图并不是真正的零知识证明，而是一种给定的场景出于说明目的，传达了有关零知识证明的一些直觉。总是会有某种方式无法通过直观的场景正确地解释所有概念。其他？” （编辑：正如我之后注意到的那样，以下我的解释基本上是基于罗曼对OP问题的评论）。回想一下，为了证明零知识证明不传达任何知识，我们必须在不知道实际秘密见证人的情况下模拟看起来有效的笔录。洞穴实验如何完成？该插图的来源是在实际论文中给出的答案：如何向孩子解释零知识协议，我鼓励您阅读以获取更多有关此问题的讨论。基本上，您可以录制某人的录像带，该录像带被要求从隧道的任意一侧出现；不能穿过门的人刚开始会随机选择一面走到那边。当这个人幸运的时候，只是从右边出来，请保留录制的视频；如果不是，请删除视频，然后重试。最后，您所拥有的是与进行真正的零知识实验的人的实际录音完全没有区别的录音。

现在，您可能会争辩说这有点可疑，也许我们可以制作一个看上去有效的视频，该视频使用视频编辑从一侧进入而另一侧离开，因此也可以“模拟”替代方案。这是我们达到此插图的极限。实际上，启发该插图的原始协议是图同构的零知识协议。它如下：给您两个图形$ G_0，G_1 $（“洞穴入口”），并声称它们是同构的（即“您可以从一个走到另一个”）。该协议的工作原理如下：


证明者知道$ G_0 $顶点的秘密排列，该顶点映射到$ G_1 $的顶点，这是他的见证人。他随机选择了一个$ b $，并随机排列了一个\\ pi $，并发送了$ G = \ pi（G_b）$（即，他“通过随机选择的一侧进入洞穴”）验证者选择了一些$ b'$并将其发送（即，她“要求证明者走出她选择的随机面”）。
证明者必须揭示映射$ G_ {b'} $到$ G $（这是$ \ pi $或由秘密排列组成的$ \ pi $）。即，他使用他的秘密见证人（“门的钥匙”）在验证者选择的一侧“到达”。

现在，此视频录制插图实际上是对如何为证明以上内容为零知识-您可以通过多次重播协议并丢弃$ b'\ neq b $处的运行来创建有效的转录本。同时，“为什么爱丽丝不能简单地进入隧道的一端而又伸出另一端？”在这里很清楚：这相当于揭示从一侧到另一侧的路径-即放弃秘密排列。但是同样，显然不是很清楚，这不是说明性示例中的有效解决方案，这是该示例的局限性（也是我不太喜欢它的原因之一）。


来自NieDzejkob：


“这个定义之间的直觉是，如果无法甚至不知道秘密值就将交互的笔录与可能产生的东西区分开，那么它就无法传达关于此值对验证者有用的任何信息”。证明者与验证者建立TLS隧道，并通过它发送秘密。没有人可以从笔录中学习任何东西，但这显然可以使验证者了解秘密。我遗漏了什么吗？


与我的脚注（2）有关的评论：实际上，笔录可确保没有任何东西不仅泄漏给外部人员，而且泄漏给验证者自己（如果泄漏的话）与与该验证程序互动而产生的笔录无法区分。在我提供的证明中，模拟了笔录，并假设验证者诚实地对挑战$ e $进行了采样，但实际上他可能不会这样做。因此，我给出的证明实际上仅表明该协议对诚实地随机采样$ e $的验证者而言是零知识的。但是，存在将这种协议转换为可以被证明对任意验证者甚至是作弊者为零知识的协议的通用技术。现在，回到您的问题：这样做的话，从验证者本人的角度看，模拟的笔录与诚实的笔录不会有什么区别，因为模拟的笔录将不包括此TLS通道传输秘密值。零知识属性的实际证明必须产生一个模拟的成绩单，验证者本人无法将其与可能由于与自己的互动而产生的成绩单区分开。因此，我以前对以下事实的评论是：为简单起见，我之前已经证明的事实只能保证对诚实地采样挑战$ e $的验证者为零知识，因为这是在模拟笔录中完成的方式。但是正如我所说，有一些方法可以针对任意验证程序进行仿真。