格上高效的属性签名方案

2022-06-17陈启虹江明明

淮北师范大学学报(自然科学版) 2022年2期

陈启虹，江明明，王艳

（1淮北师范大学计算机科学与技术学院，安徽淮北 235000；2淮北师范大学数学科学学院，安徽淮北 235000）

0 引言

在基于属性的签名（Attribute-based Signature，ABS）中［1］，用户从密钥生成中心获得他们的私钥，此私钥与他们的属性列表相关联.用户可以使用私钥为访问策略签署消息，从而产生签名，其中签名的用户属性要满足访问策略.然后验证者将确信签名者已经认可该消息.在安全性方面，基于属性签名首先要满足不可伪造性，这就保证用户即使通过与其他用户合谋，也无法伪造出其不具备属性的签名.另一个安全需求是用户属性的匿名性，这意味着签名不应该泄露任何关于用来产生它实际属性的信息.

基于属性的加密（Attribute-based Encryption，ABE）概念首先是由Sahai等［2］提出的，后来扩展到属性签名等研究内容，Maji等［3］提出基于属性签名的概念.人们相继提出基于双线性映射的属性签名［4-6］，但是这些方案容易受到量子密码分析的攻击.相对于基于大整数解问题和离散对数问题的密码体制而言，基于格的密码系统能够抵抗量子攻击.

在文献［7-10］基于格的属性签名方案中，其安全性都是建立在格上困难问题——小整数解（Small Integer Solution，SIS）.在标准模型下，本文将基于SIS 问题的困难性来证明属性签名方案在选择访问结构和消息攻击下具有不可伪造性.

1 预备

1.1 定义

在本文中，设置以下定义.向量是列向量，矩阵是由列向量组成的，ℤ 表示整数环，ℝ 表示实数环.x∈ℤm表示从ℤ 上选取一个m维向量，x∈ℝm表示从ℝ 上选取一个m维的向量.i∈[N] 意思是i={1,2,…,n} ，‖T‖表示矩阵T的欧几里得范数，͂表示T的Gram-Schmidt正交化，表示T的Gram-Schmidt范数，TΤ表示矩阵T∈的转置矩阵.

1.2 格

定义1设b1,b2…,bm∈ℝm是一组线性无关的向量，如下m维满秩格定义为：

其中B=[b1,b2,…,bm]∈ℤm×m是格Λ的一组基.

定义2设q是素数，矩阵A∈和向量u∈，定义：

定义3在给定一个正整数q，矩阵A∈和实数β的情况下，求向量v∈ℤm/{0 } 满足Av=0 modq且‖v‖≤β.该定义说明小整数解问题.

1.3 相关算法

引理1［10］设素数存在概率多项式时间算法TrapGen（q,n），利用参数q,n生

在方案中先利用上述引理1生成一个矩阵和小范数的陷门基，将产生的矩阵作为公共参数为私钥的产生做基础.

定义4［11］对任意向量c∈ℝn及实数s ＞0，在ℝn上定义高斯分布函数：；在m维格Λ上定义离散高斯分布函数

引理2［12］存在概率多项式时间算法SampleR（1m），该算法是在ℤm×m中抽样出一个可逆矩阵R，使得R的分布与Dm×m的统计距离是可忽略的.

然后在引理2抽样出一个可逆矩阵R～Dm×m，同样作为公共参数，为产生私钥做准备.

引理3［12］在输入矩阵A∈，可逆矩阵R∈ℤm×m，(A) 的一组基TA和高斯参数s∈ℝ＞0的情况下，存在概率多项式时间算法BasisDel(A,R,TA,s)，算法输出(B)的一组基TB，其中B=AR-1∈.该引理利用已知矩阵A和可逆矩阵R，形成矩阵B=AR-1，输出(B)的一组基TB.

在引理3中利用引理1和引理2所产生的矩阵，来产生私钥.然后利用下面引理4来产生签名.

引理4［13］在输入矩阵A∈,M1∈，(A)的一组基TA和向量u∈ℤn以及高斯参数的情况下，存在概率多项式时间算法SampleLeft (A,M1,TA,u,s).令矩阵，算法输出向量e∈且e的分布接近于DΛuq(F1),s.该引理利用已知矩阵A和M1，级联成一个新矩阵F1=(A|M1) ，输出一个小范数向量e，使得F1·e=umodq.

本方案主要是利用引理5和引理6来证明签名方案的不可伪造性.

引理5［12］在输入矩阵，其中a1,a2,…,am∈ℤn的情况下，存在概率多项式时间算法SampleRwithBasis (A)，输出矩阵R∈ℤm×m和陷门TB，其中B=AR-1∈，R的分布与Dm×m的统计距离是可忽略的.

该引理利用已知矩阵A和B=AR-1，输出矩阵R～Dm×m.

引理6［13］在输入矩阵A,B∈（B的秩为n），随机矩阵R∈{-1,1}m×m，(B)的一组基TB和向量u∈ℤn以及高斯参数的情况下，存在概率多项式时间算法SampleRight(A,B,R,TB,u,s) ，令矩阵F2=(A|AR+B)∈，算法输出向量e∈ℤ2m且e的分布接近于.

该引理利用已知矩阵A,B和R，级联成一个新矩阵F2=(A|AR+B)，输出一个小范数向量e，使得F2·e=umodq.

2 属性签名方案

2.1 形式化定义

定义5（访问结构）令U={a tt1,att2,…,attN} 为属性集合.对于每个atti∈U，Si=(vi,1,vi.2,…,vi,Ni)为atti可能值的集合，其中Ni是atti可能值的数量.令L=[L1,L2,…,LN]是用户的属性列表，W=[W1,W2,…,WN]是访问结构，L|=W表示属性列表L满足访问结构W.

属性签名方案由以下四个多项式时间算法组成：

Setup：输入安全参数λ，输出公共参数pp和主密钥MK.

KeyGen：输入pp，MK和用户的属性列表L，输出私钥SKL.

Sign：在给定pp，MK，SKL，消息M和访问结构W的情况下，当与属性列表L相关的用户想要去签名消息M时，当且仅当L|=W，该算法输出签名σ.

Verify：在接受到签名σ，属性列表L和访问结构W时，当签名有效时(L|=W)，该算法输出1，否则输出0.

2.2 正确性

定义6（正确性）如果Verify(pp,σ,M,L,W)=1，则签名方案是正确的.其中(pp,MK)←Setup(1λ)，M是消息，L是属性列表，W是访问结构，SKL←KeyGen(pp,MK,L)，以及σ←Sign(pp,MK,SKL,L,M).

2.3 安全模型

属性签名方案的安全需求可以概括为不可伪造性和匿名性.

定义7［14］（不可伪造性）如果存在任何概率多项式时间敌手A ，能够以可忽略的优势赢得以下敌手A 和挑战者C 之间的游戏，则属性签名方案在选择性访问结构和消息攻击下存在不可伪造性.

Init：敌手A 选择访问结构W*和消息M*，并将其发送给挑战者C.

Setup：挑战者C 从敌手A 接收到W*和M*，运行Setup（1λ）算法，并将公共参数pp发送给敌手A.

KeyGen Queries：A 将属性列表L发送给C ，其中L|≠W*，C 返回与属性列表L相关的私钥SKL给A.

Sign Queries：敌手A 将属性列表L，访问结构W和消息M发送给C ，其中若L|=W*，则有M≠M*，C 返回签名σ给A.

Forgery：A 输出一个有效的伪造签名(W*,M*,σ*)，其中W*是上述A 要挑战的访问结构且M*没有出现在上述查询中.

上述游戏中敌手A 的优势定义为φadv( A )=P[Ev(pp,σ*,M*,L*,W*)=1].其中Ev表示签名方案中的验证阶段（Verify），Ev(pp,σ*,M*,L*,W*)=1表示验证成功，φadv表示敌手成功的概率.

定义8［14］（匿名性）如果一个属性签名方案(pp,MK)←Setup（1λ），任意属性列表L1,L2，SKL1←KeyGen(pp,MK,L1) ，SKL2←KeyGen(pp,MK,L2)，对于任意消息M和满足访问结构W的属性列表L1,L2，签名σ1←Sign(pp,MK,SKL1,L1,M)和σ2←Sign(pp,MK,SKL2,L2,M)的分布是一样的，那么属性签名方案是具有匿名性的.

3 本文方案

Setup（1λ）：输入安全参数λ：

1）运行TrapGen(q,n)生成矩阵A∈和的陷门TA∈ℤm×m；

2）运行SampleR（1m）生成矩阵Ri,j∈，其中Ri,j～Dm×m，i∈[N],j∈[Ni]；

3）随机选择矩阵B,C∈和非零向量u∈.

令公共参数pp=（A,{Ri,j}i∈[N],j∈[Ni],B,C,u），主密钥MK=（TA）.

KeyGen(pp,MK,L)：输入公共参数pp，主密钥MK和属性列表L=(L1,L2,…,LN)，对于i∈[N],j∈[Ni],Li=vi,j；令矩阵，运行产生Λ q(FL) 的一组基TL∈；令SKL=(TL).

Sign(pp,SKL=TL,W,M)：在输入中有消息M，以及属性列表满足L|=W，即有Li=Wi(i=1,2,…,N).令矩阵FL,M=[FL|B+H(M)C]，运行SampleLeft(FL,C+H(M)D,TL,y,s) 产生抽样e∈ℤ2m；即签名σ=(e).其中编码函数H:→，详细定义见文献［13］.

Verify(pp,L,M,σ=(e))：令矩阵，检查是否有FW,M·e=ymodq和，若是符合上述条件则接受，否则拒绝.