一文了解零知识证明基础知识

• 承诺（Commit）：证明者针对命题做出承诺，该承诺等待验证者提出挑战并进行验证。
• 挑战（Challenge）：验证者选择随机数对提出的承诺进行挑战。
• 回应挑战（Response）：证明者将收到的随机数结合给出的承诺（承诺不可修改），返回挑战的回应。
• 验证（Verify）：验证者验证挑战的回应是否正确，如果错误，则证明失败。
• 证明者与验证者重复执行以上步骤，直到可以相信的概率达到验证者接受的条件，证明成功。

• 完备性（Completeness）：如果证明者和验证者都是诚实的，并遵守证明过程的每一步进行正确的计算，则该证明一定会成功，验证者也一定能够接受证明者； 
• 合理性（Soundness）：没有人能够假冒证明者，从而使这个证明成功；
• 零知识性（Zero-Knowledge）：证明过程执行完后，验证者只会得悉"证明者拥有这项知识"，而没有获得关于这项知识本身的任何信息。 

零知识证明的例子

2.1 向红绿色盲证明红球、绿球 

有两颗形状、大小完全一样的球：一颗红球、一颗绿球， 是红绿色盲， 能够向 证明这两颗球是一红一绿吗？

•   左手拿着红球，右手拿着绿球，并在背后不让看到，进行交换（或者不交换）两只球

• 能够根据颜色精准判断是否进行了交换 

• 执行上述操作次后，即能在是色盲的情况下，仍能够向证明能这两颗球是一红一绿

  
  

2.2 数独的零知识证明 

数独（Sudoku）规则如下：

9×9方格，其中已经填入部分数字，要求玩家在空白方格中填入数字1 − 9 ，使得完成后的每行、每列及9个3 × 3方格都包含数字1 − 9且每个数字只出现一次

假设 给出一道数独题目，由 来完成，但 过了很久都未能解出，他怀疑该数独题目没有解，要求 证明该题目有解。因此 希望在不告诉 答案相关的任何信息的情况下证明这道题有解且自己知道这个解。

和 执行以下操作：

(1) 承诺

  将答案的每个数字写在纸片上，并按照答案摆放(正面朝下)，题目中已有的数字正面朝上，这81个纸片的放置为 的“承诺”。

(2) 挑战

  不能直接将纸片翻转查看数字，但是 可以在行、列、格中任意指定一种验证方式。如图所示， 选择按照行的方式进行挑战。

(3) 挑战回应

  按照 选择行验证方式将桌面上每行的9张卡片装入一个袋子里，并且将纸片进行混淆后，把袋子交给 ，作为挑战的回应。

(4) 验证 

  打开纸袋可验证每个纸袋里的9张纸片刚好为1 − 9，即 在承诺阶段做出的承诺满足“每行1 − 9都出现且只出现一次”的要求，同时在一定程度上说明 做出的承诺很可能是一个合法的解（因为随意给出的数字不会满足这一要求，并且在承诺的时候并不知道 会选择行、列、格哪种验证方式）。

由于存在1/3的概率 事先猜对 选择行验证，然后给出的承诺仅满足行要求，不满足列要求和格要求。或者 拥有满足两项要求，但是不满足第三项要求的错误答案，此时猜对的概率为2/3。

但 为了向 证明自己知道该数独的解，会和 重复该方案的承诺、挑战、回应挑战和验证，允许 在挑战阶段任意选择验证方式，如果出现任何一次验证错误则表示证明失败。

假设进行的 次过程都验证成功，那么 在不知道数独答案的条件下单次验证成功的概率最大为2/3（考虑 满足两项要求，但是不满足第三项要求的错误答案），所有验证都成功的概率为 随着 的增大，这一概率趋近于0，而 拥有正确答案的概率趋近于1，表明 可以以大概率相信 拥有正确答案。

2.3 三染色问题的零知识证明 

地图三染色问题：如何用三种颜色染色一个地图，保证任意两个相邻的地区都是不同的颜色。

该问题可转变成连通图的顶点三染色问题，即不同城市（节点）之间修建了一些道路（边），是否存在一种染色方式，使得每个城市都用特定的三种颜色之一表示，并且任意有道路相连的两个城市都不是相同颜色。

如图所示，证明者Alice拥有一个特地地图三染色的方案，希望在不泄漏任何信息的条件下向Bob证明自己拥有该方案。

(1) 承诺

Alice将染色方案进行置换（蓝色->绿色，绿色->橙色，橙色->蓝色），然后将每个节点装入一个信封里，放在桌子上出示给Bob。

(2) 挑战

Bob可以选择任意一条连边，要求Alice打开相邻两个节点的信封进行验证。

(3) 挑战回应

Alice打开Bob指定的两个节点，作为对挑战的回应。

(4) 验证

Bob验证结果：两节点颜色不同

重复以上过程，当重复交互很多次后，Bob得到了大量的信息，但没有得到关于染色方案的任何知识，却能够相信Alice拥有该方案。

2.4 Quisquater-Guillou 零知识协议

1990年，LouisC.Guillou 和 Jean-Jacques Quisquater 提出一种形象的基本零知证明协议的例子，该图表示一个迷宫， 与 之间有一道门，需知道秘密咒语才能打开。现在，证明者 希望向验证者 证明他拥有这道门的秘密语，但是 不愿意向 泄露该咒语。 采用“分割与选择”（Cut-and-Choose）技术实现这一零知识协议。

(1) 验证者 开始停留在位置 A

(2) 证明者 一直走到迷宫的深处，随机选择到位置 C 或位置 D

(3) 看不到 后，走到位置 ，然后命令 从某个出口返回 ;

(4) 服从 的命令，要么原路返回至位置 ，要么使用秘密咒语打开门后到达位置  

上述协议中，若 不知道秘密咒语，就只能原路返回，而 第一次猜对 要求他一条路径的概率为0.5，第一轮协议 能够欺骗 的概率为0.5。

  和 重复上述步骤 次， 成功欺骗 的概率为 。假定 ，则 成功欺骗 的概率为6，如果 能够20次按 的要求返回， 即证明 确实知道秘密咒语。同时， 无法从上证明过程中获取任何关于 的秘密咒语的信息。

3.1 ElGamal加密的已知明文证明

对于 ElGamal加密方案的密文, 如果一个参与者知道了, 则可以非常方便的利用零知识证明来证明自己知道密文所对应的明文,这就是已知明文证明。 

Schonorr提出参与者能够使用零知识证明的方法来证明他知道一个 使得 成立，方法如下： 

步骤1:Alice选择随机数 发送 至Bob。 

步骤2:Bob 选择随机数 发送至 Alice。 

步骤3:Alice 发送 至 Bob。 

步骤4:Bob 验证 。

3.2 ElGamal加密的二选一零知识证明

Cramer 提出, Alice 对消息的 ElGamal 加密

在不泄露的前提下，可以向其他人证明或,步骤如下： 

步骤1：

• 若 ,Alice选择随机数，发送 

至Bob； 

• 若, Alice选择随机数, 发送 

至Bob。 

步骤2：Bob发送随机数至Alice。 

步骤3：

• 若 , Alice发送

至Bob；

• 若 , Alice发送

至Bob。 

步骤4：Bob验证

3.3 ElGamal加密的1-out-of-N零知识证明

Alice 对消息的 ElGamal 加密

令为明文集合。,可以在不泄露 的情况下，证明。

假设 对应的其ElGamal加密的密文集合为

其中

步骤1： 

Alice选择随机数,计算

，其中，并将发送至Bob。 

步骤2： Bob发送随机数至Alice。

步骤3：Alice修改与，使得

然后将 发送至Bob。

步骤4：Bob验证

一个安全的身份识别协议至少应满足以下两个条件: 

• 证明者能够向验证者证明他的确是; 

• 在证明者向验证者证明他的身份后，验证者不能获得关于的任何有用信息，使得不能冒充向第三方证明是。

也就是说，既能向证明他的身份，又没有向泄露的识别信息，即安全的身份识别协议应满足零知识性和认证性。

4.1 Fiat-Shamir 身份识别协议

1986 年，A. Fiat与A. Shamir 提出了一种基于二次剩余根的身份识别协议，即Fiat-Shamir 身份识别协议。 

1988 年，U.Feige、A.Fiat和 A.Shamir 把 Fiat-Shamir 身份识别协议改进为零知识证明的身份识别协议，即Feige-Fiat-Shamir身份识别协议，简称 F.F.S协议。该协议把“分割与选择”和“挑战与应答”的思想结合起来，其目的是证明者向验证者证明他的身份，且事后不能冒充。

协议描述：

假定存在一个可信任的中心TA，该中心的唯一任务是选择形式为的两个大素数，使得是难分解的，然后向其他人公布(为Blum 数)。TA任务完成后可被关闭或取消，因为它不再有其他的任务，但该中心不能泄露的信息。 

证明者的秘密身份由个数表示，其中 

P的公开身份由其他个数来表示，其中也满足 

且和满足： 

初始状态下验证者知道TA公布的Blum数和证明者的公开身份，现在希望向证明他知道他自己的秘密身份。协议执行的步骤如下：

• 随机选择一个整数， 计算 并把其中一个值发送给;

• 从 中选择一子集, 然后将交给;

• 计算出， 并将 交给;

• 计算出， 并验证是否成立；

若验证通过，则重复执行上述步骤；否则拒绝。

本文作者：无忧

CSDN链接：

https://blog.csdn.net/apr15/article/details/128857984

往期推荐