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

鄧宇喬

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

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

鄧宇喬

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

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

1 引言

基于屬性的數(shù)字簽名是由基于模糊身份簽名[1]的概念發(fā)展而來，機(jī)制更為靈活，其在精確（fine-grained）訪問控制的匿名認(rèn)證系統(tǒng)中發(fā)揮了重要的作用。在基于屬性的簽名體制中，用戶從屬性中心獲得一組屬性的私鑰，然后用這組屬性私鑰進(jìn)行簽名。簽名者的權(quán)力由其所擁有的屬性集合決定。驗(yàn)證者通過驗(yà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)性”。當(dāng)系統(tǒng)中的成員屬性發(fā)生變更后，沒有相應(yīng)的修改機(jī)制，需要重新分配屬性密鑰，這將為系統(tǒng)增添極大負(fù)擔(dān)。文獻(xiàn)[7]提出一種具有動態(tài)屬性的群簽名方案，但其方案主要為針對群簽名的特性提出的。本文借鑒條件密碼方案的思想[8-10]，給出一個具有動態(tài)屬性的一般數(shù)字簽名方案。在條件密碼機(jī)制中一段密文如需解密，需要滿足某個特定的條件，該條件由條件認(rèn)證方所認(rèn)證，如果不滿足條件，則解密者無法解密。如滿足特定條件，則除了可以解密出明文外，解密者還能得到條件認(rèn)證方的一個簽名。本文利用條件密碼的思想，對屬性簽名方案進(jìn)行改造，使得傳統(tǒng)的屬性簽名方案能在屬性擁有者滿足某種特定條件后可以申請動態(tài)增加其屬性密鑰，而其新增的屬性密鑰的控制權(quán)由條件認(rèn)證方所控制，這種思想的好處在于，其可以大大減輕屬性密鑰生成方的負(fù)擔(dān)，并且具有認(rèn)證的功能。隨后，本文在選擇集合模型[11-15]下證明了該方案的安全性。

2 背景知識介紹

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

定義1（訪問結(jié)構(gòu)）設(shè){P1，P2，…，Pn}是n個參與者的集合。設(shè)Λ表示由參與者集合的子集構(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)成的集合。設(shè)D表示參與者的任一子集，如果D∈Λ，則叫做授權(quán)集合，如果D?Λ則叫做非授權(quán)集合。

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

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

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

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

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

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

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

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

2.4 困難性假設(shè)

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

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

定義3（判定Diffie-Hellman假定（DBDH））該假定指的是：設(shè)(a，b，c，z∈Zp)，不存在多項(xiàng)式時間敵手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 方案定義

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

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

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

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

屬性密鑰提?。涸撍惴ń邮苷J(rèn)證方對用戶滿足某屬性的簽名SIG的輸入，還原該屬性的密鑰。

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

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

3.2 方案安全模型定義

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

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

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

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

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

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

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

3.3 方案描述

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

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

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

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

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

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

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

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

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

驗(yàn)證：驗(yàn)證過程分成以下步驟：

如果節(jié)點(diǎn)x為葉子節(jié)點(diǎn)，則計(jì)算：

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

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

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

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

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

4 方案安全性證明

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

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

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

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

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

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

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

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

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

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

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

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

PolyUnsat(Tx'，γ，)：如果x'不滿足條件，此時只知道的值（因?yàn)樵诖饲闆r下，事實(shí)上只知道的值）。

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

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

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

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

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

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

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

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

5 結(jié)論

基于屬性的數(shù)字簽名方案能很好地解決簽名者的身份隱私問題，但由于其屬性不具有“動態(tài)”的特性，導(dǎo)致了用戶在屬性遷移時的不便。本文利用“條件”的思想，把方案中的屬性改成動態(tài)的形式，當(dāng)用戶的屬性變遷后，他可以通過與認(rèn)證機(jī)構(gòu)的交互，自己計(jì)算出新增的屬性密鑰，從而較好地實(shí)現(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]陳少真，王文強(qiáng)，彭書娟.高效的基于屬性的環(huán)簽名方案[J].計(jì)算機(jī)研究與發(fā)展，2010，47（12）：2075-2082.

[12]孫昌霞，馬文平，陳和風(fēng).多授權(quán)中心的基于屬性的簽名[J].四川大學(xué)學(xué)報(bào)：工程科學(xué)版，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ù)字簽名方案能很好地實(shí)現(xiàn)用戶身份的隱藏。但所提出的簽名方案中,用戶屬性都是靜態(tài)的，當(dāng)系統(tǒng)中的成員屬性發(fā)生變更后，沒有相應(yīng)的修改機(jī)制，需要重新分配屬性密鑰，這將為系統(tǒng)增添極大負(fù)擔(dān)。在實(shí)際應(yīng)用中存在問題。基于條件加密的思想，設(shè)計(jì)了一個具有動態(tài)屬性的數(shù)字簽名方案，該方案能在該用戶滿足某屬性后，由認(rèn)證方給用戶提供簽名，并讓用戶自行計(jì)算其屬性密鑰。對簽名方案的安全性進(jìn)行了討論。

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

A

ΤP309

10.3778/j.issn.1002-8331.1301-0232

廣東省自然科學(xué)基金（No.S2012010010376）；廣東省育苗項(xiàng)目（No.LYM11068）。

鄧宇喬（1980—），男，博士，主要從事密碼學(xué)，安全電子支付，數(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