密码学学习笔记——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中的关系为：

协议的过程为：