零知识证明及其协议

信息安全 密码学 验证
2021-08-31 17:17:42

零知识证明中,我们将 Peggy(证明者)和 Victor(验证者)进行类比:

在这个故事中,佩吉发现了用来在洞穴中打开一扇魔法门的秘密词。洞窟呈圆形,入口在一侧,魔门挡在对面。维克多说他会为这个秘密付钱给她,但在他确定她真的知道之前不会。佩吉说她会告诉他这个秘密,但直到她收到钱。他们设计了一个计划,佩吉可以证明她知道这个词而不告诉维克多。

首先,维克多在佩吉进去的时候在洞外等着。他们标记了从入口 A 和 B 开始的左右路径。佩吉随机选择路径 A 或 B。然后,维克多进入洞穴并喊出他想要的路径的名称她用来返回,A 或 B,随机选择。如果她真的知道这个神奇的词,这很容易:如果有必要,她会打开门,然后沿着想要的路径返回。请注意,维克多不知道她走了哪条路。

但是,假设她不认识这个词。然后,如果维克多给出了她进入的相同路径的名称,她将只能从指定的路径返回。由于维克多会随机选择 A 或 B,因此他有 50% 的机会猜对。如果他们重复这个技巧很多次,比如连续20次,她成功预测维克多所有请求的机会将变得微乎其微。因此,如果 Peggy 可靠地出现在出口 Victor 的名字中,他可以断定她很可能知道这个秘密词。

以下验证方法对我来说足够有说服力:

  1. 维克多穿过走廊 A 和 B 并向自己保证没有办法走到另一端。(由于维克多不知道秘密,他确信这是真的)。

  2. 他可以去走廊 A 的入口,让 Peggy 从 B 入口从 A 的尽头走出来。(Peggy 做了,从 A 的尽头出来)

  3. 维克多也会站在另一条路,站在 B 的入口处,让佩吉在穿过 A 后从 B 的尽头过来。

  4. 如果 Peggy 可以同时做 2 和 3,Victor 相信 Peggy 知道这个秘密。

我觉得这种方法是错误的,想知道为什么。那么,为什么经典方法比这个更受欢迎呢?这种方法的缺点是什么?

3个回答

Kerrek SB 链接到的 Wikipedia 上的讨论很接近,但可能不太清楚。

假设佩吉设法让维克多相信她知道这个秘密。维克多能说服你佩吉知道这个秘密吗?在零知识证明中,答案应该是否定的。维克多不仅获得了关于秘密本身的“零”知识,而且也没有关于谁知道秘密的可转移知识。

如链接中所述,请考虑 Victor 为您录制会话的场景。在第一个协议中,只要让 Victor 和 Peggy 同意 Victor 提前给 Peggy 的“随机”挑战,就可以伪造录像带。由于您无法知道 Victor 是否将挑战告诉了 Peggy,因此录像带实际上一文不值,并不能说服您任何事情。

但是,在您修改后的协议中,录像带将令人信服。因此,它泄露的不仅仅是“零”知识。现在拥有转移知识的能力并不总是坏事!在某些应用程序中,您希望在所有方面都使用零知识,但可以转移知识(这些称为非交互式零知识证明)。

然后,维基百科上的评论会处理一个不诚实的验证者(也就是说,如果 Victor 可以证明他在 Peggy 已经处于其中一条路径之后产生了他的挑战,可能是通过在视频上抛硬币)并保持零知识对验证者的可倒带黑盒访问(这是类比在某种程度上分解的地方)。但是,没有必要考虑不诚实的情况来区分原始帖子中的两种协议。

问题是洞穴类比不能推到那么远。有一个关于那个确切问题讨论,看看。“零知识”部分要求证明不能与作弊验证者的模拟区分开来。

打个比方说的很简单,他不知道哪条路有魔法门,密码是什么。哦,他只能走一条路一直走到尽头。所以他还不能通过。

好吧,这是类比的延伸,我听说的那个,有两扇魔法门,Alice 知道两者的通行证有不同的密码,这更接近实际算法,并且使类比更有意义。当然,这给了我一个水晶迷宫谜题的想法,他们基本上必须用这个类比来解决它。