On Sigma Protocol

1 An example

先看个小例子，记$p,q$为素数，且$q|(p-1)$，记$g$为$\Z^*_p$中阶为$q$的元素

假设Prover随机选择了$w\in_R\Z_q$并公开$h=g^w \ mod \ p$，Verifier知道$(p,q,g,h)$，Verifier可以验证$p,q$为素数，验证$g,h$的阶为$q$

由于$\Z^*_p$中只有一个阶为$q$的子群，这意味着$h\in<g>$，也即必然存在一个$w$，满足$h=g^w \ mod \ p$，但是并不意味着Verifier一定认可Prover知道这个$w$

为了让Verifier相信，Prover和Verifier执行下列协议

1. Prover随机选择$r\in_R \Z_q$，然后向Verifier发送$a=g^r \ mod \ p$
2. Verifier随机选择$e\in _R\Z_{2^t}$并作为挑战发送给Prover（这里$t$固定且$2^t<q$）
3. Prover根据挑战，计算$z=r+ew \ mod \ q$并发送给Verifier，然后Verifer验证$p,q$为素数，验证$g,h$的阶为$q$，验证$g^z=ah^e \ mod \ p$，当且仅当这三个事件同时成立时接受Prover

这里考虑一个问题，若某个Prover $P^*$，可以在发送$a$后响应两个不同的挑战$e,e'$，且$e\neq e' \ mod \ q$，这意味着$P^*$可以计算$z\neq z'$

此时有

$$ g^z=ah^e \ mod \ p\\g^{z'}=ah^{e'} \ mod \ p $$

两式相除可以得到

$$ g^{z-z'}=h^{e-e'} \ mod \ p $$

由于$e\neq e' \ mod \ p$，因此$P^*$可以计算$(e-e')^{-1} \ mod \ q$，从而有$h=g^{(z-z')(e-e')^{-1}} \ mod \ p$

若恶意的Prover不知道$w$，则其至多只能响应一个挑战，否则通过上述分析，这个Prover可以计算出$w$，故上述证明错误的概率为$1/2^t$

上述过程也叫知识证明（Proof of Knowledge）

另一方面，上面这个协议不是零知识，为了使得找到这样一个$w$是非平凡的，$q$必须很大（比如指数级），此外为了使单轮协议执行的错误概率可忽略，$2^t$也必须是指数级大，大到标准的rewind技术无法正常（指数级大会让模拟器很难预先猜测$e$的值，从而其不知道Verifier是否存在某些恶意的策略，使得Verifer在多次协议执行后可以计算出$w$）

因此上述协议只是诚实Verifier零知识的（Honest Verifier Zero-knowledge，HVZK），为了模拟该协议，只需要随机选择$z\in_R\Z^*_p,e\in_R\Z_q$，然后计算$a=g^zh^{-e} \ mod \ p$即可，显然$(a,e,z)$具有与真实协议执行（诚实Pover和诚实Verifier）相同的分布

甚至可以这么做：先选择任意给定的$e$，然后生成一个会话并将$e$作为挑战，此时只需要随机选一个$z$并计算对应的$a$即可，换言之，模拟器不必选择$e$，其可以将$e$作为输入

但是HVZK并不是一个有用的属性，因为在实践中假设Verifier是诚实的是没有意义的，不过这种较弱的属性可以用于构造中的组件，因为通过上面的分析，我们可以知道这样的协议可以防止Prover主动作弊

还有一点需要注意的，实际协议中$p,q$在很长一段时间内是固定的，因此Verifier只需要完成一次素性检验即可

2 Definitions

基于Schnorr协议，接下来定义一些抽象属性

• $R$：二元关系，其是$\{0,1\}^*\times \{0,1\}^*$的一个子集，且要求$(x,w)\in R$，$w$的长度为$x$的多项式（$w=p(|x|$）
• $x$：某些可计算问题的实例
• $w$：该实例的某一解

举个例子，可以定义关系$DL$如下

$$ DL=\{(x,w)|x=(p,q,g,h),ord(g)=ord(g)=q,h=g^w\} $$

其中$p,q$为素数，$g,h\in \Z^*_p,w\in \Z_q$，此时关系$R$包含上述DLOG问题及其所有解

接下来我们关注下列形式的协议，其中$x$作为Prover和Verifier的公共输入，$w$满足$(x,w)\in R$作为Prover的私密输入，并假设$P,V$都是PPT机器

1. $P$发送消息$a$
2. $V$发送一个长度为$t$比特的串$e$
3. $P$响应一个$z$，$V$根据其已知信息（$x,a,e,z)$进行验证并决定是否接受$P$

上述协议中，$P$对$V$的唯一优势在于其知道$w$，因此引申出下列定义

• Definition 1：称协议$\mathcal P$为一个关于关系$R$的$\Sigma$协议，满足

  • $\mathcal P$包含上述提到的三步交互，且满足完备性：若$P,V$正确执行协议，则$V$总是接受$P$
  • 特殊合理性：对于任意公共输入$x$和任意两个关于$x$的可接受的交互脚本$(a,e,z),(a,e',z')$，满足$e\neq e'$，可以高效计算出$w$，满足$(x,w)\in R$
  • 特殊诚实Verifier零知识性：存在多项式时间的模拟器$M$，输入$x$和随机的$e$，输出一个可接受的交互脚本$(a,e,z)$，该脚本与关于相同输入$x$的真实诚实协议执行具有相同的分布

Schnorr的上述示例是该定义的特例，可以用$\Sigma$协议来作为子程序构建任何协议

定义$L_R$为一个集合：存在$w$，满足$(x,w)\in R$，根据上述定义，特殊合理性表明了关于$R$的$\Sigma$协议是一个错误概率为$2^{-t}$的交互式协议（协议同样适用于$DL$）

不过有时候Verifier可以自己检查中的成员归属，尽管如此，这个协议还是有一定的意义的，看下面这个引理

• Lemma 1：在并行组合下，$\Sigma$协议的性质不会改变

比如说并行重复执行两个$\Sigma$协议，可以得到挑战长度为$2t$的新协议

• Lemma 2：若关于$R$的$\Sigma$协议存在，则对于任意$t$，都存在一个关于关系$R$的挑战长度为$t$的$\Sigma$协议

引理2的证明如下

• Proof：记$t'$为给定协议$\mathcal P$的挑战长度，则对于任意挑战长度$t<t'$的协议可以这样得到：$P$先发送第一条消息，然后$V$发送长度为$t$的串$e$，之后$P$在$e$后附加$t'-t$个零比特作为新的串$e'$，同时为$e'$计算响应$z$，将其作为协议$\mathcal P$的响应

上述方法对于只需要并行运行$j$次（$jt'\geq t$）

3 Proof of Knowledge

Bellare和Goldreich$[2]$提出了以下知识证明的标准定义，但是定义一点也不简单

对于一些Prover $P^*$，若其声称知道某些东西，是否应该要求这些信息在某些时候出现在内存中，或者以某些方式编码在程序中（如果是的话，那么如何知道这些信息在哪里）

因此有了下面这个问题：如果说可以用机器有效的计算出这个信息，则意味着$P^*$确实有这些信息

• Definition 2：记$\kappa()$为串到区间$[0..1]$的函数，称关于关系$R$的协议$(P,V)$为知识错误为$\kappa$的知识证明（Proof of Knowledge），有

  • Completeness：对于公共输入$x$，若诚实的$P$的私密输入$w$，有$(x,w)\in R$，则$V$总是接受$P$
  • Knowledge soundness：存在一个概率算法$M$，称为知识抽取器，$M$以$x$作为输入，并以可rewind和黑盒的方式访问Prover并尝试计算$w$，要求对于任意的$P^*$，令$\epsilon (x)$为$V$接受$x$的概率，则存在一个常数$c$，当$\epsilon (x)>\kappa (x)$时，$M$输出一个正确的$w$的期望时间（访问$P^*$视为一步）至多为

$$ \frac{|x|^c}{\epsilon(x)-\kappa(x)} $$

我们可以将误差$\kappa()$视为在不知道正确的$w$的情况下说服Verifier的概率，如果希望做到更好，则需要一些实际计算$w$的能力，而计算$w$的效率越高，则意味着Prover越可以说服Verifier

根据前面提到的$\Sigma$协议，我们期望关系$R$的任何$\Sigma$协议都是知识错误为$2^{-t}$的知识证明，事实上这里有个定理

• Theorem 1：令协议$\mathcal P$为关于关系$R$的$\Sigma$协议，其挑战长度为$t$，则$\mathcal P$的知识证明的错误为$2^{-t}$

证明如下

• Proof：完整性显然成立

对于合理性，记$H$为一个二进制矩阵，其中行是所有$P^*$可能的选择集$\rho$，列是所有可能的挑战值$e$，对于矩阵中第$\rho$行第$e$列的元素$H_{}\rho ,e$，若$V$采用该挑战$e$并接受，则$H_{\rho ,e}=1$，否则$H_{\rho ,e}=0$

将$P^*$视为黑盒并随机选择挑战，这么做可以随机检查$H$中的一个元素，通过对$P^*$进行rewind，可以得到对该行的随机元素（比如说$P^*$和之前采用相同的随机掷币）

我们的目标是找到同一行的两个1，使用特殊的稳健性，得到的两个对话为我们提供了足够的信息，利用前面介绍的方法就可以有效地计算$x$的witness $w$

由于我们只知道$\epsilon:\epsilon (x)$等于$H$中1元素的个数除以总的元素个数，但是这并不能代表指定的某一行中1元素的分布（比如某一行只有一个1，则无论如何都找不到第二个）

不过可以换种方式考虑这个矩阵：若一行中，1的占比至少为$\frac{\epsilon}{2}$，则将其标记为重行（heavy row），然后通过一些计数参数，可以观察到超过一半的1位于重行内

接下来记矩阵$H'$为$H$的子矩阵，$H'$由$H$中所有不为重行的行组成，然后记$h'=|H'|,h=|H|$，则根据假设，有$H$中1的数量为$h\epsilon$，而$H'$中1的数量应当小于$\frac{h'\epsilon}{2}$，若将重行中1的数量记为$g$，则$g$满足

$$ g>h\epsilon-\frac{h'\epsilon}{2}\geq h\epsilon-{h\epsilon\over 2}={h\epsilon\over 2} $$

若此时假设$e\geq 2^{-t+2}$，则每个重行中必然包含至少两个1，因此可以随机重复探测$H$，直到找到一个1为止，该过程预期的重复次数为${1\over \epsilon }$，然后根据前面的方式，我们有大于0.5的概率在第一次找到1时，这个1所在的行是重行，假设这个行确实是重行，然后我们继续在该行随机探测，则只需要一次尝试就找到第二个1的概率为$\frac{\epsilon /2 \cdot 2^t-1}{2^t}$，因此再次随机探测找到1的期望次数为$T=\frac{2^t}{\epsilon /2 \cdot 2^t-1}\leq 4/\epsilon$，该不等式来源于我们对$\epsilon$的假设，因此整个过程会在$O({1\over \epsilon })$次尝试结束

综上，同一行中找到两个1的期望时间为$O({1\over \epsilon })$（实际上这个时间会更短，因为${1\over \epsilon }$实际上小于定义中的要求，定义中要求的是${1\over \epsilon -2^{-t}}$）

不过这是在大于0.5的概率在第一次找到1的情况，仍然有小于0.5的概率第一次找不到1，此时会需要更多次尝试才能找到另一个1，因此需要引入紧急中断算法，具体如下

1. 对$H$进行随机采样直到找到第一个1（确定该行）
2. 然后并行进行下列两项工作，当其中一个终止时另一个也终止

   2a：随机采样该行，直到找到第二个1时终止

   2b：对$H$进行随机采样并记为$a$，同时随机选择集合$\{1,...,d\}$中的一个数$b$（其中$d$为常数）并记为$b$，当且仅当$a=b=1$时终止

由于$d$为常数，因此上述紧急中断算法的期望时间为$O({1\over \epsilon })$，不过如果步骤1中找到的是一个重行，我们希望步骤2a执行时间比2b长，因此需要选择合适的$d$来确保这个问题，因为步骤2b在$k$次执行后中止的概率为$\frac{e}{d(1-\epsilon/d)^{k-1}}$，因此步骤2b在$k$或更少次的执行后终止的概率至多为$\frac{k\epsilon}{d}$，对于$k=\frac{d}{2\epsilon}$，这个界为$1\over 2$，因此可以得到步骤2b需要超过$\frac{d}{2\epsilon}$次尝试才能以超过$1\over 2$的概率终止，此时可以选择大一些的$d$，比如$d=16$，步骤2b会在$\frac{8}{\epsilon}$次尝试后以至少0.5的概率终止，此时如果第一次选中的行确实是重行，则步骤一会在少于$2T\leq \frac{8}{\epsilon}$次尝试内以至少0.5的概率终止，从而步骤2a在2b前终止的概率大于${1\over 2}*{1\over 2}={1\over 4}$

综上，如果步骤1找到的是一个重行，并且步骤2a在2b前终止，那么上述过程在同一行找到两个1的概率大于${1\over 2}*{1\over 4}={1\over 8}$，且期望时间为$O({1\over \epsilon })$

然后我们令抽取器重复上述算法，直到成功为止，由于期望的重复次数恒定（8次），因此我们得到了一个期望时间为$O({1\over \epsilon })$的算法

但是考虑一个问题，如果$2^{-t}<\epsilon <2^{-t+2}$又如何呢？如果$\epsilon$很小的话，我们有足够多的时间来探测整行，此时需要一个单独的算法来处理这种情况，因此接下来这个算法和上面那个算法并行运行

首先利用$\epsilon$来定义$\delta$，$\epsilon =(1+\delta)2^{-t}$，因此可以得到$0<\delta <3$，令$R$表示$H$中行的数量，此时整个矩阵中1的数量为$(1+\delta)R$，这么多1中至多有$R$个在单独的一行，且至少有$\delta R$个1分布在包含至少两个1的行中，这些包含两个1的行称为半重行（semi-hevy row），然后接下来算法如下

1. 对$H$进行随机采样直到找到第一个1（确定该行）
2. 对整行随机采样，直到找到另一个1，若没找到则回到第一部

注意到半重行包含的1的数量与整个矩阵包含的1的数量的比值为$\frac{\delta }{1+\delta}$，与整个矩阵元素数量的比值为$\frac{\delta }{2^t}$，因此找到一个1的期望次数为$\frac{1}{\epsilon}=\frac{2^t}{1+\delta}$，在半重行中找到一个1的期望次数为$\frac{2^t}{\delta}$，我们希望在找到$\frac{1+\delta}{\delta}$个1之后才在半重行中找到1，这个期望为$O(\frac{2^t(1+\delta)}{\delta})$，此外我们在步骤1中花了$O(\frac{2^t}{\delta})$次，因此总共花了$2^t(\frac{1}{\delta}+\frac{1+\delta}{\delta})=\frac{2^t(2+\delta)}{\delta}$次，因此期望次数为$O(\frac{2^t}{\delta})$

4 The OR-proof

$\Sigma$协议的一个基本构造允许Prover对两个输入$x_0,x_1$，证明其知道一个$w$，满足要么有$(x_0,w)\in R$成立，要么有$(x_1,w)\in R$成立，但是不揭示具体是两者中的哪个成立

假设给定关系$R$的$\Sigma$协议$\mathcal P$，同时假设$x_0,x_1$作为$P,V$的公共输入，$w$为$P$私密输入，满足$(x_b,w)\in R$，其中$b=0$或$b=1$，因此上述构造就是要求Prover利用协议$\mathcal P$完成对两个实例的证明

对于$x_b$而言，Prover可以直接执行协议，但是对于$x_{1-b}$而言，其需要利用模拟器来完成协议的执行，此外如果放宽对Prover对响应的限制，也即允许其选择挑战来响应，此时Prover可以同时证明这两个实例

更具体而言，就是下面这个协议，记为$\mathcal P_{OR}$

1. $P$利用$(x_b,w)$计算第一条消息$a_b$，然后随机选择$e_{1-b}$并将$(x_b,e_{1-b})$作为模拟器的输入，同时得到模拟器的输出$(a_{1-b},e_{1-b},z_{1-b})$，$P$将$a_0,a_1$发送给$V$
2. $V$选择一个长度为$t$比特的随机串$s$并发送给$P$
3. $P$计算$e_b=s\oplus e_{1-b}$并计算对应的响应$z_b$，$P$向$V$发送$(e_0,z_0,e_1,z_1)$
4. $V$检查是否有$s=e_0\oplus e_1$，同时检查$(a_0,e_0,z_0),(a_1,e_1,z_1)$都是正确的证明

令关系$R_{OR}=\{((x_0,x_1),w)|(x_0,w)\in R \ or \ (x_1,w)\in R\}$，有下面这个定理

• Theorem 2：协议$\mathcal P_{OR}$为关系$R_{OR}$上的$\Sigma$协议，对于任意Verifier $V^*$，对于$P$的私密输入$w$，满足$(x_b.w)\in R$，$P$和$V^*$之间的交互脚本的分布与$b$独立

证明如下

• Proof：不难看出这是个三步，完备性显然成立，合理性如下

首先令两个可接受的交互脚本如下，满足$s\neq s'$

$$ (a_0,a_1,s,e_0,e_1,z_0,z_1),(a_0,a_1,s',e_0',e_1',z_0',z_1') $$

显然对于某个$c=0$或$c=1$，满足$e_c\neq e_c'$，因此利用前面介绍的方法，可以从$(a_c,e_c,z_c),(a_c,e_c',z_c')$中计算出$w$，满足$(x_c,w)\in R$

此外HVZK也是易证的，对于给定的$s$，随机选择$e_0$，然后令$e_1=e_0\oplus s$，分别以两个输入$(x_0,e_0),(x_1,e_1)$运行模拟器$M$即可

该定理中的最后一个说法的意思是：协议$\mathcal P_{OR}$是证据不可区分的（Witness Indistinguishable，WI），这意味着Prover可能知道多个$w$，使其可以完成协议执行，但是无法区分Prover具体使用的哪个$w$，且这个属性是在HVZK成立时也满足的

5 Hard Relations

显然，如果关系$R$很简单的话，Verifier可以自己计算出来，没有必要和Prover执行协议，因此本节定义困难关系，意思就是对于$(x,w)$，若只给出$x$，则找到与其相关的$w$是困难的

• Definition 3：若关系$R$满足下列性质，则称其是困难关系

  1. 存在一个PPT算法$G$，称为生成器，输入$1^k$并输出一对关系$(x,w)\in R$，满足$|x|=k$
  2. 对于任意的PPT算法$A$，给定生成器$G$在输入$1^k$所输出$x$作为算法$A$的输入，记$w_A$为算法$A$的输出，则有

$$ Pr[(x,w)\larr G(1^k),w_A\larr A(x):(x,w_A)\in R]=negl(k) $$

例如标准DLOG假设是困难关系

引入困难关系的概念后，回顾上一节提到的$\mathcal P_{OR}$协议，上一节提到了该协议在挑战长度较大时不为零知识的（实际上$\Sigma$协议都不是零知识的）

但是如果基于困难关系的话，协议在面对恶意Verifier时具备一定的安全性，这个性质称为证据隐藏（Witness Hiding，WH），意思是即便是恶意的Verifier也无法通过与Prover的交互来计算两个实例中的任意一个的解

具体而言，来看一个关系$R$和生成器$G$，假设$R$有一个$\Sigma$协议$\mathcal P$，对于任意多项式时间Verifier $V^*$，考虑下列交互

• 运行$G$，得到一对关系$(x,w)\in R$，将$w$作为$\mathcal P$中$P$的私有输入
• 令$V^*$与$P$在公共输入$x$上执行任意（多项式）次的$\mathcal P$
• $V^*$输出串$w^*$

若有$(x,w^*)\in R$，则表示$V^*$赢得了游戏

• Definition 4：当且仅当$V^*$赢得上述游戏的概率可忽略时，称$\mathcal P$具有证据隐藏性质

$\mathcal P_{OR}$也可以有类似的WH性质，不过需要稍微修改一下生成器，修改为$G_{OR}(1^k)$，并将生成器运行两次，得到两个输出$(x_0,w_0),(x_1,w_1)$，此时随机随机选择单比特$b$，得到对应的输出$w_b$

• Theorem 3：若$R$为困难关系，则关于关系$R_{OR}$的协议$\mathcal P_{OR}$具有证据隐藏性质

这个定理的证明可以看原文$[1]$

6 Identification Schemes from Sigma-protocols

接下来考虑一个问题，如果说我们想为用户$U_1,...,U_n$构造一个安全的身份识别方案，可以这么做

给定关系$R$的$\Sigma$协议$\mathcal P$，运行$n$次生成器$G(1^k)$，得到$n$对输出$(x_1,w_1),...,(x_n,w_n)$，然后将$w_i$分配给第$i$个用户作为其私钥，同时公开所有的$x_i$

如果说用户$U_i$需要证明其身份，其可以作为Prover在$x_i$上执行协议$\mathcal P$（假设$\mathcal P$的挑战串长度为$k$比特，并假设其满足WH性质）

完备性显然成立，此外合理性和证据隐藏性意味着，任意敌手$A$（以任意策略）在协议中作为Verifier与用户$U_i$交互，无法以不可忽略的概率作为Prover成功执行协议

换言之，如果敌手$A$可以不可忽略的概率作为Prover执行协议，则意味着敌手可以找到$w_i$，具体来说的话，考虑下面这个算法

1. 令$A$扮演Verifier并与用户$U_i$交互任意多次
2. 考虑知识抽取器$M$，$M$确保协议知识证明的合理性错误为$2^{-k}$，在与诚实的Prove后，令$M$与$A$交互
3. 记$M$的输出为$w_i$，算法输出$w_i$

如果A作为Prover的成功概率不可忽略，则上述算法会在期望多项式内返回正确的$w_i$

换言之，若这个算法可以在输入$x_i$上与Prover交互并计算得到$w_i$，满足$(x_i,w_i)\in R$，则意味着协议$\mathcal P$的WH性质不成立，由于前面我们假设了协议满足WH性质，因此上述算法无法返回正确的$w_i$

但是这里有一个潜在的问题，假设敌手的攻击分为两个阶段进行，先从诚实Prover（用户$U_i$）处获取信息，然后再尝试向诚实Verifier执行协议，第二阶段中或许敌手无法从诚实Verifier处获得任何信息，但是真是协议执行可能不是如此

比如说中间人攻击：假设用户$U_i$向一个被攻破的Verifier $\widetilde V$证明其身份，也即$\widetilde V$与敌手$A$勾结，此时每次$U_i$向$\widetilde V$发送消息时，$\widetilde V$都会立即转发给$A$，然后$A$再转发给一个诚实的Verifier $V$，此时$V$回复的消息相当于回复给$U_i$的消息，显然$U_i$和$V$都是诚实的，因此$V$会接受

但是否意味着协议有问题，确实有问题，但是问题不出在协议本身的性质，而是属于信道不安全，上述MITM攻击中可以将诚实的$U_i$和$V$视为通过了不安全的信道$\widetilde V$（与$A$）进行通信，协议仍然满足证据隐藏等基本性质，只不过可以归结于协议实现的安全性不足以满足实际场景中存在的问题，因为上述场景中Prover无法区分恶意的Verifier和诚实的Verifier的身份，也即我们没有假设Verifier具有其身份或公钥

因此假设Prover和Verifier都有公钥，并且始终可以确定具有给定名称的参与者的公钥，并修改协议如下：当Prover $U_i$想要向Verifier $U_j$证明其身份时，首先进行身份交换并确认对方的公钥$x_i,x_j$，之后$U_i$为了证明知道$w_i$，$U_i$和$U_j$进行$\mathcal P_{OR}$协议（$U_i$证明其知道$w_i$或$w_j$），显然$w_j$只有$U_j$知道，因此$\mathcal P_{OR}$协议结束后，$U_j$一定可以确认$U_i$知道$w_i$，从而确认了Prover是$U_i$

考虑另一种情况：敌手$A$尝试向诚实的$U_v$扮演$U_i$的身份，同时$U_i$正在向被攻破的用户$U_j$证明身份，$U_v$那里，

6.1 Better to use signatures？

上面我们讨论了$\Sigma$协议在身份认证中的小例子，但是存在下面这个问题：假设$U_i$有一对关于安全签名方案的密钥对$(pk_i,sk_i)$，此时Verifier可以发起一个挑战$c$，并要求$U_i$返回对$c$的签名$sig_{sk_i}(c)$来证实其身份，Verifier用公钥验证即可，如果Verifier选择了一个其之前尚未使用过的$c$，则$U_i$返回签名时没什么问题，但是签名方案的安全性意味着如果没有私钥$sk_i$，即便敌手可以选择需要签名的内容进行签名，其也无法对真正的签名者尚未签名的内容进行签名

这个问题只需要$\Sigma$协议两条消息交互即可，但是在用户隐私方面有一个非常重要的区别：如果$U_i$通过签名的方式证明其身份，则签名可能会被Verifier暴露给其他人，以证明Verifier和$U_i$进行了交互，即便协议要求挑战$c$是随机选择的，Verifier也可以用时间、日期、地点等信息的Hash值来代替随机选择的$c$，从而获得$U_i$的一些信息，这个隐私问题会侵犯$U_i$的隐私，这个特性也被称为可否认性

而且这里还有一个问题，使用签名进行身份识别应当是不可否认的，但是使用$\Sigma$协议或者OR方式进行证明却是可否认的，因为Verifier总是可以利用自己的密钥来模拟协议，因此协议脚本并不能使其他人信服他确实和$U_i$进行了交互

7 Zero-Knowledge from Sigma-protocols

为了完整性，考虑一个构造，允许从困难关系$R$的$\Sigma$协议$\mathcal P$生成一个有效的零知识协议

不失一般性，我们假设协议$\mathcal P$具有Witness Hiding性质，然后公共输入$x$，Prover的私密输入$w$，协议如下

1. $V$运行$G(1^k)$，得到$(x',w')\in R$
2. $V$向$P$发送$x'$，并利用协议$\mathcal P$证明其知道$w'$，此时$V$为Prover，$P$为Verifier
3. 若$P$接受，$P$用OR方式证明其知道$w$或$w'$

接下来看一下协议的零知识性：考虑一个模拟器与一个Verifier $V^*$，$V^*$在步骤2中以可忽略的概率说服$P$，则协议和模拟过程会在步骤2停止，否则我们可以对$V^*$进行rewind并抽取出$w'$，此时再利用$w'$进行步骤3即可，根据Witness Indistinguishable的性质，没有人知道$P$用的是$w$或$w'$，因此协议是零知的

对于合理性而言，如果采用加密安全的合理性变体，合理性也是满足的：为了从成功的$P^*$中抽取$w$，我们可以先执行协议的前两部，然后对第3步进行rewind来抽取出$w^*$，满足$(x,w^*)\in R$或$(x',w^*)\in R$，不过第二种情况（$(x',w^*)\in R$）发生的概率可忽略不计，因为步骤2中给出的证明时Witness Hiding的，且$R$是困难关系，因此成功的$P^*$必然知道$w$，满足合理性

8 Commitment Schemes from Sigma-protocols

假设有生成器$G$，关于困难关系$R$的$\Sigma$协议$\mathcal P$，假设检查成员关系很简单（给定$x$，很容易判断是否存在$w$，满足$(x,w)\in R$），接下来看一下如何用这些条件构建一个完美隐藏的承诺方案

• $Setup$：$V$本地运行$G(1^k)$，得到$(x',w')\in R$，向$P$发送$x$，$P$可以检查是否有$x\in L_R$
• $Commit$：承诺一个$t$比特的串$e$，$P$先以输入$x,e$来运行模拟器$M$，得到输出$(a,e,z)$并将$a$发送给$V$
• $Open：P$向$V$发送$e,z$来揭示承诺

这里有个定理

• Theorem 4：上述承诺方案是完美隐藏且计算绑定的

证明如下

• Proof：对于隐藏性而言，$P$的第一条消息是独立于挑战$e$的，由于$x\in L_R$且$\Sigma$协议的模拟是完美的，因此模拟器生成的$a$与$e$无关

对于绑定性而言，如果$P^*$可以高效的输出$a$，并且这个$a$可以揭示为两个不同的承诺$(e,z),(e',z'),e\neq e'$，则意味着在协议$\mathcal P$中我们会同时接受$(a,e,z)$和$(a,e',z')$，从而意味着我们可以高效计算$w$，与$R$是困难关系矛盾，因此绑定性成立

9 Non-interactive Sigma-protocols and signatures usingrandom oracles

考虑一种情况，所有的参与方都可以访问一个Random Oracle $\mathcal R:\{0,1\}^l\rarr \{0,1\}^t$，则任意参与方都可以将长度为$l$的串$a$发送给RO并得到返回值$\mathcal R(a)$，由于$\mathcal R$是真随机的，因此$\mathcal R(a)$是独立于$a$的长度为$t$的真随机串，此外，RO的特性使得对于$b\neq a$而言，得到$\mathcal R(a)$并不能对猜测$\mathcal R(b)$提供优势

但是$\mathcal R$是固定的，意味着相同的请求结果会得到相同的返回值

如果Prover向RO发送一条消息$a$并将返回结果作为协议$\mathcal P$中Verifier的随机挑战，此时Prover无需与Verifier进行交互，该过程Prover可以得到交互脚本$(a,e,z)$，Prover可以向Verifier发送$(a,z)$，Verifier向RO请求$a$并得到返回结果后，利用$z$可以完成对Prover的验证

考虑一下上述情况中恶意的Prover是否可以作弊，注意到Prover在没有调用RO的情况下无法获得RO对$a$的响应，因此在发送$a$之前Prover无法获得关于$e$的信息，此外利用RO还可以消除恶意的Verifier的影响（也即强制Verifier是诚实的），因为RO的值在$t$上是一致均匀分布的（和诚实的Verifier相同），由于$\Sigma$协议是HVZK的，因此$\Sigma$协议在RO模型下满足零知识性

对于这个协议的零知识性而言，模拟器可以决定RO的响应是什么（前提是与真实协议执行具有相同的分布），因此可以随机选择$e$，运行模拟器并得到$(a,e,z)$，并将RO对$a$的响应定义为$e$，此时输出$(a,z)$即可

这种类型的构造也可以用于从$\Sigma$协议生成安全签名方案：为了生成密钥，我们在困难关系中生成$(x,w)$，令公钥$PK=x$，私钥$SK=w$，为了对消息$m$签名，签名者以Prover身份运行$\Sigma$协议，计算第一条消息$a$，然后将$(a,m)$作为RO的请求，得到响应$e$作为挑战，然后利用$w$计算出$z$，签名值即为$(a,z)$，不难证明在RO模型下攻破签名方案的困难性与已知$x$计算$w$的困难性相当

但是现实生活中并没有RO，只有Hash函数，Hash函数的单向性和复杂程度使得敌手必须通过输入来决定输出，之后才能基于输出进行合理计算，但是RO无法与Hash函数等价，因为Hash函数是固定且已知的，换言之，无法证明某些具体的Hash函数可用于使得$\Sigma$协议以安全的方式非交互的进行，在$\Sigma$协议中利用Hash函数代替RO实际上可行，但是具体安全性及其结果不明

尽管存在这些理论问题，实践中还是会使用Hash函数，因为它确实可以消除交互，此外还因为RO模型允许以比其他已知更高的效率构造安全签名和加密方案

另外还有一点，对使用Hash函数作为子程序的实际协议的大多数攻击实际上会将Hash函数视为一个Random Oracle，也即将其视为输出随机值的黑盒

总结

这篇paper主要介绍了Sigma协议及其两种构造方式

最重要的一点是，Sigma协议是HVZK的，不过也足够了，因为可以利用FS启发式将协议变为非交互式的，不存在交互的话也就不存在恶意的Verifier的问题了，不过这会将安全性引导Random Oracle中，当然就是另一个问题了

此外还有OR的构造方式可以做到WI，除非关系中确实只有一个witness（比如图只有一中三染色方案），否则Verifier无法区分具体使用的是哪个witness来完成的证明，后续也展示了一个简单的用OR构造来完成身份验证的方案

后记

这篇paper同时讲了很多内容，除了Sigma协议以外还讲了相关的包括签名方案、利用RO模型转换为非交互式，感觉以前都没学明白

Ivan Damgard教授这篇paper讲的比较透彻，也是认真读了两天，似乎对自己的签名方案有些眉目了，不过还是需要再看一些文章，尤其是关于签名方案的

References

$[1]$ I. Damgard. On Σ-protocols, 2004. Lecture on Cryptologic Protocol Theory; Faculty of Science,University of Aarhus.

$[2]$ M. Bellare and P. Rogaway: Random Oracles are Practical, Proc. of ACM CCS conference, 1993.