区块链^[1]是一种去中心化的分布式账本技术，具有不可篡改、去中心化和公开透明等特点. 随着区块链技术的应用与发展，数字身份和交易数据的重要性日益增加，同时也带来了更多隐私泄露的风险. 环签名概念最初由Rivest等人^[2]提出，它允许一个实体代表一个潜在的签名者群体（称为环）签署消息，同时在环中保持匿名性. 与群签名相比，环签名被认为是简化的群签名^[3]. 环签名不需要群管理员和其他环成员的合作或批准，可以实现自组织的匿名认证. 环签名在区块链隐私保护、匿名凭证、车辆自组织网络等方面都有许多应用. 门罗币^[4]使用了可链接环签名^[5]技术实现了交易方身份隐私保护. Bünz等人^[6]结合了环签名技术，提出了一种基于账户模型的区块链隐私保护方案Zether.

然而，文献[2-6]的方案基于公钥基础设施体系（public key infrastructure, PKI），用户公钥需要由可信证书颁发机构（certificate authority, CA）签署的证书进行认证. 在该体系中，证书的管理包括证书的吊销、存储、分发和验证，代价是较高的. 为解决该问题，Adi^[7]在1984年提出了基于身份的公钥密码学（identity-based public key cryptography, ID-PKC）. ID-PKC允许用户公钥是任何能够唯一标识用户的字符串（例如电子邮件地址），从而消除了证书的需要. 同时，引入了一个完全可信的密钥生成中心，根据用户的身份标识生成并发放用户私钥. 已有科研人员提出了基于身份的数字签名方案^[8-10].

SM9数字签名算法^[11]是由中国国家密码管理局于2016年发布，并于2018年纳入国际标准的基于身份的密码算法. SM9数字签名算法采用了非对称双线性对技术，具有可证明的安全性和高效性^[12]，适用于各种需要身份认证和通信安全的场景，例如区块链、电子现金、电子投票等. 随着区块链系统国产化的应用需求不断增加，现有的国密算法已不能满足日益复杂的区块链应用需求. 已有科研人员提出了基于SM9标识密码算法的功能型密码算法^[13-15]. 彭聪等人^[16]提出了一种基于SM9标识密码算法的环签名方案. 然而，现有方案的计算开销和通信开销均随着环成员数量的增加而增加.

本文的主要贡献有3个方面：

1） 提出了一种基于SM9数字签名的常数级大小环签名方案，并基于该环签名算法设计了一种区块链隐私保护方案；

2） 在随机谕言机模型下证明了本文方案满足不可伪造性和匿名性；

3） 分析了本文方案的计算开销和通信开销，并与现有的方案做对比，实验分析结果表明本文方案实现了环签名大小不随环用户数量变化的需求，因而具有更高的实用性.

1.   国内外相关工作

Rivest等人^[2]提出的环签名方案是基于RSA加密算法的. Abe等人^[17]提出了基于离散对数问题的环签名方案. Wong等人^[18]利用Reed-Solomon码的擦除校正技术和多项式插值之间的等价性提出了一种环签名方案. 为了抵抗量子计算机的攻击，Wang等人^[19]提出了一种基于多变量的环签名方案，随后他们又利用基于格的无陷门签名方案^[20]提出了一种基于格的环签名方案^[21]. 为了减少签名大小，Dodis等人^[22]利用基于单向域的累加器提出了首个常数级大小的环签名方案，且该方案所有身份验证的时间都与环成员数量无关.

Zhang等人^[23]提出了基于双线性对的基于身份的环签名方案. Herranz等人^[24]提出了一种基于身份的环签名方案，并将他们的方案扩展到匿名子集场景. Awasthi等人^[25]提出了一种基于身份的环签名方案和代理环签名方案. Nguyen^[26]提出了一个基于双线性对的动态累加器方案，并基于此构建了一个具有常数级签名大小的基于身份环签名方案. Chow等人^[27]提出了高效的基于身份的环签名方案，对于任意环成员数量仅需要2个双线性对计算，并在随机谕言机模型下证明对自适应选择的消息和身份攻击具有存在性不可伪造. 包嘉斌^[28]提出了基于SM9标识密码算法的环签密方案. 邓浩明等人^[29]提出了基于SM9标识密码算法的门限环签名方案.

2.   预备知识

本节给出了符号约定、双线性对、数学困难问题、SM9数字签名算法、知识签名和动态累加器的概念.

2.1   符号约定

本文使用$\lambda$表示安全参数，$\epsilon （\cdot ）$表示可忽略函数，PPT表示概率多项式时间，$p$和$N$为大素数，$\mathbb{Z}_N^*$=$\{ 1,2,…,N \}$，${F_p}$是阶为$p$的有限域，$E({F_p})$表示以${F_p}$为基域的椭圆曲线，$k \cdot P$表示椭圆曲线上点$P$的$k$倍点，KGC表示密钥生成中心，ID表示用户身份标识.

2.2   双线性对

令${\mathbb{G}_1}$是由${P_1}$作为生成元的N阶加法循环群，${\mathbb{G}_2}$是由${P_2}$作为生成元的N阶加法循环群，${\mathbb{G}_T}$是阶为N的乘法循环群，双线性对是满足下列性质的一个映射$e:{\mathbb{G}_1} \times {\mathbb{G}_2} \to {\mathbb{G}_T}$.

1） 双线性. 对于任意的$U \in {\mathbb{G}_1}$,$V \in {\mathbb{G}_2}$和$a,b \in \mathbb{Z}_N^*$，都有$e(a \cdot U,b \cdot V) = e{(U,V)^{a \cdot b}}$.

2） 非退化性. 存在$a,b \in \mathbb{Z}_N^*$，使得$e(U,V) \ne 1$.

3） 可计算性. 对于所有$U \in {\mathbb{G}_1}$,$V \in {\mathbb{G}_2}$，存在多项式时间算法有效计算$e(U,V)$.

2.3   数学困难问题

定义1. q-SDH问题（q-strong Diffie-Hellman problem, q-SDH）. 对于$U \in {\mathbb{G}_1}$，$V \in {\mathbb{G}_2}$，未知的$a \in \mathbb{Z}_N^*$，给定$U,V,a \cdot V,{a^2} \cdot V,…,{a^q} \cdot V$，PPT敌手输出$(c,{(a + c)^{ - 1}})$，其中$c \in \mathbb{Z}_N^*$.

定义2. 离散对数问题（discrete logarithm problem, DLP）. 对于$U \in {\mathbb{G}_1}$，未知的$a \in \mathbb{Z}_N^*$，给定$W = a \cdot U$，PPT敌手输出$a$.

2.4   SM9数字签名算法

SM9数字签名算法包括4个算法，分别是系统初始化算法、密钥提取算法、签名算法和签名验证算法.

1） 系统初始化算法. 输入安全参数$\lambda$，选取特定曲线生成参数$t$，构建椭圆曲线基域${F_p}$，构建$E({F_p})$上的双线性对$e:{\mathbb{G}_1} \times {\mathbb{G}_2} \to {\mathbb{G}_T}$，选择哈希函数${H_1}( \cdot ), {H_2}( \cdot ):{\{ 0,1\} ^*} \to \mathbb{Z}_N^*$. KGC随机选取$d \in \mathbb{Z}_N^*$作为签名主密钥$msk$，并计算主公钥${P_{{\text{pub}}}} = d \cdot {P_2}$. 最后，输出系统参数$Params = \{ e,{\mathbb{G}_1},{\mathbb{G}_2},{\mathbb{G}_T},{P_1},{P_2},{P_{{\text{pub}}}},{H_1},{H_2}\}$作为以下算法的默认输入.

2） 密钥提取算法. 给定用户$A$的身份标识$I{D_A}$，为产生用户$A$的签名私钥$d_{ID}^A$，KGC计算$d_{ID}^A = d \cdot {({H_1}(I{D_A}) }+ {d)^{ - 1}} \cdot {P_1}$，输出用户$A$的私钥$d_{ID}^A$.

3） 签名算法. 给定用户$A$的私钥$d_{ID}^A$，消息$m$和主公钥${P_{{\rm{pub}}}}$，随机选取$r \in \mathbb{Z}_N^*$，计算${\sigma _1} = {H_2}(m\parallel e{({P_1}, {P_{{\text{pub}}}})^r})$,${\sigma _2} = (r - {\sigma _1})d_{ID}^A$，输出签名值$\sigma = ({\sigma _1},{\sigma _2})$.

4） 签名验证算法. 给定主公钥${P_{{\text{pub}}}}$，用户$A$的身份标识$I{D_A}$，消息$m$和签名值$\sigma$，验证者计算$P = {H_1}(I{D_A}) \cdot {P_2} + {P_{{\text{pub}}}}$，验证${\sigma _1} = {H_2}(m\parallel e({\sigma _2},P) \cdot e{({P_1},{P_{{\text{pub}}}})^{{\sigma _1}}})$是否成立，若成立，则$\sigma$为合法签名，否则签名无效.

2.5   知识签名

知识签名（signatures of knowledge, SoK）是一种证明系统，证明者可以证明知道某个论断而不泄露对应的证据，它可以用于构造数字签名方案来提供认证性、完整性和不可否认性. 例如，$SoK\{ (x)\left| {X = x \cdot {P_1}} \right.\} (m)$表示证明者拥有知识$x$满足关系$X = x \cdot {P_1}$，且不泄露$x$的真实值，并对消息$m$进行签名. 知识签名需要满足正确性、可靠性、零知识性和存在性不可伪造，它包含3个算法：

1） 密钥生成. 输入安全参数$\lambda$，输出系统公开参数$Params$.

2） 证明. 输入系统公开参数$Params$，消息$m$和关系$(x,X) \in R$，输出知识签名$\pi$.

3） 验证. 给定消息$m$和知识签名$\pi$，输出accept，表明证明有效；反之，则证明无效.

2.6   动态累加器

动态累加器可以让用户证明一个元素属于一个集合，而不用透露集合中的单个成员. 它可以用于匿名凭证、群签名和环签名等应用场景，可以实时地对集合状态进行更新，同时存储和计算规模不会随着元素数量的增加而受到影响. 本文结合了Nguyen^[26]提出的动态累加器方案，包含以下4个算法：

1） 累加器初始化算法. 按照2.2节定义双线性对$e: {\mathbb{G}_1} \times {\mathbb{G}_2} \to {\mathbb{G}_T}$，随机选择$s \in \mathbb{Z}_N^*$，$L = \{ {P_1},s \cdot {P_1},s^2 \cdot {P_1},…, {s^q} \cdot {P_1}\}$，其中$q$是可以被累加器累加的最大上限值. 创建动态累加器实例，随机选择$u \in \mathbb{Z}_N^*$，累加器值初始化为${V_0} = u \cdot {P_1}$.

2） 累加器评估算法. 给定累加器值${V_0}$和集合$X = \{ {x_1},…,{x_k}\} \subset \mathbb{Z}_N^*\backslash \{ - d\}$,$k \leqslant q$，累加器值$\displaystyle \prod\limits_{i = 1}^k ({x_i} + d) {V_0}$可以通过元组$L$在不知道$s$的情况下计算.

3） 累加器成员增加算法. 增加成员$x' \notin X$，更新累加器值为$V' = (x' + d)V$，并更新证据$W' = V + (x' - x)W$.

4） 累加器成员删除算法. 删除成员$x' \in X$，更新累加器值为$V' = {(x' + d)^{ - 1}}V$，并更新证据$W' = {(x' - x)^{ - 1}}(W - V')$.

3.   基于SM9签名的环签名方案

本节介绍了如图1所示的基于身份环签名的系统模型和安全模型，并提出了基于SM9数字签名的常数级大小环签名方案.

图  1  基于身份的环签名模型

Figure  1.  Identity-based ring signature model

下载: 全尺寸图片 幻灯片

3.1   系统模型

基于身份的环签名包含3种角色：KGC、签名者和验证者. 其中可信的KGC负责初始化系统公开参数，并为用户生成对应其身份标识的私钥. 基于身份的环签名包含4个算法：

1） 系统初始化算法Setup$(\lambda )$. 由KGC执行，输入安全参数$\lambda$，输出系统公开参数$Params$和KGC的主密钥$msk$.

2） 密钥提取算法$Extract(ID,msk)$. 由KGC执行，输入用户身份标识$ID$和KGC主密钥$msk$，输出用户私钥${d_{ID}}$.

3） 环签名算法$RS ign(m,{Y_n},{d_{ID}})$. 由签名者执行，输入消息$m$，环用户标识集合${Y_n} = \{ I{D_1},I{D_2},…,I{D_n}\}$，用户私钥${d_{ID}}$，输出环签名值$\sigma$.

4） 签名验证算法${R V e ri f y}(m,\sigma ,{Y_n})$. 由验证者执行，输入消息$m$，签名$\sigma$，环用户集合${Y_n} = \{ I{D_1},I{D_2},…,I{D_n}\}$，输出accept/reject.

正确性. 对于环签名算法生成的签名，能够通过验证算法，即满足等式：

3.2   安全模型

基于身份的环签名需要满足：1） 在自适应选择消息和身份攻击下的存在性不可伪造（existential unforgeability under adaptive chosen-message-and-identity attack, EUF-CMIA）；2） 匿名性.

定义3. EUF-CMIA. 使用模拟器${{\mathcal{S}}}$与敌手${{\mathcal{A}}}$之间的游戏来定义该性质.

1） 系统初始化. ${{\mathcal{S}}}$调用Setup$(\lambda )$生成系统参数$Params$和KGC的主公私钥对$({P_{{\text{pub}}}},msk)$. ${{\mathcal{S}}}$将$Params$和${P_{{\text{pub}}}}$发送给敌手${{\mathcal{A}}}$.

2） 询问阶段. ${{\mathcal{A}}}$以自适应的方式进行3个查询：

①哈希谕言机查询. ${{\mathcal{A}}}$询问任意输入的哈希值.

②密钥提取查询. ${{\mathcal{A}}}$询问身份标识$ID$，${{\mathcal{S}}}$返回对 应的私钥.

③签名查询. ${{\mathcal{A}}}$询问环用户集合${Y_n} =\left \{ I{D_1},I{D_2},…, \right.$ $\left. I{D_n} \right\}$和一个消息$m$，${{\mathcal{S}}}$返回对应的签名$\sigma$.

3） 伪造阶段. ${{\mathcal{A}}}$伪造挑战用户集合$Y_n^* = \{ ID_1^*,ID_2^*,…, ID_n^*\}$对消息${m^*}$的签名${\sigma ^*}$，${{\mathcal{A}}}$从未询问过$Y_n^*$对消息${m^*}$的签名，且从未询问过$Y_n^*$中任何一个用户的私钥，伪造的签名值${\sigma ^*}$可以通过验证算法，则敌手${{\mathcal{A}}}$赢得游戏.

定义敌手${{\mathcal{A}}}$赢得EUF-CMIA游戏的优势为$Adv_\mathcal{A}^{{\rm{EUF}}} = Pr[RVerify({m^*},{\sigma ^*},Y_n^*) = {\text{accept}}]$. 如果该优势可忽略，则称该方案是EUF-CMIA安全的.

定义4. 匿名性. 使用模拟器${{\mathcal{S}}}$与敌手${{\mathcal{A}}}$之间的游戏来定义该性质.

1） 系统初始化. ${{\mathcal{S}}}$调用Setup$(\lambda )$生成系统参数$Params$和KGC的主公私钥对$({P_{{\text{pub}}}},msk)$. ${{\mathcal{S}}}$将$Params$和${P_{{\text{pub}}}}$发送给${{\mathcal{A}}}$.

2） 询问阶段. ${{\mathcal{A}}}$以自适应的方式进行3个查询：

①哈希谕言机查询. ${{\mathcal{A}}}$询问任意输入的哈希值.

②密钥提取查询. ${{\mathcal{A}}}$询问身份标识$ID$，${{\mathcal{S}}}$返回对 应的私钥.

③签名查询. ${{\mathcal{A}}}$询问环用户集合${Y_n} = \{ I{D_1},I{D_2}, …, I{D_n}\}$ 和一个消息$m$，${{\mathcal{S}}}$返回对应的签名值$\sigma$.

3） 挑战阶段. ${{\mathcal{A}}}$向${{\mathcal{S}}}$提交一个挑战用户集合$Y_n^* = \{ ID_1^*,ID_2^*,…,ID_n^*\}$和2个用户标识$I{D_{{\delta _1}}},I{D_{{\delta _2}}} \in Y_n^*$，${{\mathcal{S}}}$随机选择$b \in \{ 0,1\}$并使用$I{D_{{\delta _b}}}$的私钥对消息${m^*}$进行环签名，将签名值${\sigma ^*}$发送给${{\mathcal{A}}}$.

4） 猜测阶段. ${{\mathcal{A}}}$输出一个${b'} \in \{ 0,1\}$，如果${b'} = b$，${{\mathcal{A}}}$赢得游戏.

定义敌手${{\mathcal{A}}}$赢得游戏的优势为$Adv_\mathcal{A}^{{\rm{ANO}}} = Pr[{b'} = b]$. 如果该优势可忽略，则称该方案满足匿名性.

3.3   方案设计

1） 系统初始化算法Setup. 由KGC运行，输入安全参数λ，输出系统公开参数$Params$和KGC的主密钥$msk$. 参数选取同国密标准SM9数字签名算法.

①选取${G_1},{G_2},{G_3} \in {\mathbb{G}_1}$.

②产生随机数$d \in \mathbb{Z}_N^*$作为主密钥$msk$，并计算主 公钥${P_{{\text{pub}}}} = d \cdot {P_2}$.

③创建动态累加器实例，随机选择$u \in \mathbb{Z}_N^*$，累加 器值初始化为${V_0} = u \cdot {P_1}$.

④随机选择$s \in \mathbb{Z}_N^*$，计算${S_{{\text{pub}}}} = s \cdot {P_2}$，$L = \left\{ {P_1},s \cdot {P_1}, \right.$ $\left. s^2 \cdot {P_1},…,{s^q} \cdot {P_1}\right\}$，其中$q$是可以被累加器累加的最 大上限值.

⑤公共参数为$Params = \left\{ \lambda ,{G_1},{G_2},{G_3},{P_1},{P_2},{P_{{\text{pub}}}},\right.$ $\left.{S_{{\text{pub}}}}, {V_0},L,{H_1},{H_2}\right\}$，作为下面算法的默认输入.

2） 密钥提取算法$Extract$. 由KGC运行，输入用户$A$的身份标识$I{D_A}$，KGC主密钥$msk$，输出用户$A$（签名者）的私钥$d_{ID}^A$.

KGC计算用户$A$的私钥$d_{ID}^A = d \cdot {({H_1}(I{D_A}) + d)^{ - 1}} \cdot {P_1}$并发送给用户$A$.

3） 环签名算法$RS ign$. 由用户$A$运行，输入用户$A$的私钥$d_{ID}^A$，$n$个成员标识组成的环用户集合${Y_n} = \{ I{D_1},I{D_2},…,I{D_n}\}$，待签名消息$m$，输出环签名值$\sigma$.

①对于$i \in [1,n]$，计算${x_i} = {H_1}(I{D_i})$，设${x_\delta } = {H_1}(I{D_A})$， $1 \leqslant \delta \leqslant n$.

②对集合$X = \{ {x_1},{x_2},…,{x_n}\}$，$n$的最大值为$q - 1$，计算 $V = \displaystyle\prod\limits_{i = 1}^n {({x_i} + s) \cdot {V_0}}$. 注意$V$值的计算不需要知道$s$， 在已知$L$的情况下，$V$可以在多项式时间内被计算.

③计算证据${W_A} = \displaystyle\prod\limits_{i = 1,i \ne \delta }^n {({x_i} + s) \cdot {V_0}}$.

④知识签名由两部分组成，用户$A$的证据${W_A}$证明 ${x_A} = {H_1}(I{D_A})$确实在$V$中、用户$A$的私钥$d_{ID}^A$合法. 非交互式零知识证明

$\pi = S oK\left\{ {\left.\left( \begin{gathered} {x_A}, \\ d_{ID}^A, \\ {W_A} \\\end{gathered} \right) \right| \begin{gathered} e({W_A},{x_A} \cdot {P_2} + {S_{{\text{pub}}}}) = e(V,{P_2}) \wedge \\ e(d_{ID}^A,{x_A} \cdot {P_2} + {P_{{\text{pub}}}}) = e({P_1},{P_{{\text{pub}}}}) \\\end{gathered} } \right\}(m).$ 具体展开为：

选取随机值${r_1},{r_2},{r_3} \in \mathbb{Z}_N^*$，计算

$\pi$等价于${\pi '}$

选取随机值${k_1},{k_2},…,{k_7} \in \mathbb{Z}_N^*$，计算

⑤输出消息$m$的签名值$\sigma =\left (ch,{s_1},…,{s_7},{A_1},…,{A_3}, \right.$ $\left.{T_1},…,{T_4},V\right)$.

4） 签名验证算法$RVerify$. 由验证者运行，输入消息$m$，签名值$\sigma = (ch,{s_1},…,{s_7},{A_1},…, {A_3}, {T_1},…,{T_4},V)$，环用户标识集合${Y_n} = \{ I{D_1},I{D_2},…,I{D_n}\}$，输出accept/reject.

验证等式：

若等式成立，则签名有效，返回accept；否则，签名无效，返回reject.

4.   正确性和安全性分析

4.1   正确性分析

4.2   安全性分析

本节将给出基于SM9数字签名的环签名方案的安全性证明. 假设KGC是可信的，仅考虑恶意用户作为敌手. 假设q-SDH问题是困难的，本文使用的累加器方案满足抗碰撞性，其中$q$是累加器要累加元素的上限，文献[26]中给出了具体的证明，本文不再赘述.

定理1. 在随机谕言机模型下，假设群${{G}_1}$上的离散对数问题是困难的，本文方案中的知识签名$\pi$满足完备性、可靠性和零知识性.

证明.完备性可由4.1节得证. 本节只证明可靠性和零知识性.

1）可靠性. 假设群${{\mathbb{G}}_1}$上的离散对数问题是困难的，如果协议以可忽略的概率通过验证，PPT的证明者必须具有${x_A},d_{ID}^A,{W_A}$的知识. 假设协议接受具有相同的承诺$({A_1},…,{A_3},{T_1},…,{T_4})$和2个不同的挑战和响应对$(ch,{s_1},{s_2},…,{s_7})$和$(c{h'},s_1',s_2',…,s_7')$.

令${t_i} = ({s_i} - s_i'){(c{h_i} - ch_i')^{ - 1}}$，$i = 1,2,…,7$，则

根据式(1)(2)，证明者具有$o = ({t_4} - {t_7}{t_1}){G_1} + ({t_5} - {t_7}{t_2}){G_2} + ({t_6} - {t_7}{t_3}){G_3} \in {{\mathbb{G}}_1}$. 在${{\mathbb{G}}_1}$的离散对数假设下，意味着${t_4} = {t_7}{t_1}$，${t_5} = {t_7}{t_2}$. 令${x_A} = {t_7}$，${W_A} = {A_2} - {t_1}{G_2}$，$d_{ID}^A = {A_3} - {t_2}{G_3}$，则$e({W_A},{x_A} \cdot {P_2} + {S_{{\text{pub}}}}) = e(V,{P_2})$，$e(d_{ID}^A,{x_A} \cdot {P_2} + {P_{{\text{pub}}}}) = e({P_1},{P_{{\text{pub}}}})$. 因此，证明者具有满足这些关系的知识${x_A},d_{ID}^A,{W_A}$.

2）零知识性. 模拟器${{\mathcal{S}}}$随机选择$ch,{s_1},{s_2},…, {s_7} \in \mathbb{Z}_N^*$，${A_1},{A_2},{A_3} \in {{\mathbb{G}}_1}$，并计算

可以得到模拟的分布与真实记录的分布相同. 证毕.

定理2. 在随机谕言机模型下，假设q-SDH问题是困难的，累加器方案满足抗碰撞性，知识签名$\pi$满足零知识性，我们的基于SM9签名的环签名方案满足匿名性.

定理3. 在随机谕言机模型下，假设q-SDH问题是困难的，累加器方案满足抗碰撞性，知识签名$\pi$满足可靠性，我们的基于SM9签名的环签名方案是EUF-CMIA安全的.

证明.由于本文方案是基于非交互式零知识证明构造的知识签名方案，定理2和定理3可以很容易地从定理1的结论中得出，故省略. 证毕.

5.   基于环签名的区块链隐私保护方案

本文对Hyperledger Fabric联盟链结构进行修改，利用提出的环签名方案，设计了一种区块链隐私保护方案. 用户通过使用该环签名签署交易提案，实现了交易发起方的身份隐私保护. 交易核心过程如图2所示.

图  2  基于环签名的区块链交易流程

Figure  2.  Blockchain transaction process based on ring signature

下载: 全尺寸图片 幻灯片

该区块链隐私保护方案包含3个实体，即KGC、用户、区块链节点，其中区块链节点可以分为背书节点、排序节点和记账节点. 本文方案使用KGC替换了Fabric框架中的CA模块，避免了PKI体系带来的证书管理问题，在本文方案中KGC是可信的. 具体核心交易流程描述如下：

⓪ 由KGC执行Setup算法，完成系统初始化.

①用户向KGC提交自己的身份标识ID以请求用户密钥.

②KGC执行Extract算法，生成用户的私钥${d_{ID}}$并发送给用户.

③用户在发送交易之前，先构造交易提案，随机选取n个成员标识组成的环用户集合${Y_n} = \{ I{D_1},I{D_2},\cdots, I{D_n}\}$，使用RSign算法对交易提案进行签署，并发送给背书节点.

④背书节点首先使用RVerify算法验证交易提案签名，根据背书策略，模拟交易执行，完成交易验证.

⑤背书节点对交易提案进行签名背书，并发送给交易发起方用户.

⑥用户收集到一定数量的背书签名后，发送交易给排序节点.

⑦排序节点对收集到的交易进行排序，构造交易区块.

⑧排序节点广播交易区块给其他节点.

⑨记账节点使用RVerify算法验证交易签名，验证背书签名.

⑩记账节点将确认后的交易区块写入公开账本.

6.   效率分析

本节从计算开销和通信开销两方面对基于身份的环签名方案进行评估，将本文所提出的SM9环签名方案与文献[16]中的基于SM9标识密码算法的环签名方案和文献[27]所提出的基于身份的环签名方案进行了比较.

6.1   计算开销分析

在计算开销方面，主要考虑密钥提取、环签名算法和签名验证算法的计算开销. 本文使用256 b的BN曲线实例化双线性对，使用SHA-256算法实例化哈希函数，省略了耗时很短的哈希运算和加法运算. 首先在电脑端利用Miracl库测试1000次取平均值得到方案所需运算的，其中平台参数为DELL牌电脑，Windows 11操作系统，i7-10700 2.90 GHz处理器和16 GB内存. 为方便起见，表1给出了符号定义和运算耗时结果. 表2分析了3个方案的计算开销.

表  1  符号定义和运行时间

Table  1.  Symbol Definition and Running Time

符号	运算描述	运行时间/ms
$HTP$	Hash To Point	4.95
$P{M}_{ {{\mathbb{G}} }_{1} }$	${\mathbb{G}}_1$中的点乘	1.73
$PM_{{\mathbb{G}}_2 }$	${{\mathbb{G}}_2}$中的点乘	5.19
$E_{{\mathbb{G}}_T }$	${\mathbb{G}}_T$中的取幂	19.07
$BP$	双线性对	62.34
${M}_{ {{\mathbb{G}}}_{T} }$	${\mathbb{G}}_T$中的乘法	0.04
$M{E}_{{\mathbb{Z}}_{N}^{*}}$	$\mathbb{Z}_N^*$中的模幂	0.14
$M{I}_{ {\mathbb{Z} }_{N}^{*} }$	$\mathbb{Z}_N^*$中的模逆	0.05

下载: 导出CSV 

| 显示表格

表  2  环签名方案的计算开销对比

Table  2.  Comparison of Computation Costs for Ring Signature Schemes

方案	密钥提取	签名生成	签名验证
文献[27]方案	$HTP$	$n \times HTP + 2n \times P{M_{ {{\mathbb{G}}_2} } }$	$2BP + n \times P{M_{ {{\mathbb{G}}_2} } }$
文献[16]方案	$P M_{{\mathbb{G}}_{1} }+M{I}_{ {\mathbb{Z} }_{N}^{*} }$	$2n \times P{M_{ {{\mathbb{G}}_1} } } + n\times BP + (n - 1) \times {M_{ {{\mathbb{G}}_T} } }$	$n \times P{M_{ { {\mathbb{G}}_1} } } + n \times BP + n \times {M_{ { {\mathbb{G}}_T} } }$
本文方案	$P M_{{\mathbb{G}}_{1} }+M{I}_{ {\mathbb{Z} }_{N}^{*} }$	$14 P M_{{\mathbb{G}}_{1} }+2 B P+4 M_{{\mathbb{G}}_{T} }+6 M E_{\mathbb{Z}_N^* }$	$9 P{M_{ {{\mathbb{G}}_1} } } + 5 BP + 8 {M_{ {{\mathbb{G}}_T} } } + 10M{E_{\mathbb{Z}_N^*} }$

下载: 导出CSV 

| 显示表格

本文方案的签名生成算法需要计算14个${\mathbb{G}_1}$点乘运算、6个双线性对运算、4个${\mathbb{G}_T}$乘法运算和6个$\mathbb{Z}_N^*$模幂运算，耗时399.3 ms，使用预计算方法提高计算效率后，签名生成计算可以减少4个双线性对运算，仅需耗时149.9 ms. 签名验证算法需要计算9个${\mathbb{G}_1}$点乘运算、10个双线性对运算、8个${\mathbb{G}_T}$乘法运算和10个$\mathbb{Z}_N^*$模幂运算，耗时640.7 ms，使用预计算方法后，签名验证计算可以减少5个双线性对运算，仅需耗时329 ms.

如图3所示，本文方案在签名生成算法的计算开销是常数级别的，当环成员数量为10时，本文方案的计算开销与方案[27]相似.与基于SM9的环签名方案[16]相比，本文方案性能优势更加明显，当环成员数量为10时，本文方案签名生成算法的计算开销仅为方案[16]的22.7%.

图  3  签名生成计算开销对比

Figure  3.  Signature generation computational cost comparison

下载: 全尺寸图片 幻灯片

如图4所示，本文方案在签名验证算法的计算开销也是常数级别的.当环成员数量为10时，本文方案签名验证计算开销大约是方案[27]的2倍，不具有优势；当环成员数量超过40个时，本文方案签名验证计算开销与方案[27]相似.与基于SM9的环签名方案[16]相比，本文方案性能优势明显，当环成员数量为10时，本文方案签名验证计算开销仅为方案[16]的一半.

图  4  签名验证计算开销对比

Figure  4.  Signature verification computational cost comparison

下载: 全尺寸图片 幻灯片

6.2   通信开销分析

在通信开销方面，主要考虑主公钥、用户私钥、和签名的通信开销. 本文使用$\left| {{\mathbb{G}_1}} \right|,\left| {{\mathbb{G}_2}} \right|,\left| {{\mathbb{G}_T}} \right|,\left| {\mathbb{Z}_N^*} \right|$分别表示${\mathbb{G}_1},{\mathbb{G}_2},{\mathbb{G}_T},\mathbb{Z}_N^*$中元素的比特位长. 其中，$\left| {{\mathbb{G}_1}} \right| = 512$ b，$\left| {{\mathbb{G}_2}} \right| = 1\;024$ b，$\left| {{\mathbb{G}_T}} \right| = 3\;072$ b，$\left| {\mathbb{Z}_N^*} \right| = 256$ b. 表3分析了3个方案的通信开销.

表  3  环签名方案的通信开销对比

Table  3.  Comparison of Communication Costs for Ring Signature Schemes b

方案	主公钥	用户私钥	签名
文献[27]方案	$\left| {{\mathbb{G}_2}} \right|$	$\left| {{\mathbb{G}_1}} \right|$	$(n + 1)\left| {{\mathbb{G}_2}} \right|$
文献[16]方案	$\left| {{\mathbb{G}_1}} \right| + \left| {{\mathbb{G}_2}} \right|$	$\left| {{\mathbb{G}_1}} \right|$	$\left| {\mathbb{Z}_N^*} \right| + n\left| {{\mathbb{G}_1}} \right|$
本文方案	$\left| {{\mathbb{G}_1}} \right| + \left| {{\mathbb{G}_2}} \right|$	$\left| {{\mathbb{G}_1}} \right|$	$8\left| {\mathbb{Z}_N^*} \right| + 6\left| {{\mathbb{G}_1}} \right| + 2\left| {{\mathbb{G}_T}} \right|$

下载: 导出CSV 

| 显示表格

如图5所示，本文方案的签名通信开销是常数级别的，当环成员数量小于10时，本文方案与方案[27]相比不具有优势.当环成员数量小于20时，本文方案与方案[16]对比不具有优势.随着环成员数量的增长，本文方案的优势明显.

图  5  签名通信开销对比

Figure  5.  Comparison of signature communication cost

下载: 全尺寸图片 幻灯片

7.   结　　论

环签名技术是一种重要的区块链身份隐私保护技术，基于身份的环签名方案具有广泛的应用场景，它可以避免PKI体系带来的证书管理问题，也具有环签名的匿名性和不可伪造性. 随着区块链系统国产化的应用需求，传统的国密算法已无法满足复杂的区块链应用需求，本文提出了一种基于SM9数字签名的环签名方案，并在随机谕言机模型下证明了其安全性，与现有的方案相比，本文方案性能优势明显. 当环成员数量大于20时，本文方案在签名通信开销上具有明显优势. 随着环签名算法对环用户数量增长的应用需求，本文方案具备更高的实用性，有效解决了区块链中的身份隐私泄露问题. 未来工作，将研究降低环签名通信开销，设计面向轻量级设备的基于身份环签名方案.

作者贡献声明：安浩杨提出了算法方案并撰写论文；何德彪和包子健提出了指导意见；彭聪指导了实验分析部分；罗敏修改了论文.