2024-04-05  2024-04-05    10097 字  21 分钟
- 密码学

零知识证明

零知识证明

在深入介绍形式化定义和具体协议之前，我们先通过一些直观的例子来感受零知识证明的核心思想。这些例子不会涉及复杂的数学推导，而是帮助我们理解零知识证明在“证明一件事为真，但不泄露额外信息”这个目标上的意义。通过这些例子，你会先对“零知识”产生感性认识，再进一步理解它在密码学中的形式化定义和应用。下面是零知识证明的非严谨定义：

定义（零知识证明）：
零知识证明是一个交互式协议，其中证明者（Prover）能够在不向验证者（Verifier）泄露任何有用信息的前提下，使验证者确信某个陈述为真。 一个零知识证明协议应满足以下三个基本性质：

  1. 完备性(Completeness)：拥有满足陈述知识的证明者能以足够高的概率使验证者接受该陈述。
  2. 可靠性(Soundness)：如果证明者并不拥有满足陈述的知识，则其通过验证的概率可以忽略。
  3. 零知识性(Zero-Knowledge)：在整个零知识证明过程中，验证者除了得知陈述为真这一事实外，无法从协议中获得任何关于知识本身的额外信息。

一、举例说明

1.1 交互式零知识证明举例

交互式的零知识证明指的是：证明者（prover）与验证者（verifier）通过若干轮的交互，使得验证者相信证明者确实拥有某个秘密，且证明者不能得到这个秘密的任何信息。

经典零知识证明例子之—色盲游戏

Alice是色盲，Bob不是色盲，在Bob手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于Alice是色盲，所以Alice无法分辨这两个球是否是一样的，Bob需要向Alice证明这两个球是不一样的。在这里，Alice被称为验证者，他需要验证Bob的陈述正确与否，Bob被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），Bob需要在Alice不能获得两个球的颜色的情况下，向Alice证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。

Alice当Bob的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样Bob就看不到Alice手上的球了，Alice在背后随机交换左右手上的球，交换完成后Alice将手伸出，并询问Bob两个球是否交换过位置，如果Bob能看到球上的颜色，那么每次Alice换过球的位置后，Bob都能正确回答出Alice的问题。

第一次，Alice偷偷交换了手中球的位置，然后Alice问Bob是否交换了球的位置，如果Bob回答Yes，那么Alice有50%的概率相信Bob是可以区分这两个球的颜色，因为Bob有1/2的概率蒙对，所以Alice可以在进行一次测试。如果Bob回答No，那么Alice可以肯定Bob不能区分两个球的颜色。第二次，Alice没有交换手中球的位置，然后Alice问Bob是否交换了球的位置。如果Bob回答No，那么Alice有75%的概率相信Bob是可以区分两个球的颜色。

第一次迭代后，Alice可以说Bob陈述的断言为真的概率为50％。如果Bob第二次回答正确，那么Alice可以说Bob陈述为真的概率达75％。在第三次迭代后，它将是87.5％。如果连续n次Bob都通过了检查，则Alice有 $1-(1/2)^n$ 的概率可以认为 Bob 说的是真的，这两个球的确是有红蓝两种颜色。

零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover）提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈诉骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。

非交互式零知识证明：

交互式零知识证明协议依赖于验证者的随机尝试，需要证明者和验证者进行多次交互才能完成。非交互式零知识证明（Non-Interactive Zero-Knowledge, NIZK）将交互次数减少到一次，可实现离线证明和公开验证。在区块链等零知识证明应用场景中，非交互的性质是必须的，因为在区块链系统中，不能假设双方一直在线进行交互，在区块链网络上，证明者只要向全网广播一条证明交易，网络上的矿工在将这条交易打包到区块中的时候就帮验证者完成了零知识证明的校验。

数独游戏：

数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。【下图给出了一个数独游戏的题目，将空白部分填满即可赢得游戏】

Alice为了向Bob证明他已经解决了一个数独难题，创建一个防篡改的机器M。Alice将生成好的数独答案放入到机器M中，机器M可以向Bob发送证明。Alice的机器遵循以下公开可验证的协议：

首先，Alice在机器中放入尚未被解决的原始数独题目，数独中的谜题卡片三张正面朝上，例如，单元格C3具有3张正面朝上的9号卡片。【即，在3行9列的位置正面朝上放三张数字9的卡片】 则上述题目在机器M中的样子如下图：

机器中每个位置都放了三张卡片，这是因为最后验证的时候，每个位置需要验证“行，列，九宫格”，故需要三张卡片。 接下来，Alice上机器将他的答案正面朝下放置在相应的单元格上，同样也是每个单元格放三张。得到如下结果：

最后Bob向机器获取证明，机器返回给Bob27个袋子：

  1. 机器将数独中每一行9张卡片取出，并分别混淆后放入一个袋子中，一共有9行，所以9个袋子
  2. 机器将数独中每一列9张卡片取出，并分别混淆后放入一个袋子中，一共有9列，所以9个袋子
  3. 机器将数独中每个粗线宫（3*3）内卡片取出，并分别混淆后放入一个袋子中，一共有9个，所以9个袋子
  4. Bob分别对这27个袋子进行检查，如果每个袋子中的卡片都包含数字1到9，而且没有任何数字丢失或重复，那么Bob可以确认Alice的确解开了数独，并且Bob并没有从机器返回的证明中获取任何关于数独解的知识，因为机器返回给Bob袋子中的数据是被随机打乱的。

参考文献

二、Sigma协议

前面我们用一些通俗易懂的例子介绍了零知识证明的基本直观概念，说明它是在“证明某件事为真，但不泄露额外信息”。不过，这些例子与密码学中严格意义上的零知识证明仍然有一些区别。 在密码学应用中，我们通常需要证明的是自己知道某个困难问题的解，或者某个数学关系确实成立。例如，对于一个元素 $R = g^r$，我可能想要证明自己确实知道它的离散对数 $r$；或者证明一个元素 $C$ 是某条消息的合法 Pedersen 承诺。 为了实现这样的证明，密码学中发展出一类非常重要的零知识证明协议 —— 由 Sigma 协议转化而来的非交互式零知识证明（NIZK）。接下来我们将通过具体的例子来介绍这种在实际密码学中广泛使用的证明方式。

2.1 预备知识

为了更好的描述和理解 Sigma协议，首先给出一点点预备知识。

定义1：有效关系

设 $X, Y$ 是两个有效可判定的集合（即其元素可以用多项式时间编码与判别）。一个有效关系是一个二元关系 $R ⊆ X × Y$ 。其中 $Y$ 中的元素被称作statements【声明】，$X$ 中的元素称为 witness（证据）。若 $(x, y) \in R$，我们称 $x$ 是 $y$ 的一个合法 witness，或者说 $x$ 证明了声明 $y$。我们要求给定 $(x, y)$，存在一个多项式时间算法可以判定 $(x, y) \in R$ 是否成立。

2.2 Sigma协议的定义

设 $R \subseteq X \times Y$ 是一个有效关系，则一对交互算法 $(P, V)$ 构成的协议称为在 $R$ 上的 Sigma 协议，如果这个协议满足以下条件：

  1. 协议有两个参与方组成：证明者 $P$ (Prover) 和验证者 $V$ (Verifier)。证明者 $P$ 输入一个合法的 witness-statement 对 $(x, y)$，其中 $(x, y) \in R$。验证者 $V$ 则输入为一个声明 $y \in Y$。

  2. 交互过程由三轮交互组成：

    1. 承诺：证明者 $P$ 计算一组随机数的承诺 $t$，并将其发送给 $V$。
    2. 挑战：在收到 $t$ 后，$V$ 从一个有限的挑战空间 $\mathcal{C}$ 中随机选取挑战 $c$，并将其发送给 $P$。
    3. 响应：在收到 $c$ 后，$P$ 计算挑战 $c$ 对应的响应 $z$ 并发送给 $V$。
    4. 验证：$V$ 根据输入声明 $y$ 和对话 $(t, c, z)$，执行验证算法，输出accept 或 reject。

    注：下图给出了典型的 Sigma 协议交互流程：

  3. 上述交互式协议应当满足以下三个性质：

    1. 完备性： 完备性是说，如果证明者持有声明 $y$ 对应的证据 $x$ 、并且正确执行了上面的协议，验证者总是输出 accept 【按协议生成的证明总能被验证】。 也就是说：对于任意的有效关系实例 $(x,y)∈R$，执行上述协议后，验证者都接受证明者的证明。 如果协议不满足完备性，就无法达成构造这个协议最初的目的–向别人证明自己拥有秘密。
    2. 可靠性：可靠性是说，没有见证的敌手无法生成被验证者接受的证明【敌手无法伪造证明】。通俗的讲，不使用见证生成的证明无法通过验证者的验证。[逆否命题是，能通过验证者验证的证明是由某个见证生成的，这个逆否命题在证明可靠性时比较好用，这不做介绍]。
      知识可靠性是一个比可靠性更强的安全属性。简而言之，可靠性保证没有见证的人无法生成假证明以通过验证，而知识可靠性确保能生成真证明的人一定知道见证，并且这个见证可以被恢复出来。在sigma协议中，一般通过证明存在提取器来证明协议满足知识可靠性。
    3. 零知识性： 零知识性是说，上述交互式协议执行完毕之后，整个协议不会暴露有关于证据 $x$ 的任何信息【证明不暴露证据的信息】。通常可以通过证明存在一个模拟器：能在不知道见证的情况下生成与真实证明不可区分的模拟证明，从而证明零知识性。
      可以这么做是因为模拟生成的签名与真实签名在分布上不可区分，验证者无法判断一个证明是由模拟器生成还是由真实算法生成，因此无法从签名中提取任何关于证据 $x$ 的信息。若验证者能够从证明中获得证据 $x$，那么同样可以从模拟器生成的签名中获得 $x$，但模拟器本身并不掌握 $x$，模拟出的证明也和 $x$ 无关，因此证明不可能泄露证据 $x$。
      正式的，设挑战空间为 C 。如果存在一个高效的概率性算法、我们称其为模拟器并表示为 $Sim(Y,C)$ ，其输入为 $(y,c) \in Y\times C$ 且满足以下两个条件，则称证明满足零知识性：
      1. 对于所有的输入 $(y,c) \in Y\times C$，模拟器 $Sim(Y,C)$ 能够输出一对 $(t,z)$ 使得 $(t,c,z)$ 对于声明 $Y$ 来说是一个被 接受的交互证明。
      2. 对于全体 $(x,y) \in R$ 和随机选择的 $c’\stackrel{R}{\longleftarrow}C$，用模拟器生成 $(t’,z’)\stackrel{}{\longleftarrow}Sim(y,c)$、使得模拟器产生的 $(t’,c’,z’)$的分布与 正常运行Sigma协议得到的 $(t,c,z)$ 的分布相同。

    零知识性的一些说明：

    • 模拟器需要 c 作为额外输出，并且就算声明 y 的证据不存在也可以输出一个被接受的证明。
    • 上述模拟器$Sim(Y,C)$不具备秘密值 x ，但拥有一个能力 决定或者预知验证者的挑战值 c，这是他能模拟的关键，在随机预言机模型下的安全性证明中，这个性质具有重要的作用。
    • 由于模拟器产生的 $(t’,c’,z’)$ 与正常运行Sigma协议产生的 $(t,c,z)$ 在计算上不可区分,所有敌手不可能从 $(t,c,z)$ 得知到任何关于秘密 x 的信息. 这是因为, 如果敌手能从 $(t,c,z)$中得到秘密 x 的信息 , 那么由于 $(t,c,z)$ 和 $(t’,c’,z’)$ 不可区分,则这个敌手也能从 $(t’,c’,z’)$ 中得知秘密 x 的信息. 这是不可能的 , 因为 $(t’,c’,z’)$ 中根本不含由秘密 x .

定义2：知识可靠性

设$(P,V)$是关于关系$R ⊆ X × Y$ 的一个Sigma协议。如果存在一个我们称为提取器高效的确定性的算法 $Ext$ 使得： 给定一个声明 $y$，以及两个关于 $y$ 被接受的sigma协议交互信息 $(t,c,z)$ 和 $(t,c’,z’)$，满足 $c \ne c’$，如果 $Ext$ 能够输出 $x \in X$使得 $(x,y) \in R$，那么我们称 Sigma 协议满足知识可靠性。即存在一个提取器 $Ext$ 使得 $Ext((t,c,z),(t,c’,z’))=x$；

事实上，上述提取器主要是在同一个承诺下给出两个不同的挑战及响应，然后提取出证据 $x$。【可以使用分叉引理去选择两个不同的挑战 c，这里不去细讲具体的内容】

补充说明

其实 HVZK 和 Soundness 最初并不和模拟器与提取器相关，HVZK就是要求Sigma协议中，诚实验证者不能获得秘密的任何知识，Soundness则要求必须拥有秘密的人才能生成符合验证条件的协议内容。 为了能够在理论上证明 Sigma 协议的安全性，引入了模拟器和提取器，使用模拟器充当安全证明中挑战者的模拟方案，挑战者结合分叉引理和提取器求出秘密 x 解决困难问题，从而构造可证明安全的Sigma协议。通过随机预言机，还可以构造出可证明安全的非交互式零知识证明，数字签名等。

2.3 Sigma协议的例子

下面的协议中，只有Schnorr协议给出了三个性质的证明，其它证明可去参考文献【5】中查看。

  1. Schnorr协议过程：
    设 $\mathbb{G}$ 是一个阶为素数 q 的循环群，其生成元为 $g \in \mathbb{G}$ 。设证明人 P 保存私钥 $\alpha \in \mathbb{Z}_q$，对应的公钥匙为 $u = g^{\alpha} \in \mathbb{G}$ 。 P 需要向 V 证明其拥有 $\alpha$。这里 $\alpha$是证据， $u=g^{\alpha}$ 是声明。Schnorr 身份认证协议过程为：【如下图】

    1. P 计算$\alpha_t \stackrel{R}{\longleftarrow}\mathbb{Z}_q,\ u_t\stackrel{R}{\longleftarrow}g^{α_t}$，并将 $u_t$发送给 V ; 【$commitment=u_t$】
    2. V 计算$c\stackrel{R}{\longleftarrow}C ,\ \ \ C \subset \mathbb{Z}_q$ 并将 c 发送给 P ； 【$challenge=c$】
    3. P 计算$\alpha_z \leftarrow \alpha_t + \alpha c$，并将$\alpha_z$发送给 V ； 【$response=\alpha_z$】
    4. V 检查如果 $g^{a_z} = u_t \cdot u^c$ ；V 输出accept，否则输出reject。

    上述sigma协议满足三个性质，证明如下：

    • 完备性：完备性显然成立，这里不再赘述。
    • 零知识性：证明零知识性的关键在于如何构建一个模拟器 ，使得其产生出来的交互信息分布和正常 P，V 交互产生的交互信息概率分布相同。如果我们设 $vk = u$，则模拟器可以通过下列方式计算出模拟的交互信息：$α_z \stackrel{R}{\leftarrow} Z_q; c \stackrel{R}{\leftarrow} C; u_t ←g^{α_z}/u^c$。 上述模拟的元素显然满足验证等式 $g^{a_z} = u_t \cdot u^c$。并且在真实的交互过程中， $c$ 和 $\alpha_z$ 分别在挑战空间 $C$ 和 $\mathbb{Z}_q$ 中服从均匀分布，且 $c,\alpha_z$ 相互独立。此外 $u_t$ 是由 $g^{\alpha_z}=u_t \cdot u^c$ 唯一确定的，而模拟器产生的交互信息也符合这个分布。因此模拟方案和真实方案不可区分。
    • 知识可靠性：假设攻击者对于同一个承诺 u 可以产生两个被接受的交互信息 $(u_t,c,\alpha_z)$ 和 $(u_t,c’,\alpha’_z)$ 且他们满足 $c \neq c’$，则有 $ g^{\alpha_z}=u_t \cdot u^c$ 和 $g^{\alpha’_z}=u_t \cdot u^{c’}$成立，将两式相除可以得到 $g^{\Delta \alpha}= u^{\Delta c}$,其中 $\Delta \alpha = \alpha_z - \alpha_z’$；$\Delta c = c-c’$。由于 $ \Delta c \ne 0$ ，且群 $\mathbb{G}$ 是素数阶得循环群，因此有 $1/ \Delta c \in \mathbb{G}$，则有 $g^{\Delta z/\Delta c} = u$，故 $\alpha = \frac{\Delta z}{\Delta c} $。

  2. Okamoto协议过程
    设$\mathbb{G}$是一个阶为素数 q 的循环群，其生成元为 $g \in \mathbb{G}。 h \in \mathbb{G}$是群中任意一个元素。Okamoto’s protocol中的关系为：$R=\{ ((\alpha,\beta),u) \in \mathbb{Z}^2_q \times \mathbb{G} : g^{\alpha}h^{\beta}=u \}$。
    假设承诺是 $u_t$，挑战是 $c$ 且 响应为 $(\alpha_z,\beta_z)$，则协议的过程如下图：其中 $C \subset \mathbb{Z}_q$。

    上述Okamoto协议也是一个sigma协议，满足以下三个性质，证明如下：

    • 完备性：若证明者与验证者均为诚实方，则将 $u_t,\alpha_z,\beta_z$ 代入验证方的等式易知成立： $$ g^{\alpha_z} h^{\beta_z} = g^{\alpha_t + c\alpha} h^{\beta_t + c\beta} = g^{\alpha_t} h^{\beta_t} \cdot (g^{\alpha} h^{\beta})^c = u_t \cdot u^c. $$

    • 零知识性： 为了证明零知识性，需构造一个模拟器，使得其输出分布与真实交互过程的输出分布相同。模拟器的输入为声明 $u = g^{\alpha}h^{\beta}$，模拟器过程如下：

      随机选取： $(\alpha_z, \beta_z) \stackrel{R}{\longleftarrow} \mathbb{Z}_q^2, \quad c \stackrel{R}{\longleftarrow} C$ 并计算： $u_t \leftarrow g^{\alpha_z} h^{\beta_z} / u^c$
      输出模拟交互三元组：$(u_t, c, (\alpha_z, \beta_z))$ 显然，模拟输出满足验证条件 $g^{\alpha_z} h^{\beta_z} = u_t \cdot u^c$。在真实交互中，$c$ 均匀分布于 $C$，$(\alpha_z, \beta_z)$ 均匀分布于 $\mathbb{Z}_q^2$，且两者独立。并且给定 $c, (\alpha_z, \beta_z)$ 时，$u_t$ 被唯一确定。因此模拟分布与真实分布完全一致，Okamoto 协议满足零知识性。

    • 知识可靠性：假设攻击者能生成两个有效交互： $(u_t, c, (\alpha_z, \beta_z))$ 与 $(u_t, c’, (\alpha’_z, \beta’_z)$，其中 $c \ne c’$ 且二者均被验证者接受。则有： $ g^{\alpha_z} h^{\beta_z} = u_t \cdot u^c, \ g^{\alpha’_z} h^{\beta’_z} = u_t \cdot u^{c’}. $ 两式相除可得：$g^{\Delta \alpha} h^{\Delta \beta} = u^{\Delta c}$，其中 $\Delta \alpha = \alpha_z - \alpha’_z$, $\Delta \beta = \beta_z - \beta’_z$, $\Delta c = c - c’$。 由于群阶为素数 $q$ 且 $\Delta c \ne 0$，存在逆元 $(\Delta c)^{-1}$，由此可得： $g^{\frac{\Delta \alpha}{\Delta c}} h^{\frac{\Delta \beta}{\Delta c}} = u$ 因此提取出的见证为： $ \alpha = \frac{\Delta \alpha}{\Delta c}, \quad \beta = \frac{\Delta \beta}{\Delta c}, $ 这说明协议满足知识可靠性。

  3. The Chaum-Pedersen协议过程
    该协议基于 DH-triples【DH三元组】。设 $\mathbb{G}$ 是一个阶为素数 q 的循环群，其生成元为 $g \in \mathbb{G}$。对于 $(\alpha,\beta,\gamma) \in \mathbb{G}$，如果$\alpha \beta = \gamma$ 我们就说 $(g^\alpha,g^\beta,g^\gamma)$ 是一个DH-triples。等价的，如果$(u,v,w)$是一个DH-tripes，当且仅当存在一个$\beta \in \mathbb{Z_q}$ 使得$v= g^\beta , w = u^\beta$ 。在Chaum-Pedersen 协议中的关系为：$R:= \{ (\ \beta,(u,v,w)\ ) \in \mathbb{Z}_q \times \mathbb{G}^3 : v=g^\beta ,w=u^\beta \}$;

    假设承诺为 $(w_t,v_t)$，挑战为 $c$ 且 响应为 $\beta_z$，则协议的过程为：【其中$C \subset \mathbb{Z}_q$】

    上述Chaum–Pedersen协议也是一个Sigma协议，满足以下三个性质，证明如下：

    • 完备性：
      若证明者与验证者均为诚实方，则将 $v_t, w_t, \beta_z$ 代入验证方的等式易知成立： $$ g^{\beta_z} = g^{\beta_t + c\beta} = g^{\beta_t} \cdot g^{\beta c} = v_t \cdot v^c, \quad u^{\beta_z} = u^{\beta_t + c\beta} = u^{\beta_t} \cdot u^{\beta c} = w_t \cdot w^c. $$ 因此验证者的验证条件均成立，协议满足完备性。

    • 零知识性：
      为了证明零知识性，需构造一个模拟器，使得其输出分布与真实交互过程的输出分布相同。
      模拟器的输入为声明 $(u, v, w)$，模拟器过程如下：

      随机选取： $\beta_z \stackrel{R}{\longleftarrow} \mathbb{Z}_q, c \stackrel{R}{\longleftarrow} C$ 并计算： $v_t \leftarrow g^{\beta_z} / v^c, w_t \leftarrow u^{\beta_z} / w^c$，输出模拟交互四元组：$((v_t, w_t), c, \beta_z)$ ， 显然，模拟输出满足验证条件： $ g^{\beta_z} = v_t \cdot v^c, u^{\beta_z} = w_t \cdot w^c. $ 在真实交互中，$c$ 均匀分布于 $C$，$\beta_z$ 均匀分布于 $\mathbb{Z}_q$，且两者独立。并且给定 $c, \beta_z$ 时，$(v_t, w_t)$ 被唯一确定。因此模拟分布与真实分布完全一致，协议满足零知识性。

    • 知识可靠性：
      假设攻击者能生成两个有效交互： $((v_t, w_t), c, \beta_z)$ 与 $((v_t, w_t), c’, \beta’_z))$，其中 $c \ne c’$ 且二者均被验证者接受。则有： $$ g^{\beta_z} = v_t \cdot v^c, \quad u^{\beta_z} = w_t \cdot w^c, \quad g^{\beta’_z} = v_t \cdot v^{c’}, \quad u^{\beta’_z} = w_t \cdot w^{c’}. $$ 两式相除可得： $ g^{\Delta \beta} = v^{\Delta c}, \quad u^{\Delta \beta} = w^{\Delta c} $， 其中 $\Delta \beta = \beta_z - \beta’_z$，$\Delta c = c - c’$。 由于群阶为素数 $q$ 且 $\Delta c \ne 0$，因此存在逆元 $(\Delta c)^{-1}$，由此可得：$\beta = \frac{\Delta \beta}{\Delta c}$ 因此提取出的见证为 $\beta$，这说明协议满足知识可靠性。

2.3 线性Sigma协议

这一节介绍一个更加一般的sigma协议，线性sigma协议。

  1. 线性simga协议介绍
    上述Schnorr, Okamoto, 和 Chaum- Pedersen 协议都是一种更加一般的 Sigma protocol 的特例。这种更加一般的 Sigma protocol 是要证明元素之间的线性关系。设$\mathbb{G}$是一个阶为素数 q 的循环群，它的生成元为$g \in \mathbb{G}$我们考虑一个布尔函数 $\phi$： $$\phi (x_1,x_2,…,x_n):={u_1=\prod_{j=1}^{n}g_{1j}^{x_j}\ \wedge \ u_2=\prod_{j=1}^{n}g_{2j}^{x_j} \wedge … \wedge u_m=\prod_{j=1}^{n}g_{mj}^{x_j} }$$ 在函数 $\phi$ 中， $g_{ij} ,u_i \in \mathbb{G}$。这些群元素一部分可以是系统参数或常量，另一些元素则是针对函数的特殊变量。$x_i \in \mathbb{Z}_q$ 是函数 $\phi$ 的入参，当函数中的所有等式成立则 $\phi$ 返回true。对这样函数的一个特定类 F，定义关系：$R:= {((\alpha_1,…,\alpha_n),\phi) \in \mathbb{Z}_q^n \times F: \phi(\alpha_1,…,\alpha_n)= true }$
    在R中，一个函数 $\phi$ 是一个声明，而一个使得这个函数 $\phi$ 为 true 的 $(\alpha_1,…,\alpha_n) \in \mathbb{Z}_q^n$ 是这个函数 $\phi$ 的 证据。而我们称这样的协议为 linear protocols 的原因在于如果我们对函数 $\phi$ 中的等式取对数可以得到：

$$ Dlog_g({u_j})= \sum_{j=1}^n x_i \cdot Dlog_g(g_{ij}) \ \ \ \ \ (i=1,…,m) $$

一般 linear Sigma protocol 的过程为：

  1. 关于线性sigma协议的一些说明
    事实上，Schnoor协议，Okamoto协议和The Chaum-Pedersen协议都是线性Sigma协议的一种特例，我们详细说明如下：

    • 事实上，令线性sigma协议中的参数如下：即可得到 Schnorr‘s protocol 。

      • $P((\alpha_1,…,\alpha_n),\phi)$中，n = 1，$\phi(x):= {u=g^x}$
      • $\alpha_{tj}$ 中，$j = 1$ ;
      • $u_{tm}$ 中，$m = 1$ ; 【$u_{tm}$事实上就是承诺$\phi(\alpha_{t1})$】

    • 事实上，令线性sigma协议中的参数如下：即可得到 Okamoto’s protocol 。

      • $P((\alpha_1,…,\alpha_n),\phi)$中，n = 2 ; $\phi(x,y) := {u=g^xh^y}$
      • $\alpha_{tj}$ 中，$j = 2$ ;
      • $u_{tm}$ 中，$m = 1$ ; 【$u_{tm}$事实上就是承诺$\phi(\alpha_{t1},\alpha_{t2})$】

    • 事实上，令线性sigma协议中的参数如下：即可得到 The Chaum-Pedersen protocol。

      • $P((\alpha_1,…,\alpha_n),\phi)$中，n = 1 $\phi(x) := { v=g^x \wedge w=u^x}$
      • $\alpha_{tj}$ 中，$j = 1$ ;
      • $u_{tm}$ 中，$m = 2$ ; 【$u_{tm}$事实上就是承诺$\phi(\alpha_{t1})$】

线性sigma协议是一个关于关系 R 的 Sigma协议并且满足知识可靠性和零知识性，证明略。

2.4 基于同映射的Sigma协议

  1. 基于同映射的Sigma协议介绍
    我们可以利用群同态来更加清晰高效的来描述到目前为止的介绍的所有Sigma协议。设$\mathbb{H}_1,\mathbb{H}_2$是两个不知道阶的交换群，以及一个同态映射$\varphi: \mathbb{H}_1 \to \mathbb{H}_2$。为了表达的方便， 群$\mathbb{H}_1$中的运算为群加法， 群$\mathbb{H}_2$中的运算为群乘法。设$u \in \mathbb{H}_2$，证明者需要向验证着证明他知道在映射$\varphi$下 u 的原象。在这种Sigma protocol中，关系为： $$ R:={(\alpha,(u,\varphi)) \in \mathbb{H}_1 \times (\mathbb{H}_2 \times F):\varphi(\alpha)=u} $$ 其中$\alpha \in \mathbb{H}_1$是映射 $\varphi$ 对于 $u \in \mathbb{H}_2$ 的原象。协议的过程如下：

  2. 一些特例
    在$|\mathbb{H}_1| \times |\mathbb{H}_2|$最小素因子至少为 |C| 的情况下，基于同态映射的Sigma protocol满足knowledge soundness以及special HVZK。

    • Schnorr 协议中

      • $\mathbb{H}_1 := \mathbb{Z}_q,\ \mathbb{H}_2 := \mathbb{G},and \ \ \ \ \varphi_1(x):=(g^x)$
      • $R:={(\alpha,(u,\varphi)) \in \mathbb{H}_1 \times (\mathbb{H}_2 \times F):\varphi(\alpha)=u}$

    • Okamoto协议中

      • $\mathbb{H}_1 := \mathbb{Z}_q^2,\ \mathbb{H}_2 := \mathbb{G},and \ \ \ \ \varphi_1(x,y):=(g^xh^y)$
      • $R:={((\alpha,\beta),(u,\varphi)) \in \mathbb{H}_1^2 \times (\mathbb{H}_2 \times F):\varphi(\alpha,\beta)=u}$

    • The Chaum-Pedersen协议中

      • $\mathbb{H}_1 := \mathbb{Z}_q, \mathbb{H}_2 := \mathbb{G}^2,and \ \ \ \ \varphi_2(x):=(g^x,u^x)$
      • $R:={(\alpha,(u_1,u_2,\varphi)) \in \mathbb{H}_1 \times (\mathbb{H}_2^2 \times F):\varphi(\alpha)=(u_1,u_2}$

    • 一般linear sigma protocol中，对应于同态映射的表示方式为：

      • $\mathbb{H}_1 := \mathbb{Z}_q^n$ , $\mathbb{H}_2:=\mathbb{G}^m $ 并且
      • $\varphi_3(x_1,…,x_n) := (\prod_{j=1}^ng_{1j}^{x_j},…,\prod_{j=1}^ng_{mj}^{x_j})$

三、Fait-Shamir启发式

Fiat-Shamir 变换是一种将 Sigma 协议 转化为 非交互式零知识证明 的通用技术。通过该方法，证明者（Prover）无需与验证者（Verifier）进行多轮交互，只需一次性发送证明信息，即可完成验证过程。
进一步地，通过 Fiat-Shamir 变换，还可以将 Sigma 协议构造为 数字签名方案，其含义是“只有掌握 Sigma 协议中秘密的实体，才能对消息进行签名”。

3.1 Fiat-Shamir启发式的做法

Fiat-Shamir 变换的核心思想是：
引入一个 抗碰撞且输出均匀分布 的哈希函数 $H$，并利用其输出值来替代原本交互式协议中的挑战值。 在 Sigma 协议中，原本挑战 $c$ 由验证者随机生成。通过 Fiat-Shamir 变换，证明者可以自主计算挑战 $c=H(t,y)$ ，其中 $t$ 表示证明者生成的承诺，$y$ 表示声明。协议的其他部分保持不变，这样即可将原本的交互式 Sigma 协议转化为 非交互式零知识证明。

若希望将其改造成 数字签名方案，只需在计算挑战时引入待签名的消息 $m$： 即令挑战 $c=H(t,y,m)$ 。这样得到的签名表示“拥有 Sigma 协议秘密的实体对消息 $m$ 进行了签名”。

3.2 举例说明

以 Schnorr协议为例：在交互式版本中，验证者会从挑战空间中随机选择挑战值 $c$。应用 Fiat-Shamir 变换后，证明者可通过哈希函数自行生成挑战 $c = H(u_t, u)$，具体步骤如下：

  • 证明者（Prover）：

    1. 选择随机数 $\alpha_t$ 并计算 $u_t = g^{\alpha_t}$；
    2. 计算挑战 $c = H(u_t, u)$；
    3. 计算响应 $\alpha_z = \alpha_t + \alpha \cdot c$，并将 $u_t,\alpha_z$ 发送给验证者。

  • 验证者（Verifier）： 验证以下关系是否成立： $g^{\alpha_z} = u_t \cdot u^c$ 若成立，则接受该证明。

若要构造 Schnorr 签名方案，则将消息 $m$ 也加入哈希输入中 $c = H(u_t, u, m)$，这样就得到了基于 Fiat-Shamir 变换的非交互式 Schnorr 签名方案。

zk-SNARK

参考文献：

参考文献

← 初入密码界