基于SM9 标识密码算法的环签名方案*

彭 聪, 何德彪, 罗 敏, 黄欣沂, 李大为

1. 武汉大学 国家网络安全学院, 武汉430072

2. 福建师范大学 计算机与网络空间安全学院, 福州350117

3. 深圳技术大学 大数据与互联网学院, 深圳518118

1 引言

随着区块链技术的发展和成熟, 海量的交易数据和用户信息存储在区块链分布式账本中以实现数据防伪造和防篡改, 但也给身份隐私保护带来了严峻挑战[1]. 区块链具有开放性和透明性, 它允许任意用户获取交易相关信息, 包括地址、金额、时间等. 攻击者可以使用统计手段对大量交易数据和用户信息进行分析, 提取用户交易特征和真实地址等, 进而窃取用户隐私. 在使用区块链技术时, 保障交易和行为的匿名性是一个必不可少的隐私保护手段[2]. 例如, 门罗币使用环签名[3]、环机密交易[4]和地址加密等手段来混淆所有交易的收发地址和金额, 为用户提供了更高强度的隐私保护机制.

环签名是一种典型的数字签名方案, 最早由Rivest 等人[5]于2001 年提出. 在该签名方案中, 签名者随机选择多个环成员的公钥, 结合其公钥、私钥、随机数等数据完成签名, 而验证者仅能验证该签名是否来源于用户群组中的某一用户, 无法确认签名者的具体身份. 相对一般群签名而言, 环签名无需设置群管理员, 可由签名者自发组建用户群组. 环签名所具备的完全匿名性和不可伪造性使其非常适合于匿名投诉、电子投票、数字货币等领域. 自从环签名概念提出后, 研究人员设计了基于离散对数、双线性对、格理论[6]等不同密码原语的环签名方案. 除了传统公钥密码基础设施(public key infrastructure, PKI) 框架下的环签名方案, 还出现了基于身份的环签名和基于属性的环签名等方案. 相比而言, PKI 体制下的环签名方案面临证书管理和使用问题, 从而导致大量的系统资源被占用, 验证环节计算开销增加. 特别是当环用户数量增加时, 对签名和验证效率影响非常严重.

基于身份的密码体制(identity-based cryptography, IBC) 是由Shamir[7]于1984 年提出的, 其主要思路是利用用户天然的身份信息作为公钥, 无需公钥证书来证明用户身份与用户公钥的绑定关系. 由于解决了PKI 体制下的证书运维问题, IBC 密码体制得到广泛的关注. IBC 技术与环签名技术的结合大大地降低了密码系统的运维成本, 也实现了所需的匿名性和不可伪造性. 在匿名性方面, 环签名方案不仅对任意的验证用户匿名, 而且要对可信的密钥生成中心匿名. 即使拥有系统主密钥, 密钥生成中心也无法从签名值中知道签名者的真实身份. 在2001 年, Zhang 等人[8]提出了第一个基于身份的环签名方案, 随后出现了许多基于双线性对的环签名方案[9–13].

在2010 年, Brakerski 等人[14]提出了一个通用型的环签名构造方案, 它可以将已有的数字签名方案转变为环签名方案. 但其采用的的环状结构会导致计算开销随着环用户数量线性增长. 例如, 签名者执行一个环签名生成算法所需的时间与执行n次传统签名方案的时间相近,n为环用户数量. 因此, 基于身份的环签名方案的高效性是方案设计的基本要点. 此外, 考虑实际应用场景, 不同密码方案的部署应用会大大增加用户密钥管理负担和泄露风险. 譬如, 区块链系统中存在传统签名、盲签名、群签名、环签名等不同签名机制, 如果其密钥体制不一致, 用户需要存储和使用多套密钥, 这将增加终端或节点的存储资源消耗. 因此, 设计一个能够兼容原有数字签名算法的环签名方案也是当前的一个研究热点.

本文工作. 本文以SM9 数字签名算法为基础, 构建了一个新的基于身份的环签名方案, 并保障了新方案与SM9 算法私钥生成方式的一致性. 该方案的安全性可在随机预言模型下证明安全, 满足环签名方案所需的完全匿名性和不可伪造性. 通过与现有方案比对分析, 本文提出的方案在签名大小上占据明显优势,有效降低通信开销.

2 预备知识

2.1 符号约定

2.2 双线性对

设(G1,+) 和(G2,+) 是阶为N的加法循环群, (GT,·) 是阶为N的乘法循环群, 且N为素数.P1和P2分别是G1和G2的生成元, 且存在同态映射ψ:G2→G1使得ψ(P2)=P1.

双线性对e是从G1×G2到GT的映射, 满足以下性质:

上述问题的困难性是基于双线性对的身份密码体制的安全基础, 可以规约到G1、G2和GT上的离散对数问题的困难性.

2.3 SM9 数字签名算法

SM9 标识密码算法[15]是一种基于身份的密码体制, 包括数字签名算法、密钥交换算法和公钥加密算法3 个部分. 在曲线参数方面, SM9 算法采用了256 位的BN 曲线来实现双线性对运算. 具体地, 选取特定曲线生成参数t, 通过基域特征方程p(t) = 36t4+36t3+24t2+6t+1 构建椭圆曲线基域Fp; 再确定曲线方程参数为a和b, 嵌入次数为k=12 等参数, 构建E(Fp) 上的N阶循环子群G1及其生成元P1,E(Fp2) 上的N阶循环子群G2及其生成元P2, 双线性对e及其值域GT. 其中,p和N均为大素数. 此外, 不同的算法模块采用的曲线标识符、双线性对标识符以及私钥生成函数标识符取值各有不同, 具体参见文献[15].

下面给出SM9 数字签名算法的简单描述.

3 基于身份的环签名基本概念

相比传统数字签名, 环签名是面向群组的数字签名方案, 任何用户可以代表某一个用户群组完成对某个消息的签名. 为了便于描述, 本文假设用户群组中用户数量为n, 用户群组标识集合记为Un={ID1,ID2,··· ,IDn}, 其中IDi为第i个用户.

3.1 系统模型

在基于身份的环签名方案中, 密钥生成中心、签名者和验证者是3 种基本角色. 其中,

• 密钥生成中心(key generation center, KGC): 负责系统初始化工作, 初始化系统公开参数和签名主私钥, 公开系统参数并秘密持有主私钥. 系统初始化完成后, KGC 可为用户产生其身份标识对应的签名私钥.

• 签名者(Signer): 可以利用持有的签名私钥产生某个用户群组标识集合对于任何消息的环签名值.就正确性而言, 用户群组标识集合可由签名者自由组建, 但必须包含自身的身份标识.

• 验证者(Verifier): 可以验证某个群组对某个消息的环签名值的合法性.

不失一般性, 假设签名者为用户群组中的第π个用户(1≤π ≤n), 对应的身份标识和签名私钥分别为IDπ和skπ. 基于身份的环签名方案由下列4 个算法构成:

(1) 系统建立Setup(λ): 一个由KGC 执行的概率多项式时间(PPT) 算法, 输入为安全参数λ, 输出

为系统公开参数par 和签名主私钥msk.

(2) 密钥提取KeyExt(IDi,msk,par): 一个由KGC 执行的确定性算法, 输入为用户身份标识IDi, 签名主私钥msk 及公开参数par, 输出为用户签名私钥ski.

(3) 环签名生成RingSig(M,Un,skπ,par): 一个由签名者执行的概率多项式算法, 输入待签名的消息M, 环用户Un={ID1,ID2,··· ,IDn}, 用户签名私钥skπ(1≤π ≤n) 以及公开参数par, 输出为签名值σ.

(4) 环签名验证RingVrf(M,Un,σ,par): 一个由验证者执行的确定性算法, 输入为被签名的消息M,环用户Un={ID1,ID2,··· ,IDn}, 待验证的签名值σ以及公开参数par, 输出为验证通过accept或验证失败reject.

对于基于身份的环签名而言, 其正确性表现为: 对于合法的签名, 验证算法总是验证通过; 对于非法的签名, 则验证者总是验证失败. 即

3.2 安全模型

根据Bender 等[16]给出的环签名的安全性定义, 环签名必须满足不可伪造性和匿名性. 在匿名性方面, 基于身份的环签名方案不仅要求对一般验证者匿名, 还需要对拥有系统主私钥的KGC 匿名. 本文给出了基于身份的环签名方案的安全性定义:

定义3 (不可伪造性) 给定系统参数λ和一个基于身份的环签名方案, 多项式时间的敌手A与挑战者S进行EUF 游戏. EUF 游戏过程如下:

(2) 询问阶段. 除Hash 询问以外,A可以向S进行以下询问:

(a) 密钥提取询问.A向S提交一个标识IDi,S返回对应的私钥ski.

(b) 签名询问.A向S提交一个用户标识群组Uj={ID1,ID2,··· ,IDjl}(1≤l ≤n) 和一个消息Mj,S返回一个Uj对消息Mj的环签名σj.

(3) 伪造阶段.A伪造挑战用户群组U∗={ID∗1,ID∗2,··· ,ID∗n}对消息M∗的一个签名σ∗, 并且A未询问过U∗中任一用户的私钥, 也未询问U∗对M∗的签名. 如果A伪造的签名σ∗是合法的,则A赢得游戏.

(1) 系统建立阶段.S运行Setup(λ) 生成系统公开参数par 和签名主私钥msk.S产生一个最大用户集合Uθ={ID1,ID2,··· ,IDθ}.S将公开参数par 发送给A.

(2) 询问阶段. 除Hash 询问以外,A可以向S进行以下询问:

(a) 密钥提取询问.A向S提交一个标识IDi,S返回对应的私钥ski.

(b) 签名询问.A向S提交一个用户标识群组Uj={ID1,ID2,··· ,IDjl}(1≤l ≤n) 和一个消息Mj,S返回一个Uj对消息Mj的环签名σj.

(3) 挑战阶段.A向S提交一个消息M∗, 一个用户群组U∗以及两个标识IDπ1,IDπ2∈U∗,S随机选择b ∈{0,1}, 调用算法RingSig(M∗,U∗,skπb,par), 用IDπb的私钥skπb对消息M∗进行环签名, 并将得到的签名返回给A.

(4) 猜测阶段.A输出一个比特b′∈{0,1}. 若b′=b,A赢得游戏.

4 SM9 环签名生成与验证方案

本文所构造的环签名方案具体描述如下:

算法1 (系统建立) (par,msk)←Setup(λ): 输入安全参数λ, KGC 按照如下方式生成系统公开参数par 和主私钥msk:

(1) 随机产生一个整数d ∈[1,N −1].

(2) 计算G2中的元素Ppub-s=[d]P2.

(3) 输出公开参数par=Ppub-s和主私钥msk=d.

算法2 (密钥提取) ski ←KeyExt(IDi,msk,par): 对于身份标识IDi, KGC 利用主私钥d进行如下计算得到对应的签名私钥ski:

算法3 (环签名生成)σ ←RingSig(M,Un,skπ,par): 为生成消息M的环签名σ, 签名者的计算过程如下:

(1) 预计算GT中的元素g=e(P1,Ppub-s).

(2) 随机选取r ∈Z∗N, 并计算R=[r]P1.

(3) 计算wπ+1=e(R,Ppub-s) 和hπ+1=H2(Un||M||wπ+1).

(4) 令i=π+1, 循环执行以下步骤n −1 次:

(a) 若i>n, 则令i=1 和h1=hn+1.

(b) 随机选取ri ∈Z∗N, 并计算Ri=[ri]P1.

(c) 计算vi=H1(IDi) 和ui=e(Ri,[vi]P2+Ppub-s).

(d) 计算wi+1=ui·ghi和hi+1=H2(Un||M||wi+1).

(e) 令i=i+1.

(5) 计算l=r −hπmodN; 若l=0, 则重新执行. 否则, 计算Rπ=[l]skπ.

(6) 输出消息M的环签名值为σ=(h1,R1,R2,··· ,Rn).

算法4 (环签名验证) accept/reject←RingVrf(M,Un,σ,par). 为验证消息M′的签名值σ′, 验证者的计算过程如下:

5 安全性证明

本节我们将证明基于SM9 标识密码算法的环签名方案具有匿名性和不可伪造性. 在不可伪造性方面,我们仅考虑敌手为恶意的用户而非恶意的KGC, 因为KGC 在知道系统主私钥的情况下可以随意伪造任意用户的签名值. 在匿名性方面, 我们考虑敌手为恶意的KGC 和用户, 即保证在敌手即使知道系统主私钥的情况下也无法知道环签名的真实签名者身份.

定理1 在随机预言模型下, 如果q-SDH 问题是困难的, 则本文中设计的环签名方案具有不可伪造性.

定理2 如果环签名所使用的随机数来源是均匀分布的, 则本文中设计的环签名方案具有匿名性.

证明: 假定存在两个均匀分布的随机数源Ω1和Ω2, 对任意给定x1←$Ω1和x2←$Ω2,x1和x2是统计不可区分的. 假设存在多项式时间的敌手A能够以不可忽略的优势ϵ找到真实签名者, 则挑战者S能够以不可忽略的概率优势ϵ区分x1和x2.

(1) 系统建立阶段. 在此阶段,S执行Setup 算法生成系统公开参数和主私钥, 并确定一个最大可能用户群组的标识集合Uθ. 之后,S将par 和msk 以及Uθ发送给A. 因为考虑到KGC 可能是敌手A, 故将msk 对A可知.

(2) 询问阶段. 在此阶段,A可以进行任意数据的Hash 询问, 而S只需要产生随机响应值返回即可.同时,A可以询问Uθ中任意用户的私钥和任何消息的环签名值.

(3) 挑战阶段.S接收到A的挑战请求(M∗,U∗,IDπ1,IDπ2) 后, 采用不同的随机源作为输入, 执行两次RingSig 算法:

6 效率分析

本文以计算开销和通信开销来评估本文方案的效率, 并将评估结果与方案[10]、方案[11] 进行比较.

在计算开销方面, 我们主要考虑了密钥提取、环签名生成和签名验证等3 个环节的时间开销. 因为系统建立算法可由KGC 预先完成, 不影响使用过程中的效率, 故我们不对其进行评估比较. 表1 给出了3种方案的计算开销对比分析结论. 其中,Tinv表示Fp上的模逆计算时间,Tpm-1和Tpm-2分别表示G1和G2上的标量乘计算时间,Tbp表示双线性对计算时间,Tpm-3表示GT上的标量乘计算时间,Th表示哈希函数平均运算时间,Thtp表示将一个比特串哈希到椭圆曲线点HashToPoint 的运算时间. 其他运算所需时间占整体运算时间比重非常低, 因此我们做出适当忽略.

表1 环签名方案的计算开销分析Table 1 Comparisons of computation costs

对于密钥提取算法, 本文的方案需要1 次哈希运算、1 次Fp上的模逆运算和1 次G2上的点乘运算,而方案[10] 和方案[11] 均需要1 次HashToPoint 运算. 对于签名生成算法, 本文的方案需要n次哈希运算、2n次G1上的点乘运算、n次双线性对运算和n −1 次GT上的标量乘运算, 而方案[10] 需要n+1哈希运算、n次HashToPoint 运算和2n次G2上的点乘运算, 方案[11] 需要n+1 哈希运算、1 次G1上的点乘运算、n −1 次G2上的点乘运算和n+1 次双线性对运算. 对于签名验证算法, 本文的方案需要n次哈希运算、n次G1上的点乘运算、n次双线性对运算和n次GT上的标量乘运算, 而方案[10] 和方案[11] 均需要n+1 哈希运算、n次G2上的点乘运算和2 次双线性对运算. 因为HashToPoint 的时间开销远远大于一个点乘和模逆运算的总时间开销, 本文的方案在密钥生成过程具备较高的性能优势. 但很显然, 本文方案在签名生成和验证环节不占性能优势.

在通信开销方面, 表2 给出了每种方案的系统公钥长度, 用户私钥长度和签名长度. 其中,|G1|、|G2|、|GT| 分别表示对应群中元素的长度,|Zp| 表示Zp中元素长度. 具体地, 以256 比特BN 曲线[18]对例,|G1| = 512 bit,|G2| = 1024 bit,|GT| = 3072 bit,|Zp| = 256 bit. 显然, 本文方案在私钥长度与其他方案[10,11]一致, 但系统公钥长度略高于其他方案[10,11], 即多一个G1中的元素作为系统公钥. 但在签名长度方面, 本文方案的签名值包含一个Zp中的元素和n个G1中的元素, 总签名长度为512n+256 比特. 而方案[10] 的签名值包含n个GT中的元素、n个Zp中的元素和1 个G1中的元素, 其长度为3328n+512 比特. 方案[11] 的签名值包含n+1 个G2中的元素, 其长度为1024n+1024 比特. 那么,本文方案的签名长度约是方案[10] 的0.15 倍和方案[11] 的0.49 倍. 综合而言, 本文方案通信开销存在明显优势, 存储开销略高于其他方案, 具有更好的实用性.

表2 环签名方案的通信开销分析Table 2 Comparisons of communication costs

7 结论

基于身份的环签名方案应用场景非常广泛, 一方面它具有环签名的完全匿名性和不可伪造性, 另一方面它有效地避免了传统公钥基础设施所面临的证书管理问题. 考虑到基于身份密码体制下环签名方案与传统签名方案密钥一致性问题, 本文提出了一个基于SM9 数字签名算法的环签名方案, 并在随机预言模型下证明其安全性, 通过与现有方案的性能比对分析表明本方案在签名大小方面具有较大优势, 因而具备更高的实用性. 进一步的工作, 将考虑如何降低环签名验证开销以及如何实现环签名大小不随环用户数量变化等问题.