陳啟虹，江明明，王 艷

（1淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000；2淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

0 引言

在基于屬性的簽名（Attribute-based Signature，ABS）中［1］，用戶從密鑰生成中心獲得他們的私鑰，此私鑰與他們的屬性列表相關(guān)聯(lián).用戶可以使用私鑰為訪問策略簽署消息，從而產(chǎn)生簽名，其中簽名的用戶屬性要滿足訪問策略.然后驗(yàn)證者將確信簽名者已經(jīng)認(rèn)可該消息.在安全性方面，基于屬性簽名首先要滿足不可偽造性，這就保證用戶即使通過與其他用戶合謀，也無法偽造出其不具備屬性的簽名.另一個(gè)安全需求是用戶屬性的匿名性，這意味著簽名不應(yīng)該泄露任何關(guān)于用來產(chǎn)生它實(shí)際屬性的信息.

基于屬性的加密（Attribute-based Encryption，ABE）概念首先是由Sahai等［2］提出的，后來擴(kuò)展到屬性簽名等研究?jī)?nèi)容，Maji等［3］提出基于屬性簽名的概念.人們相繼提出基于雙線性映射的屬性簽名［4-6］，但是這些方案容易受到量子密碼分析的攻擊.相對(duì)于基于大整數(shù)解問題和離散對(duì)數(shù)問題的密碼體制而言，基于格的密碼系統(tǒng)能夠抵抗量子攻擊.

在文獻(xiàn)［7-10］基于格的屬性簽名方案中，其安全性都是建立在格上困難問題——小整數(shù)解（Small Integer Solution，SIS）.在標(biāo)準(zhǔn)模型下，本文將基于SIS 問題的困難性來證明屬性簽名方案在選擇訪問結(jié)構(gòu)和消息攻擊下具有不可偽造性.

1 預(yù)備

1.1 定義

在本文中，設(shè)置以下定義.向量是列向量，矩陣是由列向量組成的，? 表示整數(shù)環(huán)，? 表示實(shí)數(shù)環(huán).x∈?m表示從? 上選取一個(gè)m維向量，x∈?m表示從? 上選取一個(gè)m維的向量.i∈[N] 意思是i={1,2,…,n} ，‖T‖表示矩陣T的歐幾里得范數(shù)，?表示T的Gram-Schmidt正交化，表示T的Gram-Schmidt范數(shù)，TΤ表示矩陣T∈的轉(zhuǎn)置矩陣.

1.2 格

定義1設(shè)b1,b2…,bm∈?m是一組線性無關(guān)的向量，如下m維滿秩格定義為：

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

定義2設(shè)q是素?cái)?shù)，矩陣A∈和向量u∈，定義：

定義3在給定一個(gè)正整數(shù)q，矩陣A∈和實(shí)數(shù)β的情況下，求向量v∈?m/{0 } 滿足Av=0 modq且‖v‖≤β.該定義說明小整數(shù)解問題.

1.3 相關(guān)算法

引理1［10］設(shè)素?cái)?shù)存在概率多項(xiàng)式時(shí)間算法TrapGen（q,n），利用參數(shù)q,n生

在方案中先利用上述引理1生成一個(gè)矩陣和小范數(shù)的陷門基，將產(chǎn)生的矩陣作為公共參數(shù)為私鑰的產(chǎn)生做基礎(chǔ).

定義4［11］對(duì)任意向量c∈?n及實(shí)數(shù)s ＞0，在?n上定義高斯分布函數(shù)：；在m維格Λ上定義離散高斯分布函數(shù)

引理2［12］存在概率多項(xiàng)式時(shí)間算法SampleR（1m），該算法是在?m×m中抽樣出一個(gè)可逆矩陣R，使得R的分布與Dm×m的統(tǒng)計(jì)距離是可忽略的.

然后在引理2抽樣出一個(gè)可逆矩陣R～Dm×m，同樣作為公共參數(shù)，為產(chǎn)生私鑰做準(zhǔn)備.

引理3［12］在輸入矩陣A∈，可逆矩陣R∈?m×m，(A) 的一組基TA和高斯參數(shù)s∈?＞0的情況下，存在概率多項(xiàng)式時(shí)間算法BasisDel(A,R,TA,s)，算法輸出(B)的一組基TB，其中B=AR-1∈.該引理利用已知矩陣A和可逆矩陣R，形成矩陣B=AR-1，輸出(B)的一組基TB.

在引理3中利用引理1和引理2所產(chǎn)生的矩陣，來產(chǎn)生私鑰.然后利用下面引理4來產(chǎn)生簽名.

引理4［13］在 輸 入 矩陣A∈,M1∈，(A)的一組基TA和向量u∈?n以及高斯參數(shù)的 情 況 下，存 在 概 率 多 項(xiàng) 式 時(shí) 間 算 法SampleLeft (A,M1,TA,u,s).令 矩 陣，算法輸出向量e∈且e的分布接近于DΛuq(F1),s.該引理利用已知矩陣A和M1，級(jí)聯(lián)成一個(gè)新矩陣F1=(A|M1) ，輸出一個(gè)小范數(shù)向量e，使得F1·e=umodq.

本方案主要是利用引理5和引理6來證明簽名方案的不可偽造性.

引理5［12］在輸入矩陣，其中a1,a2,…,am∈?n的情況下，存在概率多項(xiàng)式時(shí)間算法SampleRwithBasis (A)，輸出矩陣R∈?m×m和陷門TB，其中B=AR-1∈，R的分布與Dm×m的統(tǒng)計(jì)距離是可忽略的.

該引理利用已知矩陣A和B=AR-1，輸出矩陣R～Dm×m.

引理6［13］在輸入矩陣A,B∈（B的秩為n），隨機(jī)矩陣R∈{-1,1}m×m，(B)的一組基TB和向量u∈?n以 及 高 斯 參 數(shù)的 情 況 下，存 在 概 率 多 項(xiàng) 式 時(shí) 間 算 法SampleRight(A,B,R,TB,u,s) ，令矩陣F2=(A|AR+B)∈，算法輸出向量e∈?2m且e的分布接近于.

該引理利用已知矩陣A,B和R，級(jí)聯(lián)成一個(gè)新矩陣F2=(A|AR+B)，輸出一個(gè)小范數(shù)向量e，使得F2·e=umodq.

2 屬性簽名方案

2.1 形式化定義

定義5（訪問結(jié)構(gòu)） 令U={a tt1,att2,…,attN} 為屬性集合.對(duì)于每個(gè)atti∈U，Si=(vi,1,vi.2,…,vi,Ni)為atti可能值的集合，其中Ni是atti可能值的數(shù)量.令L=[L1,L2,…,LN]是用戶的屬性列表，W=[W1,W2,…,WN]是訪問結(jié)構(gòu)，L|=W表示屬性列表L滿足訪問結(jié)構(gòu)W.

屬性簽名方案由以下四個(gè)多項(xiàng)式時(shí)間算法組成：

Setup：輸入安全參數(shù)λ，輸出公共參數(shù)pp和主密鑰MK.

KeyGen：輸入pp，MK和用戶的屬性列表L，輸出私鑰SKL.

Sign：在給定pp，MK，SKL，消息M和訪問結(jié)構(gòu)W的情況下，當(dāng)與屬性列表L相關(guān)的用戶想要去簽名消息M時(shí)，當(dāng)且僅當(dāng)L|=W，該算法輸出簽名σ.

Verify：在接受到簽名σ，屬性列表L和訪問結(jié)構(gòu)W時(shí)，當(dāng)簽名有效時(shí)(L|=W)，該算法輸出1，否則輸出0.

2.2 正確性

定義6（正確性） 如果Verify(pp,σ,M,L,W)=1，則簽名方案是正確的.其中(pp,MK)←Setup(1λ)，M是消息，L是屬性列表，W是訪問結(jié)構(gòu)，SKL←KeyGen(pp,MK,L)，以及σ←Sign(pp,MK,SKL,L,M).

2.3 安全模型

屬性簽名方案的安全需求可以概括為不可偽造性和匿名性.

定義7［14］（不可偽造性） 如果存在任何概率多項(xiàng)式時(shí)間敵手A ，能夠以可忽略的優(yōu)勢(shì)贏得以下敵手A 和挑戰(zhàn)者C 之間的游戲，則屬性簽名方案在選擇性訪問結(jié)構(gòu)和消息攻擊下存在不可偽造性.

Init：敵手A 選擇訪問結(jié)構(gòu)W*和消息M*，并將其發(fā)送給挑戰(zhàn)者C.

Setup：挑戰(zhàn)者C 從敵手A 接收到W*和M*，運(yùn)行Setup（1λ）算法，并將公共參數(shù)pp發(fā)送給敵手A.

KeyGen Queries：A 將屬性列表L發(fā)送給C ，其中L|≠W*，C 返回與屬性列表L相關(guān)的私鑰SKL給A.

Sign Queries：敵手A 將屬性列表L，訪問結(jié)構(gòu)W和消息M發(fā)送給C ，其中若L|=W*，則有M≠M(fèi)*，C 返回簽名σ給A.

Forgery：A 輸出一個(gè)有效的偽造簽名(W*,M*,σ*)，其中W*是上述A 要挑戰(zhàn)的訪問結(jié)構(gòu)且M*沒有出現(xiàn)在上述查詢中.

上述游戲中敵手A 的優(yōu)勢(shì)定義為φadv( A )=P[Ev(pp,σ*,M*,L*,W*)=1].其中Ev表示簽名方案中的驗(yàn)證階段（Verify），Ev(pp,σ*,M*,L*,W*)=1表示驗(yàn)證成功，φadv表示敵手成功的概率.

定義8［14］（匿名性） 如果一個(gè)屬性簽名方案(pp,MK)←Setup（1λ），任意屬性列表L1,L2，SKL1←KeyGen(pp,MK,L1) ，SKL2←KeyGen(pp,MK,L2)，對(duì)于任意消息M和滿足訪問結(jié)構(gòu)W的屬性列表L1,L2，簽名σ1←Sign(pp,MK,SKL1,L1,M)和σ2←Sign(pp,MK,SKL2,L2,M)的分布是一樣的，那么屬性簽名方案是具有匿名性的.

3 本文方案

Setup（1λ）：輸入安全參數(shù)λ：

1）運(yùn)行TrapGen(q,n)生成矩陣A∈和的陷門TA∈?m×m；

2）運(yùn)行SampleR（1m）生成矩陣Ri,j∈，其中Ri,j～Dm×m，i∈[N],j∈[Ni]；

3）隨機(jī)選擇矩陣B,C∈和非零向量u∈.

令公共參數(shù)pp=（A,{Ri,j}i∈[N],j∈[Ni],B,C,u），主密鑰MK=（TA）.

KeyGen(pp,MK,L)：輸入公共參數(shù)pp，主密鑰MK和屬性列表L=(L1,L2,…,LN)，對(duì)于i∈[N],j∈[Ni],Li=vi,j；令 矩 陣，運(yùn) 行產(chǎn) 生Λ 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]，運(yùn)行SampleLeft(FL,C+H(M)D,TL,y,s) 產(chǎn)生抽樣e∈?2m；即簽名σ=(e).其中編碼函數(shù)H:→，詳細(xì)定義見文獻(xiàn)［13］.

Verify(pp,L,M,σ=(e))：令矩陣，檢查是否有FW,M·e=ymodq和，若是符合上述條件則接受，否則拒絕.

4 安全性分析

4.1 正確性

定理1以上構(gòu)造的屬性簽名方案，滿足上述定義的正確性.

證明當(dāng)訪問結(jié)構(gòu)符合L|=W時(shí)，有Li=Wi(i=[N]) ，故[FW|B+H(M)C]=FL,M.由引理7和引理5可知，有FW,M·e=ymodq且e≤s· 2m，即簽名方案是正確的.

4.2 不可偽造性

定理2上述構(gòu)造的屬性簽名方案，在格困難問題假設(shè)下，在選擇性訪問結(jié)構(gòu)和消息攻擊下存在不可偽造性.

證明假設(shè)存在概率多項(xiàng)式時(shí)間敵手A ，能夠以不可忽略的優(yōu)勢(shì)ε攻破上述所提出的方案.在這里，構(gòu)造一個(gè)模擬者B 來模擬A 要攻擊的環(huán)境.然后，經(jīng)過一系列的攻擊，最后利用A 的偽造來解決SIS困難問題的一個(gè)實(shí)例.

Init：敵手A 選擇訪問結(jié)構(gòu)W*和消息M*，并將其發(fā)送給模擬者B.

Setup：為應(yīng)對(duì)A 的查詢，B 做出以下運(yùn)算：

1）運(yùn)行TrapGen(q,n)生成矩陣A0∈和(A0)的陷門TA0∈?m×m；

2）運(yùn)行TrapGen(q,m)生成矩陣C∈和(C)的陷門

3）選擇矩陣R∈{-1，1}m×m；

4）對(duì)于每個(gè)屬性vi,j∈W*，其中i∈[N],j∈[Ni] ，運(yùn)行SampleR（1m）生成隨機(jī)可逆矩陣Ri,j，有

5）令矩陣B=A0R-H(M*)C和A=A0RN,jN*…R1,j1*；

6）對(duì)于i∈[N],j∈[Ni]，令矩陣

7）運(yùn)行Ni-1 次SampleRwithBasis(Fi)，生成矩陣Ri,j和Λ⊥q(Fi(Ri,j)-1)的陷門Ti,j，其中j∈[Ni],j≠j*.B 將公共參數(shù)pp=（A0,A,B,C,y,{Ri,j}i∈[N],j∈[Ni]）發(fā)送給A.

KeyGen Queries：假設(shè)敵手A 詢問屬性列表L的私鑰，其中L|=W*.這里必須存在i使得vi,j∈L且vi,j?W*，也就是意味著j≠j*.用t表示i的最小值，模擬者B 計(jì)算：

通過上述構(gòu)造，B 已知Tt,j是的 陷 門，其 中運(yùn) 行BasisDel生成(FL)的陷門TL.令SKL=(TL)，將其發(fā)送給A.

Sign Queries：假設(shè)敵手A 輸出(L,W,M)詢問屬性列表L在消息M上的簽名.若L|≠W*，則模擬者B 按照上述生成的私鑰SKL，然后利用Sign（pp,SKL,W,M）產(chǎn)生簽名σ.若L|=W*，則有M≠M(fèi)*，B 計(jì)算

H(M)-H(M*) 是非奇異的，令矩陣C′=(H(M)-H(M*))C，所以TC也是的陷門，B 可運(yùn)行Sam?令簽名σ=(e).模擬者將簽名σ發(fā)送給A.

Forgery：A 輸出(W*,M*,σ*=(e*))，模擬者B 計(jì)算，

4.3 比較

與相關(guān)方案文獻(xiàn)［15］從空間利用率上比較主密鑰、私鑰和簽名，比較結(jié)果如表1所示.

表1 從空間利用率上與文獻(xiàn)［15］比較主密鑰、私鑰和簽名

5 總結(jié)

在本文中，提出一個(gè)基于格的屬性簽名方案，并在基于SIS問題下證明方案的安全性.本文的方案與文獻(xiàn)［15］中方案不同之處在于，利用格擴(kuò)展算法來生成用戶的私鑰.方案使用更少的空間，但是該方案訪問策略較為簡(jiǎn)單.希望在之后的工作中可以構(gòu)造其他復(fù)雜訪問策略的基于格的屬性簽名方案.