具有撤銷功能的基于身份的簽密方案

劉振華，俎龍輝，李娟娟

（1.西安電子科技大學數學與統計學院，陜西西安710071；2.桂林電子科技大學廣西信息科學實驗中心，廣西桂林541004）

具有撤銷功能的基于身份的簽密方案

劉振華1，2，俎龍輝1，李娟娟1

（1.西安電子科技大學數學與統計學院，陜西西安710071；2.桂林電子科技大學廣西信息科學實驗中心，廣西桂林541004）

為了有效解決簽密系統中撤銷用戶的問題，提出了具有撤銷功能的基于身份的簽密方案。方案將主密鑰隨機分布在初始密鑰和更新密鑰中，再隨機生成簽密密鑰，從而不僅能有效撤銷用戶，而且能抵抗密鑰泄露攻擊。在標準模型下，證明了該方案基于DBDH問題假設，具有不可區分性；基于CDH問題假設，具有不可偽造性。同時，任何第三方在不訪問明文的情況下，均可驗證簽密密文。

簽密；密鑰泄露；撤銷；可證明安全；公開可驗證

簽密是在一個操作中既簽名又加密，有效獲得數據機密性和不可否認性的一種密碼體制。簽密方案具有更短的密文和更小的計算開銷的優點。1997年，Zheng［1］首次提出簽密概念。

當使用密碼方案時，用戶密鑰丟失或泄露在所難免。在公鑰加密系統中，一種撤銷是通過文獻［2］的技術實現證書撤銷。在身份基加密系統中，Boneh等［3］指出要撤銷某個用戶，私鑰生成中心停止為其發布更新密鑰，并為其他用戶產生更新密鑰，這使得私鑰生成中心工作量和用戶數量成線性關系。之后Boldyreva等［4］提出利用二叉樹結構實現高效撤銷用戶的方案，使得私鑰生成中心更新次數僅為用戶數量的對數次。然而，安全性證明僅在選擇身份模型下實現的。在Boldyreva等的基礎上，Libert和Vergnaud［5］提出了完全身份下的解決方案。Seo等將撤銷功能推廣到分級加密情形［6］，并提出能夠抵抗密鑰泄露攻擊的加密方案［7］。鎖琰等［8］提出一種基于密鑰隔離的分布式群簽名方案，但是需要分布式協助器幫助群成員完成密鑰更新。另外，Tsai T.T.等［9］提出一個安全的具有可撤銷功能的基于身份簽名方案，并在標準模型下給出安全證明。

對基于身份的簽密方案，具有撤銷功能同樣十分重要。2012年，Wu T.Y.等［10］首次給出了可撤銷的基于身份的簽密（revocable identity based signcryp?tion，RIBSC）的形式化定義與安全模型，并提出具體的方案。然而，該方案是在隨機預言機模型下可證明安全的，在實際應用中卻存在一定的安全隱患，并且在密鑰生成過程中不具有隨機性。

1 RIBSC形式化定義與安全模型

1.1 形式化定義

為了有效撤銷用戶，抵抗密鑰泄露攻擊，本文在文獻［10］的RIBSC形式化定義中增加密鑰生成算法和撤銷算法，安全模型中增加了密鑰詢問，同時增加了有關密鑰詢問的限制條件。

可撤銷的基于身份簽密方案，包含以下算法：

1）Setup：輸入安全參數k和時間T。返回系統的公共參數mpk和主私鑰msk。

2）Initial Key extract：輸入主私鑰msk，身份ID。返回初始密鑰skID。

3）Key update：輸入主私鑰msk，身份ID和時間T，撤銷列表RL。若ID?RL。返回身份ID在時間T的更新密鑰kuT。反之，身份ID已經被撤銷，返回⊥。

4）（Un）Signcryption Key generate：輸入身份ID在時間T的初始密鑰skID，更新密鑰kuT。返回（解）簽密密鑰dkID，T或⊥（當ID∈RL時）。

5）Signcrypt：輸入消息M，時間T，發送者身份IDA，接收者身份IDB。返回密文CT。

6）Unsigncrypt：輸入密文CT，時間T，發送者身份IDA，接收者身份IDB。返回解簽密密鑰dkID，T和消息M'或⊥（當CT是無效密文時）。

7）Revoke：輸入要撤銷的身份ID和時間T，撤銷列表RL。返回在時間T更新后的撤銷列表RL。

1.2 安全模型

定義1 不可區分性（IND?CCA2）對于一個可撤銷的基于身份的簽密方案，如果不存在任何概率多項式數量級界的敵手A，可以以一個不可忽略的優勢在以下的游戲中獲勝，那么該方案具有適應性選擇密文攻擊下不可區分性。

Setup：挑戰者B執行Setup算法，獲得系統公共參數mpk和主私鑰msk。將mpk發送給敵手A，自己保存msk。

第1階段 敵手A執行適應性的多項式數量級界的以下詢問：

1）Initial Key extract詢問：A選擇身份ID。B計算初始密鑰skID，發給A。

2）Key update詢問：A選擇身份ID和時間T。B計算未撤銷用戶的更新密鑰kuT，發給A。反之，若用戶已經被撤銷，返回⊥。

3）（Un）Signcryption Key generate詢問：A選擇用戶的初始密鑰skID，更新密鑰kuT。B計算未撤銷用戶的（解）簽密密鑰dkID，T，發給A。

4）Signcrypt詢問：A選擇消息M，時間T，發送者IDA，接收者IDB。B計算密文CT，發給A。

5）Unsigncrypt詢問：A選擇密文CT，時間T，發送者IDA，接收者IDB。B計算消息M'，發給A。

挑戰階段 由A決定第1階段何時結束。當結束后選擇等長的消息，時間T?，挑戰的發送者身份，接收者身份發送給B。其中不能在第1階段出現過。B隨機選取γ∈{0，1}，運行Signcrypt算法，將密文CT?，發給敵手A。

第2階段 在A接收到B給的密文CT?后，仍可以進行與第1階段相似的多項式數量級界的詢問，但是要滿足一定的條件。

猜測 最后，A輸出γ'，若γ＝γ'，敵手獲勝。

定義2 不可偽造性（EUF?CMA）對于一個可撤銷的簽密方案，如果不存在任何概率多項式數量級界的敵手A，可以以一個不可忽略的優勢在以下的游戲中獲勝，那么該方案具有適應性選擇消息攻擊下存在性不可偽造性。

Setup：與IND?CCA2游戲中初始化過程相似。

第1階段 敵手A執行與IND?CCA2游戲定義中相似的多項式數量級界的詢問。

偽造階段 敵手A輸出對于挑戰（m?，T?，ID?A，ID?B）的一個新的密文CT?。當下列條件滿足時，稱敵手在該游戲中獲勝。

①偽造的CT?是對一個合法密文。

1.3 困難假設

定義3 DBDH問題令G，GT是大素數p階循環群，g是群G的生成元，給定（g，ga，gb，gc）∈G4和T∈GT其中a，b，c∈Zp?未知。G上的DBDH問題是判斷是否有T＝e（g，g）abc。若任意概率多項式時間算法A解決DBDH問題的優勢可忽略，則稱群G上的DBDH困難問題假設成立。

定義4 CDH問題令G是大素數p階循環群，g是該群的生成元，給定（g，ga，gb）∈G3，其中a，b∈未知。G上的CDH問題是計算gab∈G。若任意概率多項式時間算法A解決CDH問題優勢可忽略，則群G上的CDH困難問題假設成立。

2 新的RIBSC具體構造

1）Setup 階為素數p的乘法循環群G、GT，大小由安全參數k決定，g是群G的生成元，雙線性對映射e：G×G→GT，隨機選取，g2、h1、h2、h3、u'、u″、v'、v″、m'、ui、vi、mi←G，并計算g1＝gα、。向量U＝(ui)、V＝(vi)、M＝(mi)，長度分別為nu、nu、l。4個哈希函數H1：GT×{0，1}l，。輸出mpk＝（G，GT，e＾，Hi，hj，g，g1，g2，u'，u″，v'，v″，U，V，M）msk＝（，其中i＝1，2，3，4，j＝1，2，3。nu為身份和時間的比特串長度。nm為消息比特串長度。

2）initial key extract 輸入主私鑰msk，身份ID。隨機選取，使得ID[ i]表示ID的第i比特。是使得ID[ i]＝1索引i的集合。

初始私鑰為

3）key update 輸入主私鑰msk，身份ID，時間T。對于時間T內的任意身份，若ID?RL，隨機選取，并計算，T[ i]表示T的第i比特，定義是使得T[ i]＝1的索引i的集合。更新密鑰為

4）（Un）signcryption key generate 輸入（ID，T）的初始密鑰skID，更新密鑰kuT。隨機選取r1，，計算：

所以（解）簽密密鑰為

5）signcrypt 發送者以身份IDA和時間T執行以上2）、3）、4）算法獲得簽密密鑰dkIDA，T。隨機選取其中lτ為整數，對消息m計算：

6）unsigncrypt 當IDB收到密文CT后：

①計算λ＝H3(σ1)，β＝H2(σ4，IDA，τ)，ρ＝H4(σ2，σ3，IDB，)。

②驗證密文CT是否滿足等式：

若（1）不成立，則CT是無效的密文，輸出⊥。若等式（1）成立，則

a）計算IDB在時間T的解簽密密鑰

7）revoke 輸入時間T和要撤銷的身份ID，撤銷列表RL。返回更新后的撤銷列表RL。

3 安全性證明

定理1 （IND?RIBSC?CCA2）如果對于任何敵手只允許進行qc次初始密鑰詢問，qg次更新密鑰詢問，qj次簽密密鑰詢問，qs次簽密詢問，qus次解簽密詢問，在概率多項式時間t內，最多具有ε的優勢攻破所提出的方案的安全性，那么存在概率多項式時間t'的算法以ε'的優勢解決DBDH問題：

Setup 模擬器B令lu＝2（qc+qg+qj）。因為在密鑰提取詢問終止的情況下，簽密和解簽密也不會終止，所以qs、qus是無限制條件的。B隨機選取整數ku，0≤ku≤nu。假設lunu+1()＜p，隨機選取x'，x″，xi←Zlu，y'，y″，yi←Zp，2個向量X＝（xi），Y＝（yi）長度均為nu。ID和T的函數：

為nu，nm。計算：

第1階段

1）initial key extract詢問：由于B不知道主密鑰ha2，A以身份ID詢問B時，隨機選取r←Z?p，gθ，hθ←G。按內外敵手如下計算：

①外部敵手時，若F1(ID)＝0( modp)，則輸出⊥。

②內部敵手時，計算skID＝(skID，1，skID，2，skID，3)＝

2）key update詢問：當A以（ID，T）詢問B時，若ID?RL，B根據上述選定的gθ、hθ，計算，隨機選取，如下計算：

①外部敵手時，計算kuT＝（kuT，1，kuT，2，kuT，3）＝

②內部敵手時，若F2T()＝0 modp()，則輸出⊥。

否則，計算kuT＝（kuT，1，kuT，2，kuT，3）。

其中，s'＝s-a／F2T()。

3）（Un）signcryption key generate詢問：當A以（ID，T）的初始密鑰skID，更新密鑰kuT向B詢問時，B運行此算法，獲得（解）簽密密鑰dkID，T。

4）signcrypt詢問：當A以(m，T，IDA，IDB)向B詢問時，B隨機選取，τ←{0，1}lτ，lτ為整數。

①計算σ1＝gt，σ2＝H1(e( g1，h2)t，τ)⊕m，

5）unsigncrypt詢問：A以(CT，T，IDA，IDB)向 B進行詢問時，B首先驗證等式（1）是否成立，若不成立，則輸出⊥。否則，按內外敵手如下計算：

①外部敵手時，若F1IDB()≠0 modp()，運行Unsigncrypt算法恢復出明文。

②內部敵手時，若F2T()≠0 modp()，運行Un?signcrypt算法恢復出明文。

否則，當F1IDB()＝0 modp()，F2T()＝0 modp()時，計算：

m＝σ2⊕H1(e( Δ?，h2)，τ)＝σ2⊕H1(e( g1，h2)t，τ)

挑戰階段。

計算

第2階段 敵手A可以進行與第1階段相似的詢問，但是要滿足定義1中的限制條件。

猜測A 輸出對γ的猜測γ'，若γ'＝γ，則B輸出1，意味著T＝e g，g()abc。否則輸出0。

運用類似文獻［9，11］的方法，B作為敵手A的挑戰者，通過調用A解決DBDH困難問題的優勢為

定理2 （EUF?RIBSC?CMA）如果對于任何敵手只允許進行qc次初始密鑰詢問，qg次更新密鑰詢問，qj次簽密密鑰詢問，qs次簽密詢問，qus次解簽密詢問，在概率多項式時間t內最多具有ε的優勢攻破所提方案的安全性，那么存在概率多項式時間t'的算法B以ε'的優勢解決CDH問題：

證明 可參照定理1的證明得證。

4 效率分析與公開可驗證性

4.1 效率分析

表1列出了本文方案與文獻［10?11］方案計算效率和安全性比較。文獻［10］中的方案是在隨機預言機模型下可證明安全的。雖然具有高效率，但是不能保證方案的實際安全性。與文獻［11］中的方案相比，本文方案簽密運算多1個指數運算，解簽密運算多2個雙線性對運算，但本文方案具有撤銷功能。因此，本文方案增加了計算量，但達到了更高的安全性。表中+1()Tp表示簽密算法中的雙線性對e( g1，h2)t運算的次數，Te表示一次指數運算。

表1 計算效率與安全性比較Table 1 Comparison of computation and security

4.2 公開可驗證性

在如今開放網絡上的通信、電子商務、電子政務等實際應用中簽密文的公開驗證是必不可少的。在解簽密驗證過程中，對于所有接收到密文CT的合法用戶來說無需解密就可以直接驗證方程（1）是否成立。因為由mpk可以得到（g，g1，g2，u'，u″，m'， U，M，h1，h3），由CT可以得到(σ1，σ4，σ5，σ6)和(λ，β，ρ)。因此方案的簽名滿足公開可驗證性。

5 結論

本文改進了文獻［10］中RIBSC的形式化定義與安全模型，并基于Selvi［11］的簽密方案，構造出一種可以有效抵抗密鑰泄露攻擊的新RIBSC方案。在標準模型下，證明了新方案具有IND?CCA2和EUF?CMA安全性。此外，所提方案又能保證在不訪問明文的情況下，任何第三方都可以對密文進行公開驗證，達到了簽密在電子商務、電子政務等實際應用中公開驗證的要求。然而，所提方案計算復雜度與用戶數量成線性關系，下一步研究工作重點是對其進行效率提高。

［1］ZHENG Y L.Digital signcryption or how to achieve cost（sig?nature and encryption）＜＜cost（signature）+cost（encryp?tion）［C］／／Advances inCryptology—CRYPTO'97.Berlin：Springer，1997：165?179.

［2］GOYAL V.Certificate revocation using fine grained certifi?cate space partitioning［C］／／Financia Cryptography and Da?ta Security.Berlin：Springer，2007：247?259.

［3］BONEH D，FRANKLIN M.Identity?based encryption from the weil pairing［C］／／Advances in Cryptology?CRYPTO 2001.Berlin：Springer，2001：213?229.

［4］BOLDREVA A，GOYAL V，KUMER V.Identity?based en?cryption with efficient revocation［C］／／Proceedings of the 15th ACM Conference on Computer and Communications Se?curity.Berlin：Springer，2008：417?426.

［5］LIBERT B，VERGNAUD D.Adaptive?ID secure revocable identity?based encryption［C］／／Topics in Cryptology?CT?RSA2009.Berlin：Springer，2009：1?15.

［6］SEO J H，EMURA K.Efficient delegation of keygeneration and revocation functionalities in identity?based encryption［C］／／Topics in Cryptology-CTRSA 2013.Berlin：Spring?er，2013：343?358.

［7］SEO J H，EMURA K.Revocable identity?based encryption revisited：security model and construction［C］／／Public?Key Cryptography?PKG2013.Berlin：Springer，2013：216?234.

［8］鎖琰，李曉輝，徐小巖，等.一種安全的分布式群簽名方案［J］.哈爾濱工程大學學報，2011，32（12）：1594?1623.SUO Yan，LI Xiaohui，XU Xiaoyan，et al.A secure distribu?ted group signature scheme［J］.Journal of Harbin Engineer?ing University，2011，32（12）：1594?1623.

［9］TSAI T T，TSENG Y M，WU T Y.Provably secure revoca?ble ID?based signature in the standard model［J］.Security and Communication Networks，2013，6（6）：669?796.

［10］WU T Y，TSAI T T，TSENG Y M.A revocable ID?based signcryption scheme［J］.Information Hiding and Multi?media Signal Processing，2012，3（3）：240?251.

［11］SELVI S S D，VIVEK S S，VINAYAGAMURTHY D，et al.ID based signcryption scheme in standard model［C］／／Provable Security.Berlin：Springer，2012：35?52.

Identity?based signcryption with the revocation function

LIU Zhenhua1，2，ZU Longhui1，LI Juanjuan1

（1.School of Mathematics and Statistics，Xidian University，Xi'an 710071，China；2.Guangxi Experiment Center of Information Sci?ence，Guilin University of Electronic Technology，Guilin 541004，China）

An identity?based signcryption scheme with revocation is proposed in order to solve the problem of revo?king users in the signcryption system.In this scheme，the master key is randomly distributed in the initial key and update key，which are used to generate the signcryption key randomly.Thus，the proposed scheme can revoke users effectively as well as resist key compromise attack.In the standard model，the scheme is proven to be indistinguish?able and unforgettable against adaptive chosen ciphertext attacks and adaptive chosen message attacks under deci?sional bilinear Diffie?Hellman assumption and computational Diffie?Hellman assumption，respectively.Furthermore，any third party can verify the ciphertext without accessing plaintext.

signcryption；key compromise；revocation；provable security；public ciphertext verifiability

10.3969／j.issn.1006?7043.201401033

TN 918.1

：A

：1006?7043（2015）02?0856?05

http：／／www.cnki.net／kcms／detail／23.1390.U.20150428.0928.015.html

2014?01?12.網絡出版時間：2015?04?28.

國家自然科學基金資助項目（61472470，61100229）；陜西省自然科學基金資助項目（2014JM2?6091，2015JQ1007）；廣西信息科學實驗中心經費資助（20130201）.

劉振華（1978?），男，副教授，博士；俎龍輝（1987?），女，碩士研究生.

俎龍輝，E?mail：sdjnlonghui＠126.com.