【密码学】哈希零知识证明系统原理

AI摘要：

该文介绍了基于哈希的零知识证明系统，其中涉及四元语言系统(X, L, W, RL)。通过密钥生成算法Gen、私有求值算法Priv和公开求值算法Pub，构建了非交互式的哈希零知识证明系统。文章详细阐述了哈希函数的投射性和均匀性，以及构造基于DDH假设的universal HPS的简单实例。通过该系统，证明者可以证明某实例满足特定特征，而验证者可以验证证明的有效性，实现了零知识性、完备性、高效性等特性。然后，文章介绍了哈希证明系统的局限性，目前主要用于证明群中的子群成员归属问题。最后，作者参考学习了知乎文章，并附上了相关例子图片。

  在基于哈希的零知识证明系统中，涉及到一个四元语言系统$(X,L,W,R_L)$。其中$X$为实例集合，抽象表示包含所有待证明的示例。$W$是证据集合，其中的元素通过二元关系$R_L$用以表征实例集合X中的具有一定特征的某些实例，这些实例构成$X$中的一个真子集$L$。即：$L\subsetneq X,x \in L \Leftrightarrow \exists w \in W, (x,w)\in R_L$。

  其中需要通过零知识证明的，就是我们拥有某个给出的实例$x \in L$的证据w，因此进一步引入哈希证明系统的三个算法Gen、Priv和Pub，用以给出零知识证明。

  其中Gen为密钥生成算法，能够生成一对密钥$(pk,sk)$，$sk$和$pk$之间存在多对一的映射关系$(\alpha (sk)=pk)$，每个$sk$都定义了一个哈希函数$H_{sk} :X \rightarrow \Pi $，将实例空间$X$上的某个实例映射到零知识证明使用的证明空间$\Pi $。Priv为私有求值算法，能通过$sk$高效计算任意实例$x$的哈希值$H_{sk} (x)$。$H_{sk} (x)=Priv(x,sk), x \in X$。Pub为公开求值算法，利用该算法可以在没有$sk$的情况下，根据$pk$和拥有的证据$w$高效计算满足二元关系$R_L $的实例$x$的哈希值$H_{sk} (x)$。$H_{sk} (x)=Pub(x, w, pk), x \in L$。哈希函数$H_{sk} $在$X$上具有唯一性和均匀性。投射性指当实例元素满足二元关系$R_L $时，任意$sk$都投射到唯一的一个可由公钥和证据确定的哈希值上，即：$\forall x \in L, H_{sk} (x)=Pub(x, w, pk)=Pub(x, w, \alpha (sk))=Priv(x,sk)$。均匀性指当实例元素不满足二元关系时，其哈希值根据$sk$值的不同，在证明空间上均匀分布，即$\forall x \in X, x \notin L, H_{sk} (x)$在$\Pi $上均匀分布。

  利用以上内容我们就可以构建一个非交互式的哈希零知识证明系统。首先由可信第三方通过秘钥生成算法生成一对$(pk,sk)$，将$pk$作为公共参考串，$sk$作为陷门发送给验证者。证明者利用公开的公开求值算法以及$x$和$pk$，再私密输入仅自己知道的证据$w$可以计算得到对应该$x$的唯一哈希值。验证者可以利用私有求值算法，根据$sk$, $x$快速计算哈希值，并与证明者提供的哈希值比对进行验证。比对哈希值一致则可以验证证明者拥有证据$w$，且证明过程无需泄露该证据。验证过程中证明者和验证者无需交互，同时，因为只有拥有$sk$才有能力进行验证，所以该证明系统是可指定验证者的。

$$ Gen(\lambda ) \rightarrow (pk, sk) $$

$$ Prover(x, w) \stackrel{H_{sk} (x)=Pub(x, w, pk)}{\longrightarrow} Verifier(sk,x) ：H_{sk} (x) \stackrel{?}{=} Prive(x, sk) $$

  哈希函数的投射性保证了证明者的正确计算结果一定能通过验证者正确计算的验证，具有完备性；哈希函数的均匀性抵抗了证明者的强大计算能力，使通过暴力计算得到正确哈希值的概率可以忽略不计，同时验证者拥有的一个私钥陷门与实例无关，验证者无法据此判断实例是否满足二元关系，具有合理性和健壮性；证明系统中验证者和证明者在得到相应信息时计算对应哈希值的过程是高效的，具有高效性；证明过程中验证者和证明者均独立计算，未泄露任何私密信息，具有零知识性。该证明系统的局限在于表达能力有限, 目前仅能用于证明群中的子群成员归属问题, 尚未知能否延伸到任意的NP语言。

  一个基于DDH假设的universal HPS, 也称为Cramer-Shoup Lite HPS的简单具体构造实例：

  注：本文参考学习知乎文章《浅谈哈希证明系统》，阅读转写而成，文末例子图片亦借用自该文章。