基于SM9 数字签名的环签名及其在区块链隐私保护中的应用

安浩杨 何德彪 包子健 彭 聪 罗 敏

（武汉大学国家网络安全学院 武汉 430072）

（haoyangan@whu.edu.cn）

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

然而，文献[2-6]的方案基于公钥基础设施体系（public key infrastructure,PKI），用户公钥需要由可信证书颁发机构（certificate authority,CA）签署的证书进行认证.在该体系中，证书的管理包括证书的吊销、存储、分发和验证，代价是较高的.为解决该问题，Adi[7]在1984 年提出了基于身份的公钥密码学（identitybased 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 符号约定

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

2.2 双线性对

令 G1是由P1作为生成元的N阶加法循环群，G2是由P2作为生成元的N阶加法循环群，GT是阶为N的乘法循环群，双线性对是满足下列性质的一个映射e:G1×G2→GT.

1）双线性.对于任意的U∈G1,V∈G2和a,b∈都有e(a·U,b·V)=e(U,V)a·b.

2）非退化性.存在a,b∈使得e(U,V)≠1.

3）可计算性.对于所有U∈G1,V∈G2，存在多项式时间算法有效计算e(U,V).

2.3 数学困难问题

定义1.q-SDH 问题（q-strong Diffie-Hellman problem,q-SDH）.对于U∈G1，V∈G2，未知的a∈给定U,V,a·V,a2·V,…,aq·V，PPT 敌手输出 (c,(a+c)-1)，其中c∈

定义2.离散对数问题（discrete logarithm problem,DLP）.对于U∈G1，未知的a∈给定W=a·U，PPT敌手输出a.

2.4 SM9 数字签名算法

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

1）系统初始化算法.输入安全参数 λ，选取特定曲线生成参数t，构建椭圆曲线基域Fp，构建E(Fp)上的双线性对e:G1×G2→GT，选择哈希函数H1(·),H2(·):{0,1}*→KGC 随机选取d∈作为签名主密钥msk，并计算主公钥Ppub=d·P2.最后，输出系统参数Params={e,G1,G2,GT,P1,P2,Ppub,H1,H2}作为以下算法的默认输入.

4）签名验证算法.给定主公钥Ppub，用户A的身份标识IDA，消息m和签名值 σ，验证者计算P=H1(IDA)·P2+Ppub，验证是否成立，若成立，则 σ为合法签名，否则签名无效.

2.5 知识签名

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

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

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

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

2.6 动态累加器

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

1）累加器初始化算法.按照2.2 节定义双线性对e:G1×G2→GT，随机选择L={P1,s·P1,s2·P1,…,sq·P1}，其中q是可以被累加器累加的最大上限值.创建动态累加器实例，随机选择累加器值初始化为V0=u·P1.

2）累加器评估算法.给定累加器值V0和集合累加器值可以通过元组L在不知道s的情况下计算.

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

4）累加器成员删除算法.删除成员x′∈X，更新累加器值为V′=(x′+d)-1V，并更新证据W′=(x′-x)-1(W-V′).

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

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

Fig.1 Identity-based ring signature model图1 基于身份的环签名模型

3.1 系统模型

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

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

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

3）环签名算法RSign(m,Yn,dID).由签名者执行，输入消息m，环用户标识集合Yn={ID1,ID2,…,IDn}，用户私钥dID，输出环签名值 σ.

4）签名验证算法RVerify(m,σ,Yn).由验证者执行，输入消息m，签名 σ，环用户集合Yn={ID1,ID2,…,IDn}，输出accept/reject.

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

3.2 安全模型

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

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

1）系统初始化.S调用Setup(λ)生成系统参数Params和KGC 的主公私钥对 (Ppub,msk). S将Params和Ppub发送给敌手 A.

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

①哈希谕言机查询.A询问任意输入的哈希值.

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

③签名查询.A 询问环用户集合Yn={ID1,ID2,…,

IDn}和一个消息m，S 返回对应的签名 σ.

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

1）系统初始化.S调用Setup(λ)生成系统参数Params和 KGC 的主公私钥对 (Ppub,msk). S将Params和Ppub发送给A.

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

①哈希谕言机查询.A询问任意输入的哈希值.

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

③签名查询.A 询问环用户集合Yn={ID1,ID2,…,IDn}

和一个消息m，S 返回对应的签名值 σ.

3.3 方案设计

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

2）密钥提取算法Extract.由KGC 运行，输入用户A的身份标识IDA，KGC 主密钥msk，输出用户A（签名者）的私钥

KGC 计算用户A的私钥=d·(H1(IDA)+d)-1·P1并发送给用户A.

3）环签名算法RSign.由用户A运行，输入用户A的私钥n个成员标识组成的环用户集合Yn={ID1,ID2,…,IDn}，待签名消息m，输出环签名值 σ.

4）签名验证算法RVerify.由验证者运行，输入消息m，签名值σ=(ch,s1,…,s7,A1,…,A3,T1,…,T4,V)，环用户标识集合Yn={ID1,ID2,…,IDn}，输出accept/reject.

验证等式：

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

4 正确性和安全性分析

4.1 正确性分析

4.2 安全性分析

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

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

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

根据式(1)(2)，证明者具有

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

证毕.

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

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

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

证毕.

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

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

Fig.2 Blockchain transaction process based on ring signature图2 基于环签名的区块链交易流程

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

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

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

②KGC 执行Extract算法，生成用户的私钥dID并发送给用户.

③用户在发送交易之前，先构造交易提案，随机选取n个成员标识组成的环用户集合Yn={ID1,ID2,···,IDn}，使用RSign算法对交易提案进行签署，并发送给背书节点.

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

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

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

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

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

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

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

6 效率分析

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

6.1 计算开销分析

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

Table 1 Symbol Definition and Running Time表1 符号定义和运行时间

Table 2 Comparison of Computation Costs for Ring Signature Schemes表2 环签名方案的计算开销对比

Table 3 Comparison of Communication Costs for Ring Signature Schemes表3 环签名方案的通信开销对比 b

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

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

Fig.3 Signature generation computational cost comparison图3 签名生成计算开销对比

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

Fig.4 Signature verification computational cost comparison图4 签名验证计算开销对比

6.2 通信开销分析

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

Fig.5 Comparison of signature communication cost图5 签名通信开销对比

7 结论

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

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