安全多方计算之五：零知识证明（从入门到入土。。）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

零知识证明

1. 简介
2. 零知识证明的例子
3. ElGamal加密的零知识证明
4. 身份的零知识证明
- 4.1 Fiat-Shamir 身份识别协议

1. 简介

零知识证明Zero Knowledge Proof由S.Goldwasser、S.Micali 及 C.Rackoff于1985年在论文《The Knowledge Complexity of Interactive Proof Systems》交互式证明系统中的知识复杂性首次提出是一种用于证明者在不泄露任何其他信息的情况下证明其掌握知识正确性的密码学协议。

该协议的一方称为证明者Prover用 $P$ 表示另一方称为验证者Verifier用 $V$ 表示。零知识证明指 $P$ 试图使 $V$ 相信某个论断是正确的但却不向 $V$ 泄露任何有用的信息即 $P$ 在论证的过程中 $V$ 得不到任何有用的信息。零知识证明除了证明证明者论断的正确性外不泄露任何其他信息或知识。

零知识证明一般包含以下阶段

承诺Commit证明者针对命题做出承诺该承诺等待验证者提出挑战并进行验证。
挑战Challenge验证者选择随机数即上述例子中的行、列或格对提出的承诺进行挑战。
回应挑战Response证明者将收到的随机数结合给出的承诺承诺不可修改返回挑战的回应。
验证Verify验证者验证挑战的回应是否正确如果错误则证明失败。

证明者与验证者重复执行以上步骤直到可以相信的概率达到验证者接受的条件证明成功。

零知识证明具有以下特点

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

零知识证明与比特承诺都要求协议参与者对某种知识或某个声明做出证明或承诺但不泄露该知识或承诺的任何信息。不同的是比特承诺需要在打开阶段揭示承诺但零知识证明在证明过程结束后仍不会泄露掌握的知识。比特承诺一般用于在电子拍卖或电子投票中参与者对自己的投票或选票做出承诺而在协议执行过程中为了抵抗恶意参与者或主动攻击者需要协议参与者通过零知识证明来证明自己所作操作都是按照协议正确执行的。

2. 零知识证明的例子

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

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

$X$ 左手拿着红球右手拿着绿球并在背后不让 $Y$ 看到进行交换或者不交换两只球
$Y$ 能够根据颜色精准判断 $X$ 是否进行了交换
执行上述操作 $N$ 次后即能在 $X$ 是色盲的情况下 $Y$ 仍能够向 $X$ 证明能这两颗球是一红一绿

2.2 数独的零知识证明

数独Sudoku规则如下

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

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

$P$ 和 $V$ 执行以下操作

1承诺

$P$ 将答案的每个数字写在纸片上并按照答案摆放(正面朝下)题目中已有的数字正面朝上这81个纸片的放置为 $P$ 的“承诺”。
在这里插入图片描述
2挑战

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

3挑战回应

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

4验证

$V$ 打开纸袋可验证每个纸袋里的 $9$ 张纸片刚好为 $1 - 9$ 即 $P$ 在承诺阶段做出的承诺满足“每行 $1 - 9$ 都出现且只出现一次”的要求同时在一定程度上说明 $P$ 做出的承诺很可能是一个合法的解因为随意给出的数字不会满足这一要求并且在承诺的时候并不知道 $V$ 会选择行、列、格哪种验证方式。
在这里插入图片描述
由于存在 $1/3$ 的概率 $P$ 事先猜对 $V$ 选择行验证然后给出的承诺仅满足行要求不满足列要求和格要求。或者 $P$ 拥有满足两项要求但是不满足第三项要求的错误答案此时猜对的概率为 $2/3$ 。

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

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

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 提出一种形象的基本零知证明协议的例子该图表示一个迷宫 $C$ 与 $D$ 之间有一道门需知道秘密咒语才能打开。现在证明者 $P$ 希望向验证者 $V$ 证明他拥有这道门的秘密语但是 $P$ 不愿意向 $V$ 泄露该咒语。 $P$ 采用“分割与选择”Cut-and-Choose技术实现这一零知识协议。

在这里插入图片描述

(1)验证者 $V$ 开始停留在位置 $A$
(2)证明者 $P$ 一直走到迷宫的深处随机选择到位置 $C$ 或位置 $D$
(3) $V$ 看不到 $P$ 后走到位置 $B$ 然后命令 $P$ 从某个出口返回 $B$ ;
(4) $P$ 服从 $V$ 的命令要么原路返回至位置 $B$ 要么使用秘密咒语打开门后到达位置 $B$

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

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

在这里插入图片描述

3. ElGamal加密的零知识证明

3.1 ElGamal加密的已知明文证明

对于 ElGamal加密方案的密文 $E(M)=(\alpha, \beta)=\left(g^{r}, y^{r} M\right)$ , 如果一个参与者知道了 $r$ , 则可非常方便地利用零知识证明来证明自己知道密文 $(\alpha, \beta)$ 所对应的明文 M , 这就是已知明文证明。

Schonorr提出参与者能够使用零知识证明的方法俩证明他知道一个 $r$ 使得 $\alpha=g^{r}$ 成立, 方法如下:

步骤1: Alice 选择随机数 $z$ 发送 $a^{\prime}=g^{z}$ 至 Bob。
步骤2: Bob 选择随机数 $c$ 发送至 Alice。
步骤3: Alice 发送 $\bmod q$ 至 Bob。
步骤4: Bob 验证 $g^{k}=a^{\prime} \alpha^{c}$ 。

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

Cramer 提出, Alice 对消息 $M$ 的 ElGamal 加密 $(\alpha, \beta)=\left(g^{r} \bmod p, y^{r} M \bmod p\right)$ 在不泄露 $M$ 的前提下, 可以向其他人证明 $M = 7$ 或 $M = Z$ , 步骤如下:

步骤 1 :

若 $M = 1$ , Alice 选择随机数 $r_{1}, d_{1}, w$ , 发送 $(\alpha, \beta), a_{1}=g^{r_1} \alpha^{d_{1}}, b_{1}= y^{r_{1}}\left(\frac{\beta}{z}\right)^{d_{1}}, a_{2}=g^{w}, b_{2}=y^{w}$ 至 Bob;
若 $M = Z$ , Alice 选择随机数 $r_{2}, d_{2}, w $, 发送$ $(\alpha, \beta), a_{1}= g^{w}, b_{1}=y^{w}, a_{2}=g^{r_{2}} \alpha^{d_{2}}, b_{2}=y^{r_{2}} \beta^{d_{2}}$ $至 Bob。

步骤 2: Bob 发送随机数 $c$ 至 Alice。

步骤 3:

若 $M = 1$ , Alice 发送 $d_{1}, d_{2}=\left(c-d_{1}\right) \bmod p, r_{1}, r_{2}=\left(w-r d_{2}\right) \bmod p$ 至 Bob;
若 $M = Z$ , Alice 发送 $d_{1}=\left(c-d_{2}\right) \bmod p, d_{2}, r_{1=}\left(w-r d_{1}\right) \bmod p, r_{2}$ 至 Bob。

步骤 4: Bob 验证 $c=(d_{1}+d_{2})\bmod p, a_{1}=g^{r_{1}} \alpha^{d_{1}}, b_{1}=y^{r_{1}}\left(\frac{\beta}{z}\right)^{d_{1}}, a_{2}=g^{r_{2}} \alpha^{d_{2}}, b_{2}= y^{r_{2}} \beta^{d_{2}}$

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

Alice 对消息 $m$ 的 ElGamal 加密 $(\alpha, \beta)=\left(g^{r} \bmod p, y^{r} m \bmod p\right)$

$\left(m_{1}, m_{2}, \ldots, m_{N}\right)$ 为明文集合。 $m=m_{t}, t \in[1, N]$ 可以在不泄露 $m$ 的情况下证明 $\in M$ 。

假设 $M$ 对应的其 ElGamal 加密的密文集合为 $\left(\left(\alpha_{1}, \beta_{1}\right),\left(\alpha_{2}, \beta_{2}\right), \ldots,\left(\alpha_{N^{\prime}} \beta_{N}\right)\right)$ 其中 $\left(\alpha_{i^{\prime}} \beta_{i}\right)= \left(g^{k_{i}} \bmod p, y^{k_{i}} m_{i} \bmod p\right)$

步骤 1:

Alice 选择随机数 $d_{1}, d_{2}, \ldots, d_{N}, r_{1}, r_{2}, \ldots, r_{N}$ , 计算
$a_{i}=\left(\frac{\alpha_{i}}{\alpha}\right)^{d_{i}} \cdot g^{r_{i}}, \quad b_{i}=\left(\frac{\beta_{i}}{\beta}\right)^{d_{i}} \cdot y^{r_{i}}, \quad i=1, \ldots, N,i \neq t .$

$a_{t}=g^{w}, b_{t}=y^{w}$ , 其中 $w=\left(k_{t}-r\right) d_{t}+r_{t}$ 并将 $\left(a_{i} b_{i}\right), i=1, \ldots, N$ 发送至 Bob。

步骤 2: Bob 发送随机数 $c$ 至 Alice。

步骤 3: Alice 修改 $d_{t}$ 与 $r_{t}$ , 使得 $c=\sum_{i=1}^{N} d_{i}, w=\left(k_{t}-r\right) d_{t}+r_{t}$

然后将 $d_{1}, d_{2}, \ldots, d_{N}, r_{1}, r_{2}, \ldots, r_{N}$ 发送至 Bob。

步骤 4: Bob 验证 $c=\sum_{i=1}^{N} d_{i}, \quad a_{i}=\left(\frac{\alpha_{i}}{\alpha}\right)^{d_{i}} \cdot g^{r_{i}}, \quad b_{i}=\left(\frac{\beta_{i}}{\beta}\right)^{d_{i}} \cdot y^{r_{i}}, \quad i= 1, \ldots, N$

4. 身份的零知识证明

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

证明者 $P$ 能够向验证者 $V$ 证明他的确是 $P$ ;
在证明者 $P$ 向验证者 $V$ 证明他的身份后验证者 $V$ 不能获得关于 $P$ 的任何有用信息使得 $V$ 不能冒充 $P$ 向第三方证明 $V$ 是 $P$ 。

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

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协议。该协议把“分割与选择”和“挑战与应答”的思想结合起来其目的是证明者 $P$ 向验证者 $V$ 证明他的身份且事后 $V$ 不能冒充 $P$ 。

协议描述

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

证明者 $P$ 的秘密身份由 $k$ 个数 $x_1,...,x_i,...,x_k$ 表示其中 $\le x_i<n,i=1,2,...,k$ $P$ 的公开身份由其他 $k$ 个数 $y_1,...,y_i,...,y_k$ 来表示其中 $y_i$ 也满足 $\le y_i<n,i=1,2,...,k$ 且 $x_i$ 和 $y$ 满足: $y_ix_i^2 \bmod n, i= 1,2,...,k$ 初始状态下验证者 $V$ 知道TA公布的Blum数 $n$ 和证明者P的公开身份 $y_1,...,y_i,...,y_k$ 现在 $P$ 希望向 $V$ 证明他知道他自己的秘密身份。协议执行的步骤如下:

$P$ 随机选择一个整数 $a$ 计算 $\equiv \pm a^2 \bmod n$ 并把其中一个值发送给 $V$ ;
$V$ 从 ${1,2,…,k}$ 中选择一子集 $e=\{e_1,e_2,...,e_j\}$ 然后将 $e$ 交给 $P$ ;
$P$ 计算出 $T_x \equiv \prod_{i=1}^{j} x_{e_i} \bmod n$ 并将 $\equiv aT_x \bmod n$ 交给 $V$ ;
$V$ 计算出 $T_y \equiv \prod_{i=1}^{j} y_{e_i} \bmod n$ 并验证 $\equiv \pm b^2 T_y \bmod n$ 是否成立;