密码学学习笔记——Sigma Protocol

Effective relation 指的是一组二元关系  其中  为有效的可辨认的有限集合。  中的元素被称作statements。如果  ，则称  为  的witness。

设  是一个effective relation。那么一对  构建在  上的一个Sigma protocol 为：

•  是一个叫做  的交互式协议，其输入为一个witness-statement对

•  是一个叫做  的交互式协议，其输入为一个witness 

•  和  的交互过程为：

• 首先  计算一个承诺(commitment)  ，将其发送给  ；

• 在收到了来自  的消息  后，  在有限的挑战空间  中随机选取一个挑战元素(challenge)，并将其发送给  ；

• 在接收到来自  的挑战  后，  计算出一个反馈(response)  ,将其发送给  ；

• 在收到了来自  的消息  后, 输出accept或者reject。  的输出由statement  和交互中的消息  严格计算得出。

协议的要求是，对于所有的  ，当  与  交互后，  总是输出accept。需要注意的是，为了系统的安全性，挑战空间的大小应该为sup-poly（超过多项式大小）。

Figure 1 Sigma protocol的执行过程

设  是关于关系  的一个Sigma协议。如果醉在一个高效的确定性的算法 （称作一个witness extractor）使得：给定一个statement  ，以及两个关于  被accepted的conversation  和  ，并且  ，  能够输出  使得（i.e.，  是  的witness）则我们称  提供 knowledge soundness。

设  是关于关系  的一个Sigma协议，且挑战空间为  。如果存在一个高效的概率性算法  （称作simulator），其输入为  且满足：

1. 对于所有的输入 ，  能够输出一对  使得 对于  是一个被accpeted的conversation。

2. 对于全体，我们计算。

使得 的分布同  和  之间conversation的分布相同，则我们称  是special HVZK。Special的原因在于：1）  需要  作为额外输出；2）就算  的witness不存在，也可以输出一个被accepted的conversation。

设  是一个阶为素数  的循环群，其生成元为  。设证明人  保存私钥  ，对应的公钥匙为  。  需要向  证明其拥有  。这里  是witness，  是statement。Shnorr's identification protocol的协议过程为：

• 密钥生成算法产生公私钥：。其中验证密钥  ，私钥为  。

• 使用 初始化，  使用 初始化， 和  之间的交互过程为：

1.  计算  ，并将  发送给  ；

2.  计算  ，并将  发送给  ；

3.  计算  ，并将  发送给  ；

4.  检查如果  输出accept，否则输出reject。

Figure 2: Schnorr’s identification protocol 过程

Schnorr‘s protocol 的安全性是构建在离散对数问题上的，其证明的方式为假设攻击者在不知道  可以构建对于一个  合法的conversations，那么我们就可以利用攻击者的能力来解决离散对数问题。由于逆否命题是等价，如果离散对数问题无法攻破，那么Schorr's protocol 就是安全的。

proof：假设攻击者对于  可以产生两个被accepted的conversation  和  其中  ，则有  以及  ，两式相除的  ，其中  ,  。由于  ，且群  是素阶循环群，因此  ，则有  ，则我们的到了离散对数问题  的解  。 

证明HVZK在于如何构建一个产生conversation并被verifier接受的  ，且  产的conversation中元素的分布和正常  交互产生的conversation中元素的概率分布相同。设  ，则  计算：

在真实的交互过程中，  和 分别在挑战空间  和  中服从均匀分布，且  相互独立。此外  是由  唯一确定的，因此可以明显看出，  产生的conversation中元素的概率分布同正常交互所产的conversation中元素的概率分布相同。

由Knowledge soundness 的定义以及Schnorr's protocol的安全性分析可知，Schnorr's protocol满足Knowledge soundness。

设  是一个阶为素数  的循环群，其生成元为 。  是群中任意一个元素。Okamoto’s protocol中的关系为：

协议的过程为：

Figure 3：Okamoto’s protocol 过程

其中  。

The Chaum-Pedersen protocol 是基于DH-triples的。设  是一个阶为素数  的循环群，其生成元为 。对于  ，如果  我们就说  是一个DH-triples。等价的，如果 是一个DH-tripes，当且仅当存在一个  使得  ,  。在Chaum-Pedersen protocol 的关系为：

协议的过程为：

Figure 4: The Chaum-Pedersen protocol 过程

其中  。

上述the Schnorr, Okamoto, and Chaum- Pedersen protocols都是一种更加一般的Sigma protocol的特例。这种更加一般的Sigma protocol是要证明元素之间的线性关系。设  是一个阶为素数  的循环群，其生成元为  。我们考虑一个布尔函数  ：

在函数  中，  。这些群元素一部分可以是系统参数甚至是常量，另一些元素是针对函数的特殊变量。  是函数  的入参，当函数中的所有等式成立则  返回true。对于这样函数的一个特定的类  ，我们可以定义一个关系：

在  中，一个函数  是statement，而一个是这个函数  为true的  是这个函数  的witness。而我们称这样的协议为linear protocols的原因在于如果我们对函数  中的等式取对数可以得到：

对于一般linear Sigma protocol的过程为：

Figure 5: 一般的linear protocol

• Schnorr‘s protocol 中  .

• Okamoto's protocol 中 

• The Chaum-Pedersen protocol中 

对于一般的linear protocol是一个关于关系  的Sigma函数并且满足knowledge soundness以及special HVZK。

我们可以利用群同态来更加清晰高效的来描述到目前为止的介绍的所有Sigma协议。设 是两个不知道阶的交换群，以及一个同态映射  。为了表达的方便， 群中的运算为群加法， 群中的运算为群乘法。设  ，证明者需要向验证着证明他知道在映射 下  的原象。在这种Sigma protocol中，关系为：

其中  是映射  对于  的原象。协议的过程如下：

Figure 6：基于同态映射的Sigma protocol过程

在  最小素因子至少为  的情况下，基于同态映射的Sigma protocol满足knowledge soundness以及special HVZK。

• Okamoto’s protocol 中 

• The Chaum-Pedersen protocol中 

• 一般linear protocol中 

封面图片来自 Unsplash， 作者 Leon Skibitzki 

长按二维码添加微信进群技术讨论

info@secbit.io

安比（SECBIT）实验室