鄧宇喬

廣東商學院 數(shù)學與計算科學學院，廣州 510320

基于動態(tài)屬性的數(shù)字簽名方案

鄧宇喬

廣東商學院 數(shù)學與計算科學學院，廣州 510320

DENG Yuqiao.Dynamic attribute-based signature scheme.Computer Engineering and Applications,2013,49（15）：19-22.

1 引言

基于屬性的數(shù)字簽名是由基于模糊身份簽名[1]的概念發(fā)展而來，機制更為靈活，其在精確（fine-grained）訪問控制的匿名認證系統(tǒng)中發(fā)揮了重要的作用。在基于屬性的簽名體制中，用戶從屬性中心獲得一組屬性的私鑰，然后用這組屬性私鑰進行簽名。簽名者的權(quán)力由其所擁有的屬性集合決定。驗證者通過驗證該簽名，只能確定該簽名滿足某個訪問結(jié)構(gòu)，但是不知道簽名者是如何滿足這個訪問結(jié)構(gòu)的。2008年Guo等[2]提出了一個在Goyal等[3]的加密方案上構(gòu)造的屬性簽名方案，Shahandashti等[4]在Sahai和Waters[5]的加密方案上構(gòu)造了基于屬性的門限簽名方案，另外，Chase[6]等提出了多授權(quán)中心概念，并給出了一個多授權(quán)中心的基于屬性的加密方案，用戶的多個屬性由不同的授權(quán)中心監(jiān)管，并分別對其中的每個屬性產(chǎn)生加密私鑰。

但是，以上的基于屬性的密碼體制尚存有一個明顯的缺陷，即其屬性不具有“動態(tài)性”。當系統(tǒng)中的成員屬性發(fā)生變更后，沒有相應的修改機制，需要重新分配屬性密鑰，這將為系統(tǒng)增添極大負擔。文獻[7]提出一種具有動態(tài)屬性的群簽名方案，但其方案主要為針對群簽名的特性提出的。本文借鑒條件密碼方案的思想[8-10]，給出一個具有動態(tài)屬性的一般數(shù)字簽名方案。在條件密碼機制中一段密文如需解密，需要滿足某個特定的條件，該條件由條件認證方所認證，如果不滿足條件，則解密者無法解密。如滿足特定條件，則除了可以解密出明文外，解密者還能得到條件認證方的一個簽名。本文利用條件密碼的思想，對屬性簽名方案進行改造，使得傳統(tǒng)的屬性簽名方案能在屬性擁有者滿足某種特定條件后可以申請動態(tài)增加其屬性密鑰，而其新增的屬性密鑰的控制權(quán)由條件認證方所控制，這種思想的好處在于，其可以大大減輕屬性密鑰生成方的負擔，并且具有認證的功能。隨后，本文在選擇集合模型[11-15]下證明了該方案的安全性。

2 背景知識介紹

2.1 訪問樹結(jié)構(gòu)

定義1（訪問結(jié)構(gòu)）設{P1，P2，…，Pn}是n個參與者的集合。設Λ表示由參與者集合的子集構(gòu)成的集合，B，C表示參與者集合的子集，對于所有的B，C：如果B∈Λ并且B?C，那么C∈Λ，則說Λ是一個單調(diào)的訪問結(jié)構(gòu)。一個訪問結(jié)構(gòu)（或者單調(diào)的訪問結(jié)構(gòu)）Λ是一個非空的參與者集合的子集（或者單調(diào)子集）構(gòu)成的集合。設D表示參與者的任一子集，如果D∈Λ，則叫做授權(quán)集合，如果D?Λ則叫做非授權(quán)集合。

訪問樹結(jié)構(gòu)（Access Τree）：訪問樹用于表達一個控制訪問結(jié)構(gòu)。每一棵樹的非葉子節(jié)點都是一個門限，用kx表示該節(jié)點的門限值。訪問樹中的某節(jié)點是可訪問的，當且僅當該節(jié)點的子節(jié)點集合中至少有kx個節(jié)點是可訪問的。而葉子節(jié)點則與屬性綁定。對于葉子節(jié)點x，函數(shù)att(x)表示葉子節(jié)點相對應的屬性。對于任意節(jié)點x，函數(shù)index(x)表示該節(jié)點的索引值，而parent(x)則表示該節(jié)點的父節(jié)點的索引值。

2.2 基于條件的密碼技術(shù)

本文在改造屬性簽名方案中，借鑒了基于條件的密碼技術(shù)?；跅l件的密碼技術(shù)首先由Kim等在文獻[8]中提出，在該文中，他們所構(gòu)造的基于條件的數(shù)字簽名主要是針對某個特定的應用場景——數(shù)字簽名的公平交換而言的。Berta[9]等人把這種技術(shù)應用到微型的電子卡片技術(shù)中，隨后，基于條件的密碼技術(shù)被Klonowski[10]等人作了有意義的推廣，得到了一定的發(fā)展。在基于條件的加密方案中，某用戶對文檔的解密建立在某個條件成立的基礎上。本文將使用這種加解密技術(shù)以解決屬性的動態(tài)調(diào)整問題。

2.3 雙線性映射技術(shù)

雙線性映射是指具有下面性質(zhì)的映射：

設G是由P生成的循環(huán)加群，其階為素數(shù)q，V是一個階為q的循環(huán)乘群。

（2）非退化：存在一個P∈G，滿足e(P，P)≠1。

（3）可計算：對P，Q∈G，存在一個有效的算法計算e(P，Q)。

2.4 困難性假設

定義2（判定Diffie-Hellman問題（DDH））該假定指的是：設(a'，b'，c'∈Zp)，不存在多項式時間敵手B有不可忽略的優(yōu)勢區(qū)分元組(Α'=ga'，B'=gb'，C'=ga'b')和元組(Α'=ga'，B'=gb'，C'=gc')。

敵手B解決該問題的優(yōu)勢定義為：

定義3（判定Diffie-Hellman假定（DBDH））該假定指的是：設(a，b，c，z∈Zp)，不存在多項式時間敵手B有不可忽略的優(yōu)勢區(qū)分元組(Α=ga，B=gb，C=gc，e(g，g)abc)和元組(Α=ga，B=gb，C=gc，e(g，g)z)。敵手B解決該問題的優(yōu)勢為：

3 基于動態(tài)屬性的數(shù)字簽名方案

3.1 方案定義

實現(xiàn)的基于動態(tài)屬性的數(shù)字簽名方案主要包含以下六個算法：初始化、密鑰產(chǎn)生、生成動態(tài)屬性密鑰、屬性密鑰提取、簽名、驗證，具體描述如下：

初始化：該算法接受一個安全參數(shù)λ和屬性集合U的輸入，輸出公共參數(shù)PK和主密鑰MSK。

密鑰產(chǎn)生：該算法接受MSK，PK，訪問結(jié)構(gòu)Α以及屬性集合γ的輸入，輸出該屬性集合的私鑰SK。

生成動態(tài)屬性密鑰：該算法接受系統(tǒng)私鑰和用戶滿足某屬性所需條件的明文m的輸入，輸出該屬性的動態(tài)屬性密鑰。

屬性密鑰提取：該算法接受認證方對用戶滿足某屬性的簽名SIG的輸入，還原該屬性的密鑰。

簽名：該算法接受公鑰PK、用戶屬性私鑰以及消息m的輸入，輸出用戶對該消息的簽名。

驗證：該算法接受公鑰PK，消息m以及簽名S的輸入，如果簽名為真，則輸出1，否則輸出0。

3.2 方案安全模型定義

本文方案的安全模型參考的是選擇集合安全模型的定義方法（Selective-Set Model）[3]，方案安全模型定義如下：

參數(shù)設置：挑戰(zhàn)者運行方案的參數(shù)設置算法，并把產(chǎn)生的公共參數(shù)發(fā)送給敵手。

階段1在該階段，敵手Α可以詢問多個訪問結(jié)構(gòu)Λj的動態(tài)屬性密鑰及滿足該屬性所需具備條件的散列值（即H(m)值），并可將該結(jié)構(gòu)中的任意的動態(tài)屬性密鑰進行提?。吹玫狡鋵傩悦荑€），但需滿足以下條件：敵手能從動態(tài)屬性密鑰中提取出來的屬性密鑰集合γ'必須是γ的真子集（即γ'?γ），且γ?Λj。

挑戰(zhàn)：在此階段，敵手提交兩個等長的消息M0和M1。挑戰(zhàn)者隨機拋一枚硬幣b，并根據(jù)屬性集合γ對Mb進行簽名，然后把簽名發(fā)送給敵手Α。

階段2此階段與階段1相同。

猜測：在此階段，敵手Α輸出對b的猜測b'。

需要注意的是，簽名方案的安全性通常是建立在簽名的不可偽造性上的，本文所提的簽名的安全性為建立在Selective-Set Model模型上，然而，可以看出，如果某個攻擊者在計算上甚至無法分清兩個等長消息的簽名，則他必定是無法偽造出該消息的簽名的，因此，本文所提方案在傳統(tǒng)簽名的不可偽造性上也是成立的。

3.3 方案描述

設G1是一個以素數(shù)p為階的雙線性群，g是其生成元。

為拉格朗日參數(shù)，S是一個在Zp的集合。所有的屬性集合為U，而所有屬性都與Zp*中的元素關(guān)聯(lián)。

初始化：對于一個集合的屬性，為其隨機選擇Zp上的ti作為屬性i的私鑰。同時，選擇屬性認證方的私鑰xΑ∈Zp，認證方的公鑰為yΑ=gXΑ。并公布屬性對應的公鑰為而簽名者的公鑰為Y=e(g，g)y，簽名者的主密鑰為，屬性認證方的私鑰為xΑ。

選擇隨機數(shù)k，計算對于消息m的Elgamal簽名：如果該簽名合法，將滿足以下式子：yaab=gH(m)。其中消息m為滿足該屬性所需的條件。認證方公開a和ab。

該屬性的擁有者可計算二元組dk=(a',b')=(Kx*S'z,az)，。二元組dk即為動態(tài)屬性密鑰。在此二元組中，維持了本文所提方案的屬性密鑰的動態(tài)性，在下一步密鑰提取的過程中，將給出當用戶滿足某個條件時，如何通過此二元組計算出用戶目前尚未滿足的某個屬性的密鑰。

由以上過程可以看到，在計算動態(tài)屬性密鑰時，與具體密文無關(guān)，僅需提供屬性密鑰即可計算。因此，可對具體屬性預先計算好其動態(tài)屬性密鑰。

屬性密鑰提取：當認證方認證某用戶滿足某屬性的條件時，認證方把其簽名的參數(shù)b發(fā)給用戶，因而，用戶可以得到該屬性的密鑰：Kx'=a'/b'b=Kx*S'z/azb=Kx。

同時，用戶還可以得到認證方頒發(fā)的簽名SIG=(a，b)。該簽名滿足：

簽名：對于屬性集合γ和消息M∈G2，簽名者選擇隨機值r，s，用以下方式計算簽名：

驗證：驗證過程分成以下步驟：

如果節(jié)點x為葉子節(jié)點，則計算：

Dx=e(Ci，Bi)=（x為i對應的屬性的節(jié)點序號）

如果節(jié)點x為非葉子節(jié)點，則簽名者的身份屬性中必定包含至少有kx個子節(jié)點的值是滿足訪問結(jié)構(gòu)要求的。定義Sx表示這kx個子節(jié)點值的集合，定義Fz表示節(jié)點z所表示的值，通過拉格朗日插值定理，可以得到：

其中，i=index(z)，Sx'={index(z):z∈Sx}。

假設某用戶的屬性滿足其簽名的權(quán)限，則驗證者能根據(jù)用戶最終解出訪問樹根節(jié)點的值：Fr==e(g,g)sy。

隨后，驗證者驗證是否有：gM=E'/e(g，g)sy成立。

4 方案安全性證明

定理1假定以上的定義2、定義3的問題難解，則本文所述方案是安全的，即在Seletive-Set游戲中，敵手的優(yōu)勢是可忽略的。

證明假設存在一個多項式時間的敵手Α能在Seletive-Set游戲中破解本文的方案，將構(gòu)造一個模擬器B同時解決本文定義2至定義3中的兩個問題。

首先，挑戰(zhàn)者設置一個雙線性映射e和群G1，G2，并給定生成元g。挑戰(zhàn)者投擲硬幣μ，如果μ=1，則設置(Α,B，C，D，Α'，B'，C')=(ga，gb，gc，e(g，g)abc，ga'，gb'，ga'b')；如果μ=0，則設置(Α，B，C，D，Α'，B'，C')=(ga，gb，gc，e(g，g)z，ga'，gb'，gc')。

初始化：模擬器運行算法Α，Α選擇它需要挑戰(zhàn)的屬性集合γ。

的h'將表示某個動態(tài)屬性的滿足條件明文的散列值，即h'=H(m)）。隨后，模擬器公開上述公共參數(shù)。

階段1在該階段中，為了簡化描述，分為兩種情況討論。

（1）敵手提取了γ中所有的屬性密鑰

這種情況下，即敵手知道了γ中所有的屬性密鑰，此時動態(tài)屬性密鑰的作用消失了（也即敵手滿足了所有動態(tài)屬性密鑰的條件）。

此時按以下兩種方法構(gòu)造訪問樹中某棵子樹的根節(jié)點的多項式：

PolySat(Tx，γ，λx)：這種情況下，Tx(γ)=1，即根節(jié)點為x的樹能被訪問結(jié)構(gòu)γ訪問。此時，選取根節(jié)點x的多項式qx，使得qx(0)=λx（λx∈Zp為已知），隨后，選取該根節(jié)點每一個孩子x'的多項式qx'，使得qx'(0)=qx(index(x'))。

PolyUnsat(Tx，γ，gλx)：這種情況下，Tx(γ)=0，即根節(jié)點為x的樹不能被訪問結(jié)構(gòu)γ訪問。此時只知道gλx的值。定義一個度為dx的多項式qx，令qx(0)=λx，由于Tx(γ)=0，所以，訪問結(jié)構(gòu)中滿足條件的節(jié)點不多于dx個，設hx≤dx為滿足條件的節(jié)點個數(shù)，對于滿足條件的節(jié)點x'，設qx(index(x'))=λx'，λx'∈Zp，由于qx是度為dx的多項式，所以可以選取不多于dx個節(jié)點的值。算法遞歸地調(diào)用以下兩個方法設置該樹以下的節(jié)點的多項式：

PolySat(Tx'，γ，λx')：如果x'滿足條件，此時λx'已知，故可以直接構(gòu)造。

PolyUnsat(Tx'，γ，)：如果x'不滿足條件，此時只知道的值（因為在此情況下，事實上只知道的值）。

最后，模擬器執(zhí)行PolyUnsat(T，γ，Α)來定義整棵訪問樹的根節(jié)點的多項式。可以發(fā)現(xiàn)，對于每一個節(jié)點x，如果該節(jié)點滿足條件，則必然知道λx的值，否則，至少知道gλx的值。隨后，模擬器定義多項式Qx(.)=bqx(.)，所以，對于根節(jié)點r的多項式Qr而言，有Qr(0)=ab。以下定義葉子節(jié)點對應的Kx值如下：

（2）敵手僅提取了部分的動態(tài)屬性密鑰

即敵手至少有一個屬性att(x)的屬性密鑰未知，而僅知道其對應的動態(tài)屬性密鑰。當敵手詢問的動態(tài)屬性att(x')≠att(x)時，隨機選取t'，m'∈，令H(m)=m'，計算SIG=(a，b)=(gt'，t'-1(m'-xΑa))，則該屬性對應的動態(tài)密鑰為dk=(a'，b')=(Kx'*abz，az)，z∈。

挑戰(zhàn)：敵手Α提交兩個等長的消息M0，M1，挑戰(zhàn)者隨機拋一枚硬幣b，隨機選取r∈，并公布以下簽名：

如果μ=1，則密文和動態(tài)密鑰都為合法的構(gòu)造，如果μ=0，則(D，C')=(e(g，g)z，gc')均為隨機數(shù)。

階段2該階段與階段1過程一樣。

猜測：Α提交對b的猜測b'，如果b'=b，則模擬器輸出μ=1表示這是合法的DH和DBDH問題的元組，否則，模擬器輸出μ=0。

假設敵手Α攻破本系統(tǒng)的優(yōu)勢為ε，那么根據(jù)概率的知識容易知道，模擬器攻破以上兩個難題的優(yōu)勢為ε/2。

5 結(jié)論

基于屬性的數(shù)字簽名方案能很好地解決簽名者的身份隱私問題，但由于其屬性不具有“動態(tài)”的特性，導致了用戶在屬性遷移時的不便。本文利用“條件”的思想，把方案中的屬性改成動態(tài)的形式，當用戶的屬性變遷后，他可以通過與認證機構(gòu)的交互，自己計算出新增的屬性密鑰，從而較好地實現(xiàn)了用戶權(quán)限的靈活控制。

[1]Yang P，Cao Z，Dong X.Fuzzy identity based signature，Report 2008/002[EB/OL].[2012-11-21].http：//eprint.iacr.org/2008/002.

[2]Guo S，Zeng Y.Attribute-based signature scheme[C]//International Conference Information Security and Assurance（ISA 2008），2008：509-511.

[3]Goyal V，Pandey O，Sahai A，et al.Attribute-based encryption for fine-grained access control of encrypted data[C]//Proc of CCS.New York：ACM Press，2006：89-98.

[4]Shahandashti S F，Safavi-Naini R.Τhreshold attribute-based signatures and their application to anonymous credential systems[C]//LNCS 5580：AFRICACRYPΤ 2009.Berlin：Springer-Verlag，2009：198-216.

[5]Sahai A，Waters B.Fuzzy identity-based encryption[C]//LNCS 3494：AdvancesinCryptology-EUROCRYPΤ 2005.Aarhus：Springer-Verlag Press，2005：457-473.

[6]Chase M.Multi-authority attribute based encryption[C]//Vadhan S P.Lecture Notes in Computer Science ΤCC，2007：515-534.

[7]Emura K，Miyaji A，Omote K.A dynamic attribute-based group signature scheme and its application in an anonymous survey for the collection of attribute statistics[C]//International Conf on Availability，Reliability and Security，2009.

[8]Lee B，Kim K.Fair exchange of digital signatures using conditional signature[C]//Symposium on Cryptography and Information Security，Shirahama，Japan，2002：179-184.

[9]Berta I Z，Buttyn L，Vajda I.Migrating the untrusted terminal problem using conditional signatures[C]//International Conference on Information Τechnology：Coding and Computing（IΤCC），2004.

[10]Marek K，Miros?aw K，Anna L.Conditional digital signatures[C]//LNCS 3592：ΤrustBus 2005，2005：206-215.

[11]陳少真，王文強，彭書娟.高效的基于屬性的環(huán)簽名方案[J].計算機研究與發(fā)展，2010，47（12）：2075-2082.

[12]孫昌霞，馬文平，陳和風.多授權(quán)中心的基于屬性的簽名[J].四川大學學報：工程科學版，2011，43（1）：83-86.

[13]Lewko A，Waters B.Unbounded HIBE and attribute-based encryption[C]//Proceedings of the 30th Annual International Conference on Τheory and Applications of Cryptographic Τechniques：Advances in Cryptology，EUROCRYPΤ’11，2011.

[14]Lewko A，Okamoto Τ.Fully secure functional encryption：attribute-based encryption and（hierarchical）inner product encryption[EB/OL].[2012-11-21].http：//eprint.iacr.org/2010/110.

[15]Ostrovsky R，Sahai A，Waters B.Attribute based encryption with non-monotonic access structures[C]//ACM Conference on Computer and Communications Security（ACM CCS），2007.

DENG Yuqiao

Mathematics and Computer Science College,Guangdong University of Business Studies,Guangzhou 510320,China

Τhe user’s privacy can be well protected using attribute-based signature scheme.But the attributes are static in all attribute-based signature schemes,which are due to certain problems in practical applications：when the member’s attribute has been changed,there is no corresponding mechanism to re-assign the attributes key,which will cause tremendous burden.Based on conditions-based encryption,this paper develops a dynamic attribute-based signature scheme.User is allowed to calculate its own attributes key in the scheme once it satisfies certain attribute after the authenticating party’s digital signature is given.Τhe security of the scheme is discussed.

attribute signature scheme;conditions encryption scheme;dynamic;bilinear pairings

基于屬性的數(shù)字簽名方案能很好地實現(xiàn)用戶身份的隱藏。但所提出的簽名方案中,用戶屬性都是靜態(tài)的，當系統(tǒng)中的成員屬性發(fā)生變更后，沒有相應的修改機制，需要重新分配屬性密鑰，這將為系統(tǒng)增添極大負擔。在實際應用中存在問題?；跅l件加密的思想，設計了一個具有動態(tài)屬性的數(shù)字簽名方案，該方案能在該用戶滿足某屬性后，由認證方給用戶提供簽名，并讓用戶自行計算其屬性密鑰。對簽名方案的安全性進行了討論。

屬性簽名；條件加密；動態(tài)；雙線性對

A

ΤP309

10.3778/j.issn.1002-8331.1301-0232

廣東省自然科學基金（No.S2012010010376）；廣東省育苗項目（No.LYM11068）。

鄧宇喬（1980—），男，博士，主要從事密碼學，安全電子支付，數(shù)字版權(quán)管理系統(tǒng)方面的研究。E-mail：dengyuqiao80@yahoo.cn

2013-01-21

2013-05-09

1002-8331（2013）15-0019-04

CNKI出版日期：2013-05-15 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130515.1015.006.html