零知识认证是怎么回事

cisamaqing

假定 Peggy 声称知道图 G 和 H 之间的同构。实际上，这意味着她自己（为大图）构造了这两幅图，或者至少是构造图的人提供了同构性。如果以前公布过：Peggy 是知道 G 和 H 之间的同构的人，那么知道这一同构可能是她证明自己身份的方式。显然，仅仅通过直接显示同构会允许任何观察者冒充 Peggy，所以这样不好。

下面是 Peggy 所做的用以证明她知道同构的步骤：

Peggy 随机改变 G 的次序以产生另外一幅图 I。由于 Peggy 知道 G 和 H 之间的同构，因此她很容易同时找到 H 和 I 之间的同构。
Peggy 将 I 给 Victor。
Victor 可能要求 Peggy 证明：要么（a）I 和 G 同构，要么（b）I 和 H 同构。但是，Victor 可能不要求两者都证明（如果他同时获得了对两者的证明，那么他可以自己证明 G 和 H 之间的同构了）。
Peggy 提供 Victor 所请求的证明。

零知识证明，第五部分 第 11 页（共12 页）




到目前为止一切顺利。这表明了什么呢？如果一个假冒 Peggy 的人不知道 G 和 H 之间的同构，冒充者能做的最多是试图假冒与 G 同构的 I（她同 Victor 一样知道 G 和 H），并希望 Victor 不要求 H 和 I 之间的同构。或者，假冒 Peggy 的人可以试图假冒从 H 构造的 I，并且希望相反的情况。不论如何，冒充者有 50% 的可能性被上面的协议抓住。

然而 Victor 可能发现 1/2 的可信度并不足以让 Peggy 证明她知道同构。幸运的是，Victor 能够简单地要求 Peggy 现在生成 I' 并再次经受该协议的考验。如果她现在通过了，那么 Victor 对 Peggy 的可信度可达到 3/4。如果这还不够好，那么她可以使用 I'' 第三次经受协议的考验，并获得 7/8 的可信度；或者 15/16 的可信度，31/32 的可信度，等等。通过重复该协议，Peggy 可以证明：她知道 Victor 所要求的任意可信度的同构（但总是比 100% 要小一些）。不管对该协议重复了多少次，Victor 都不会获得有助于构造他自己的 G/H 同构的知识，因此“零知识”泄露给了 Victor。