格上基于身份的可链接环签名*

汤永利, 夏菲菲, 叶 青, 王永军, 张晓航

1. 河南理工大学 计算机科学与技术学院, 焦作454003

2. 河南工业和信息化职业学院, 焦作454000

1 引言

近年来, 区块链[1]技术已经在人类生活的各个方面得到应用, 在一定程度上解决了相互不信任的个体之间的协作与价值流转. 然而区块链上数据的传输和存储都是公开可见的, 可以提供任意信息的查询, 仅通过“伪匿名” 的形式对交易双方的隐私进行保护, 无法实现完备的隐私保护需求. 为了满足这一应用需求, 《中国区块链技术和应用发展白皮书》[2]明确提出: 环签名比较有希望解决区块链的隐私保护问题,从而满足用户身份匿名性及交易信息不可伪造性的需求.

Rivest 等[3]在2001 年提出第一个环签名方案, 他们给出了基于Rabin 陷门函数和RSA 陷门置换的环签名, 并在随机谕言机模型下证明所提方案的安全性. 在环签名中, 任意用户可以代表整个环对任意消息进行签名, 获取环公钥的任意验证者都可以验证签名是否来自此环, 但无法确定具体是哪个成员生成的签名. 将环签名应用于区块链, 可以有效保护用户的身份隐私. 值得注意的是若仅采用普通的环签名体制解决区块链中的隐私保护问题, 资金持有者在环签名的庇护下, 可以对同一笔资金签名(即花费) 多次,而不能被检测出来, 即出现所谓的“双重花费” 问题. 为了避免出现该问题, 应采用可检测两个签名是否为同一用户所签的可链接环签名. 2004 年, Liu 等[4]对基本的环签名方案添加可链接属性, 基于离散对数假设提出了第一个随机谕言机模型下的可链接环签名. 2006 年, Au 等[5]基于累加器技术提出了签名尺寸为常数的可链接环签名, Yuen 等[6]在2013 年提出了第一个标准模型下基于椭圆曲线配对技术的可链接环签名, 2014 年Liu 等[7]提出了具有无条件匿名性的可链接环签名, 并给出形式化安全模型定义与证明,但上述可链接环签名均基于公钥证书, 存在密钥管理负担, 难以避免复杂的用户公钥证书管理问题.

Shamir 在1984 年提出了基于身份的密码体制[8], 在基于身份的密码体制中, 密钥生成中心(key generation center,KGC)根据用户的身份信息(例如: 身份证号、邮箱地址等)生成该用户公钥,根据系统主密钥和用户的身份信息进行计算生成对应的私钥, 避免了传统公钥基础设施(public key infrastructure,PKI) 体系中用户公钥证书复杂的管理问题. Zhang 等[9]在2002 年提出了第一个基于身份的环签名方案, 之后基于身份的环签名方案[10–13]被相继提出. 2013 年, Au 等[14]给出了第一个基于身份的可链接环签名, 且签名长度为常数, 使用离散对数难题(discrete logarithm problem, DLP) 等困难假设在随机谕言机模型下证明所提方案的安全性. 由于量子计算技术带来的威胁, 传统基于数论难题(例如: 大整数因子分解难题、有限域离散对数难题) 的密码体制将会被攻破, 若环签名仍采用基于数论难题进行构造, 在量子时代, 环签名的安全性将难以保证. 近几年, 基于格理论构造的新型密码体制因其具有较好的渐进效率、可并行化、运算简单、抗量子攻击和存在最坏情况下的随机实例等优点, 成为后量子密码时代的研究热点, 而基于格的环签名方案[15,16]也相继被提出. 2018 年, Torres 等[17]提出了随机谕言机模型下第一个基于格的一次可链接环签名, 采用拒绝抽样技术使得输出签名的分布与签名私钥的分布相互独立, 使签名生成的效率进一步提高. 随后, Torres 等[18]又在文献[17] 方案的基础上进行扩展给出了支持多输入、多输出的可链接环签名方案, 实用性更强. 2018 年, Baum 等[19]给出了格上更加简单、高效的可链接环签名方案.

为了使基于身份的可链接环签名能够抵抗量子攻击, 本文提出了一个格上基于身份的可链接环签名.主要贡献有:

(1) 将格密码学与基于身份的可链接环签名相结合, 构造了随机谕言机模型下安全的格上基于身份的可链接环签名;

(2) 利用Gentry 等[20]提出的原像抽样算法和Lyubashevsky[21]提出的拒绝抽样技术分别生成用户的私钥及签名, 提高了用户密钥和签名的生成效率;

(3) 在随机谕言机模型下证明本文所提的方案满足无条件匿名性、不可伪造性及可链接性, 将所提可链接环签名方案的不可伪造性归约至格上小整数解(SIS) 困难假设;

(4) 分别从时间开销和存储开销两个方面给出详细的性能分析. 结果表明, 与格上的可链接环签名方案相比, 本方案密钥和签名生成以及签名验证的效率有了进一步的提高.

2 预备知识

2.1 符号说明

为表述方便对文中符号进行说明, 如表1 所示.

表1 符号说明Table 1 Symbol description

除了表1 中的符号, 文中还用到计算复杂度符号O, ω, 并定义了negl(n) 表示n 的可忽略函数.

2.2 格的相关定义

2.3 困难假设

2.4 相关算法

2.5 拒绝抽样技术

3 基于身份的可链接环签名定义及安全模型

3.1 基于身份的可链接环签名定义

一个基于身份的可链接环签名方案[23]包括以下5 个概率多项式时间算法:

(1) Setup(1n): 由密钥生成中心(KGC) 执行, 输入安全参数n, 输出系统公开参数PP 和系统主密钥MSK.

(2) KeyExt(IDi,MSK,PP): 由密钥生成中心(KGC) 执行, 输入用户身份IDi和系统主密钥MSK以及系统公开参数PP, 输出用户身份IDi对应的私钥SIDi.

(3) Sign(PP,R,u,SIDi): 由签名者执行, 输入公开参数 PP, 构成环的用户身份集合 R =(ID1,ID2,··· ,IDl), 待签消息u ∈{0,1}∗以及签名者身份IDi∈R 对应的私钥SIDi, 输出环R 关于消息u 的可链接环签名σR(u), 签名σR(u) 包含可链接标签I, 对于同一签名者产生的两个可链接环签名σR(u1), σR∗(u2), 有I(1)= I(2).

(4) Verify(PP,R,u,σR(u)): 由验证者执行, 输入公开参数 PP, 构成环的用户身份集合 R =(ID1,ID2,··· ,IDl), 待签消息u ∈{0,1}∗以及签名σR(u). 若验证成功则输出“Valid”, 否则输出“Invalid”.

(5) Link(σR(u1),σR∗(u2)): 由验证者执行, 输入签名σR(u1), σR∗(u2), 验证I(1)=I(2)是否成立.如果相等则输出“Link”, 否则输出“Unlink”.

3.2 安全模型

基于身份的可链接环签名的安全性定义[23,24]除了满足普通环签名的正确性、匿名性和不可伪造性之外, 还要满足可链接性. 可链接环签名的正确性包括签名验证正确性和链接正确性两方面, 具体定义见定义4; 匿名性是指攻击者无法确定签名是由环中具体哪个成员生成, 具体定义见定义5; 不可伪造性是指在不知签名者签名私钥的情况下, 环外成员无法代替真实签名者进行签名, 具体定义见定义6; 可链接性是指只具有一个签名私钥的用户无法给出两个签名能够通过链接算法的检测, 具体定义见定义7. 我们用攻击者A 与挑战者S 之间进行的一系列游戏来刻画基于身份的可链接环签名的安全性定义, 在随机谕言机模型下, 攻击者A 可以访问随机谕言机(Random Oracle) 并进行以下两种询问:

(1) 私钥询问(Corruption Oracle): 攻击者A 选择用户身份IDi发送给挑战者S 进行私钥询问, 挑战者S 运行密钥提取算法KeyExt(IDi,MSK,PP) 生成IDi对应的私钥SIDi, 并将结果返回给攻击者A.

(2) 签名询问(Singing Oracle): 攻击者A 选择一个环R = (ID1,ID2,··· ,IDl), 一个用户身份IDk∈ R 和消息u ∈ {0,1}∗发送给挑战者S 进行签名询问, 挑战者S 运行签名算法Sign(PP,R,u,SIDk), 用IDk对应的私钥SIDk进行签名, 并将生成的签名结果σR(u) 返回给攻击者A.

定义4 (Correctness) 可链接环签名的正确性包括签名验证正确性和签名链接正确性两方面, 其中,验证正确性是指对于合法签名σR(u), 验证算法Verify(PP,R,u,σR(u)) 输出“Invalid” 的概率是可忽略的, 即:

链接正确性是指两个签名 (σR(u1), σR∗(u2)) 若为用户用同一个签名私钥生成, 链接算法Link(σR(u1),σR∗(u2)) 输出“Unlink” 的概率是可忽略的, 即:

匿名性(Anonymity) 可链接环签名的匿名性用如下攻击者A 与挑战者S 之间进行的游戏来刻画.

(1) 系统建立: 输入安全参数n, 挑战者S 运行系统建立算法Setup(1n) 得到系统公开参数PP 和系统主密钥MSK, 并将公开参数PP 发送给攻击者A.

(2) 询问阶段: 攻击者A 可以进行多项式次访问谕言机, 并进行如上私钥询问及签名询问.

(3) 挑战阶段: 攻击者A 输入环用户身份集合R = (ID1,ID2,··· ,IDl) 和待签消息u ∈{0,1}∗, 两个用户身份IDi0, IDi1∈R 进行签名询问, 挑战者S 随机选择b ∈{0,1} 计算IDib对应的私钥SIDib, 运行签名算法用签名私钥SIDib对消息u 进行签名, 将生成的签名结果σR(u) 返回给攻击者A.

(4) 猜测阶段: 攻击者A 输出b∗作为对签名人身份的猜测, 如果b=b∗则攻击者A 赢得游戏.则攻击者A 赢得匿名性游戏. 攻击者A 赢得匿名性游戏的优势定义为:

定义5 (Anonymity) 当对于任意多项式时间攻击者A, A是可忽略的, 则称一个可链接环签名方案是匿名的.

不可伪造性(Unforgeability) 可链接环签名的不可伪造性用如下攻击者A 与挑战者S 之间进行的游戏来刻画.

(1) 系统建立: 输入安全参数n, 挑战者S 运行系统建立算法Setup(1n) 得到系统公开参数PP 和系统主密钥MSK, 并将公开参数PP 发送给攻击者A, 将系统主密钥MSK 保密.

(2) 询问阶段: 攻击者A 可以进行多项式次访问谕言机, 并进行如上私钥询问及签名询问.

(3) 伪造阶段: 攻击者A 给出(u∗,R∗,σR∗(u∗)), 若满足以下条件:

(a) Verify(u∗,R∗,σR∗(u∗))=“Valid”;

(b) 攻击者A 未询问过环R∗中任一用户的私钥;

(c) 攻击者A 未发起过(u∗,R∗) 的签名询问;

(d) 环R∗中任一用户的公钥均由挑战者S 给出.则攻击者A 赢得不可伪造性游戏. 攻击者A 赢得不可伪造性游戏的优势定义为:

定义6 (Unforgeability) 对于任意多项式时间攻击者A,是可忽略的, 则称一个可链接环签名方案是不可伪造的.

可链接性(Linkability) 可链接环签名的可链接性用如下攻击者A 与挑战者S 之间进行的游戏来刻画.

(1) 系统建立: 输入安全参数n, 挑战者S 运行系统建立算法Setup(1n) 得到系统公开参数PP 和系统主密钥MSK, 并将公开参数PP 发送给攻击者A, 将系统主密钥MSK 保密.

(2) 询问阶段: 攻击者A 可以进行多项式次访问谕言机, 并进行如上私钥询问及签名询问.

4 方案构造

为解决现有基于身份的可链接环签名不能抵抗量子攻击的问题, 本文基于原像抽样和拒绝抽样等技术构造了一个格上基于身份的可链接环签名. 本文核心思想是将基于身份的密码学引入在Torres 等[17]提出的基于格的可链接环签名方案中, 在系统建立阶段用陷门生成算法[20]获取系统主密钥, 在密钥提取阶段釆用原像抽样[20]技术获取用户私钥, 在签名生成阶段采用拒绝抽样技术[21]以一定的概率生成签名.本文所构造的方案具体描述如下:

5 安全性证明

定理2 (Correctness) 本文提出的格上基于身份的可链接环签名是正确的.

证明: 下面将从签名验证正确性及链接正确性两方面证明本方案满足正确性.

(1) 验证正确性: 由可链接环签名的生成过程我们有:

由于序列{Ci} (i=1,2,··· ,l) 在可链接环签名验证过程中与签名过程中相同, 我们有C1=Cl+1.

因此, 本方案满足签名验证正确性.

(2) 链接正确性: 一个用户用自己的私钥SIDi签署两条消息u1,u2生成两个签名σR(u1), σR∗(u2),σR(u1), σR∗(u2) 分别包含对应的可链接标签I(1), I(2). 则链接算法进行验证时必然输出为“Link”.

分析: 签署消息u1的可链接标签为I(1)=H2(C,r), 签署消息u2的可链接标签为I(2)=H2(C,r),由于, I(1), I(2)的产生均用同一个随机选取的矩阵C, 若签名者用相同的私钥r 签署消息u1, u2则必有I(1)=I(2).

因此, 本方案满足签名链接正确性.

综上所述, 本文提出的格上基于身份的可链接环签名满足正确性.

定理3 (Anonymity) 对于任意多项式时间攻击者A, 本方案在随机谕言机模型下是无条件匿名的.

证明: 通过挑战者S 和攻击者A 之间进行游戏交互完成无条件匿名性证明. Game0模拟挑战者S对身份IDi0进行签名, Game1模拟挑战者S 对身份IDi1进行签名. 如果攻击者A 对两个签名的离散高斯分布不可区分, 那么本文方案满足无条件匿名性.

Game0游戏:

(3) 挑战者S 运行签名算法Sign(PP,R,u,SIDi0), 生成签名σR(u) = (C1,t1,··· ,tl,I,b) 并发送给攻击者A.

(4) 攻击者A 收到签名后给出关于b 的猜测.

Game1游戏:

定理4 (Unforgeability) 如果SIS 问题是困难的, 对于任意多项式时间攻击者A, 本方案在随机谕言机模型下是不可伪造的.

证明: 通过挑战者S 和攻击者A 之间进行游戏交互完成不可伪造性证明. 假设攻击者A 能够以不可忽略的概率ε 成功伪造签名, 下面将展示挑战者S 如何利用攻击者A 的伪造结果找到一个短向量e, 构造一个SIS 问题的解.

攻击者A 与挑战者S 之间的游戏交互如下:

故//e//≤2σ2(m+1), 令β = 2σ2(m+1), 短向量e 即是SIS(n,m,β) 的解.

概率分析: 假设攻击者A 能够成功伪造一个合法环签名的概率为ε, 允许进行私钥询问的最大次数为qE. 下面分析S 成功解决SIS 问题的概率ε∗, 挑战者S 会在下列情况下放弃游戏, 导致模拟失败.

i) (R∗,u∗,T∗,v∗) 不在询问列表L2中. 因为H2是随机谕言, 若A 没有向S 提交过(R∗,u∗)询问, 签名σR∗(u∗) 通过验证C1=Cl+1的概率为1/(2d)l.

ii) tk−tk∗=0(签名σR(u) 对应的签名私钥和伪造签名σR∗(u∗) 对应的签名私钥相等) 的概率为ε1, 由于攻击者A 在不知道签名私钥的情况下, 签名与签名私钥是相互独立的, 因此签名σR(u) 和σR∗(u∗) 的私钥相等的概率ε1是可忽略的.

综上所述, 挑战者S 成功解决SIS 问题的概率ε∗≥ε −1/(2d)l−ε1.

定理5 (Linkability) 如果本方案是不可伪造的, 对于任意多项式时间攻击者A, 本方案在随机谕言机模型下是可链接的.

证明: 通过挑战者S 和攻击者A 之间进行游戏交互完成可链接性证明. 根据可链接性的定义, 假设存在攻击者A 能够以不可忽略的概率ε 赢得定义7 中的可链接性游戏, 则攻击者A 将与挑战者S 进行如下游戏交互:

(1) 挑战者S 运行系统建立算法Setup(1n) 得到系统公共参数PP、系统主密钥MSK, 发送公共参

数PP 给攻击者A.

(2) 攻击者A 可以进行多项式次的访问谕言机, 并进行Hash 询问、私钥询问及签名询问, 挑战者S返回其询问对应的结果给攻击者A.

1) Hash 询问.

a. H1询问: A 可以选择用户身份IDi∈R 进行询问, S 将aIDi返回给A.

6 性能分析

本文选择三个代表性方案作为参照对象: 2017 年, Jia 等[15]提出的格上高效的基于身份的环签名,2018 年, Torres 等[17]提出的第一个格上的可链接环签名以及Baum 等[19]提出的格上更加简单、高效的可链接环签名. 将从时间开销与存储开销两个方面分别对本文方案与以上三个方案进行性能分析.

四种方案的时间开销比较结果如表2 所示, 其中l 代表环成员个数, TTG,TSP,TSD,TBD,TLHL,TMUL,TINV分别表示算法TrapGen、SamplePre、SampleDom、格基委派算法(BasisDel)、剩余哈希定理(Leftover Hash Lemma, LHL)[25]、标量乘法运算及矩阵求逆运算的单步平均耗时. 主要从系统密钥生成、用户密钥生成、签名生成和签名验证所消耗的时间分别进行分析. 考虑矩阵标量乘运算、高斯采样(SampleDom) 等相对耗时较多的计算过程, 忽略Hash 运算、矩阵的加减法等相对耗时较少的运算过程.在系统密钥生成方面, 由于本文方案和文献[15] 的方案均赋予了基于身份的属性, 运用陷门生成算法TTG生成系统主密钥, 即系统主密钥生成时间为TTG. 而文献[17] 的方案和文献[19] 的方案不是基于身份的可链接环签名, 没有这部分时间开销. 在用户密钥生成方面, 本文方案运用耗时较短的哈希函数生成用户的公钥, 调用原像抽样算法(SamplePre) 生成用户的私钥, 因此, 环用户公钥生成时间可忽略, 环用户密钥生成耗时为TSP; 文献[15] 的方案用户公钥运用矩阵的标量乘运算和求逆运算生成, 私钥经调用格基委派算法(BasisDel) 和原像抽样算法(SamplePre) 生成; 而文献[17] 的方案和文献[19] 的方案用户公钥生成均由一个随机选取的矩阵与向量进行标量乘运算生成. 文献[17] 的方案用户私钥经运用剩余哈希定理(LHL) 生成, 文献[19] 的方案用户私钥由高斯采样算法(SampleDom) 生成. 综上考虑, 本文用户密钥生成效率优于其他三种方案. 在签名生成方面, 本文方案最终生成的签名为σR(u)=(C1,t1,··· ,tl,I,b), 其中序列{Ci}, (i = 1,2,··· ,l) 的生成需要2l 个矩阵与向量的标量乘运算, 在签名生成过程需要调用高斯釆样算法(SampleDom) 随机选取l 个m+1 维的列向量, 可链接标签I 经调用耗时较少哈希函数生成,因此, 可链接标签的生成时间可忽略, n 维列向量b 的生成需要1 个矩阵与向量的标量乘运算. 经对比,本文与文献[19] 的方案签名生成耗时相当, 较文献[17] 的方案签名生成少了l+1 个矩阵的标量乘运算,较文献[15] 的方案签名生成多了l 个矩阵的标量乘运算. 在签名验证方面, 本文方案进行验证时, 需要计算序列{Ci}, (i=2,··· ,l+1) 的值, 需要进行2l 次矩阵与向量的标量乘运算得到Cl+1的值与C1比较进而对生成的签名进行验证. 经比较, 本文方案的签名验证效率与所选的三个参考方案相比有了一定的提高. 文献[15] 的方案在签名生成方面具有一定的优势, 但其在密钥生成阶段消耗时间过多. 综合整个系统的时间开销, 我们的方案在用户密钥生成、签名生成、签名验证方面具有更高的效率.

四种方案的存储开销比较结果如表3 所示, 其中l 仍代表环成员个数. 主要从公钥长度、私钥长度及签名长度分别进行分析. 在用户公钥长度方面, 本文方案中用户的公钥由用户的身份信息进行哈希运算生成, 用户公钥为n 维列向量. 文献[15] 的方案用户公钥由一个n×m 维矩阵与一个m×m 维矩阵进行标量乘运算生成, 用户公钥为一个n×m 维矩阵. 文献[17] 的方案用户公钥由一个n×(m −1) 维的矩阵与一个m −1 维的列向量进行标量乘运算生成, 用户公钥为一个n 维列向量. 文献[19] 的方案用户公钥由一个n×m 维的矩阵与一个m 维的列向量进行标量乘运算生成, 用户公钥为一个n 维列向量. 比较结果表明本文方案的用户公钥长度与文献[17] 的方案和文献[19] 的方案相等, 较文献[15] 的方案有了明显的减小. 在用户私钥长度方面, 本文用户的私钥基于原像抽样算法(SamplePre) 生成, 用户私钥为一个m维的列向量, 文献[15] 的方案中用户私钥经调用格基委派算法(BasisDel) 和原像抽样算法(SamplePre)生成为一个m×k 维矩阵, 文献[17] 的方案中用户私钥经调用剩余哈希定理(LHL) 定义为一个m −1 维列向量, 文献[19] 的方案中用户私钥运用高斯采样算法(SampleDom) 生成为一个m 维的列向量, 比较结果表明本文方案的用户私钥长度与文献[17] 的方案相等, 较文献[15] 的方案有了明显的减小. 在签名长度方面, 本文方案生成的签名中向量ti(i = 1,2,··· ,l) 是m+1 维列向量, 向量b 是n 维列向量. 分析结果表明, 文献[17] 的方案和文献[19] 的方案签名长度相等, 本文生成签名的长度略高于所选的三个参考方案. 综合分析整个系统的存储开销性能, 文献[15] 的方案用户公钥、私钥长度较长, 其他方面四种方案的存储开销基本相当.

表2 时间开销比较Table 2 Comparison of time costs

表3 存储开销比较Table 3 Comparison of storage overhead

我们设置参数n = 8, m = 640, q = 232= 4 294 967 296, k = 6 使得我们的方案是安全的, 将本文方案在Windows 10 系统、Intel(R) Core(TM)i5-8300H CPU@2.30 GHz 处理器和8.00 GB 运行内存下进行实现与评估. 表4、表5 中分别给出所选的三个参考方案与本文方案在环成员数量不同情况下的时间开销和存储开销对比结果. 给出本方案的时间开销分别在l = 1, l = 8, l = 32, l = 128 的结果如表6 所示.实验结果与理论分析基本一致, 综合整个系统的时间开销, 我们的方案在用户密钥生成、签名生成、签名验证方面具有更高的效率. 综合分析整个系统的存储开销性能, 文献[15] 的方案用户公钥、私钥长度较长,其他方面4 种方案的存储开销基本相当. 本文方案有待进一步优化从而获得更小的存储开销.

7 结束语

相较普通基于数字证书的可链接环签名, 基于身份的可链接环签名能够在保护用户身份隐私的同时,有效解决复杂的用户证书管理问题. 但在量子技术得到应用的前提下, 基于经典数论难题的可链接环签名(包括基于数字证书和基于身份的可链接环签名) 方案都将不再安全. 因此, 本文运用原像抽样算法与拒绝抽样等技术, 提出了一种格上基于身份的可链接环签名方案. 在随机谕言机模型下, 将本方案的安全性归约至小整数解(SIS) 困难假设, 并给出了严格的安全性证明. 对比已有的格上可链接环签名方案, 本文所提出的方案在用户密钥生成、签名生成和验证的效率等有了进一步的优化与提高.

表4 时间开销比较(ms)Table 4 Comparison of time costs (ms)

表5 存储开销比较(KB)Table 5 Comparison of storage overhead (KB)

表6 本文方案时间开销比较(ms)Table 6 Comparison of time costs of proposed scheme (ms)