基于橢圓曲線的高效無證書環(huán)簽名方案

朱秀萍，劉亞麗*，林昌露，李濤，董永權(quán)

基于橢圓曲線的高效無證書環(huán)簽名方案

朱秀萍1，2，3，劉亞麗1，2，3*，林昌露2，李濤1，2，3，董永權(quán)1

（1.江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116； 2.福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室（福建師范大學(xué)），福州 350117； 3.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西 桂林 541004）（ ? 通信作者電子郵箱liuyali@jsnu.edu.cn）

環(huán)簽名具有自發(fā)性和匿名性，被廣泛用于解決用戶身份和數(shù)據(jù)隱私泄露問題；而無證書公鑰密碼體制不僅可以解決密鑰托管問題，還不需要公鑰證書的管理；無證書環(huán)簽名則結(jié)合了上述兩者的優(yōu)點(diǎn)，具有廣泛的研究意義，但現(xiàn)有大多數(shù)無證書環(huán)簽名方案基于雙線性配對運(yùn)算和模指數(shù)運(yùn)算，計(jì)算成本高、效率低。為了提高簽名階段和驗(yàn)證階段的效率，提出一種新的基于橢圓曲線的高效無證書環(huán)簽名（ECL-RS）方案，使用了計(jì)算代價(jià)低、安全性高、靈活性好的橢圓曲線。該方案的安全性規(guī)約為離散對數(shù)困難問題和Diffie-Hellman問題，且在隨機(jī)預(yù)言機(jī)模型（ROM）下證明了它能夠抵抗公鑰替換攻擊和惡意密鑰生成中心攻擊，具有不可偽造性和匿名性。性能分析表明，ECL-RS方案只需（+2）（表示為環(huán)成員個(gè)數(shù)）次橢圓曲線標(biāo)量乘法和標(biāo)量加法運(yùn)算，以及（+3）次單向哈希運(yùn)算，在保證安全的情況下具有較低的計(jì)算代價(jià)和更高的效率。

環(huán)簽名；橢圓曲線；無證書環(huán)簽名；高效性；隨機(jī)預(yù)言機(jī)模型

0 引言

環(huán)簽名在2001年由Rivest等［1］首次提出，因按照一定規(guī)律首尾相連組成一個(gè)環(huán)狀結(jié)構(gòu)而得名。在環(huán)簽名方案中，簽名者可以任意選擇幾個(gè)成員組成一個(gè)環(huán)，沒有群的建立過程，也沒有群管理者，在沒有其他環(huán)成員幫助的情況下生成簽名。驗(yàn)證者使用公鑰驗(yàn)證生成的簽名是否由環(huán)中成員所產(chǎn)生，但是卻無法確定簽名是由環(huán)中哪個(gè)成員所產(chǎn)生。環(huán)簽名有兩個(gè)獨(dú)特的性質(zhì)：自發(fā)性和匿名性［1］。自發(fā)性允許簽名者在沒有任何其他小組成員的幫助或合作的情況下生成一個(gè)環(huán)簽名；匿名性意味著環(huán)簽名可以在不暴露實(shí)際簽名者身份的情況下被驗(yàn)證。因此，環(huán)簽名獨(dú)有的自發(fā)性、匿名性以及靈活的結(jié)構(gòu)等特性被廣泛用于解決用戶身份和數(shù)據(jù)隱私保護(hù)問題。

1976年，Diffie和Hellman［2］第一次提出了公鑰密碼學(xué)（Public Key Cryptography， PKC）的概念。傳統(tǒng)的公鑰基礎(chǔ)設(shè)施（Public Key Infrastructure， PKI）［3］需要一個(gè)受信任的第三方證書頒發(fā)機(jī)構(gòu)為每個(gè)用戶頒發(fā)一個(gè)綁定用戶身份和公鑰的證書。Shim［4］提出了一個(gè)只需常數(shù)個(gè)雙線性配對操作的環(huán)簽名方案，在co-Diffifie-Hellman假設(shè)下，使用隨機(jī)預(yù)言機(jī)模型（Random Oracle Model， ROM）證明了方案的安全性，并選擇Barreto-Naehrig曲線上的最優(yōu)配對來研究方案的性能；但方案需要證書管理開銷和高計(jì)算代價(jià)的雙線性配對，導(dǎo)致效率并不理想。張文芳等［5］提出了一個(gè)基于大整數(shù)分解難題和RSA公鑰密碼體制的環(huán)簽名方案。該方案通過隨機(jī)選擇參數(shù)生成關(guān)聯(lián)標(biāo)簽，使方案滿足強(qiáng)匿名性，并在一定條件下可轉(zhuǎn)換成普通數(shù)字簽名。但在傳統(tǒng)PKI的簽名方案中，成員證書的傳輸和驗(yàn)證涉及相當(dāng)多的通信和計(jì)算成本，因此效率低。從上述分析可以得出傳統(tǒng)PKI不僅效率低還會帶來證書管理問題，因?yàn)轵?yàn)證者必須檢查每個(gè)用戶證書的有效性，證書的管理在計(jì)算時(shí)間和存儲空間方面要求非常高，使得簽名方案復(fù)雜且效率低。

為了解決證書管理問題，Shamir［6］在1984年引入了基于身份的公鑰密碼學(xué)（IDentity Based-Public Key Cryptography， IDB-PKC）。在IDB-PKC中，所有用戶的私鑰都是由一個(gè)被稱為私鑰生成器（Private-Key Generator， PKG）的可信第三方產(chǎn)生。Wang等［7］提出了一種新的基于身份的可引用環(huán)簽名方案，將環(huán)簽名方案擴(kuò)展為可引用的，任何人都可以從原始消息產(chǎn)生的環(huán)簽名中推導(dǎo)出消息子串產(chǎn)生新的簽名。該方案基于復(fù)合階的雙線性配對，證明了在子群決策困難問題假設(shè)下是匿名的，并在Diffie-Hellman困難問題假設(shè)下，針對ROM中自適應(yīng)選擇的消息攻擊是不可偽造的。Au等［8］基于標(biāo)準(zhǔn)模型提出了一種安全且不受限制的基于身份的環(huán)簽名方案。該方案在標(biāo)準(zhǔn)模型下證明了它的構(gòu)造是安全的，并根據(jù)環(huán)簽名中超級匿名性的定義方法，定義了一個(gè)新的基于身份的環(huán)簽名的匿名級別，在此級別中，敵手可以指定用于創(chuàng)建用戶密鑰的隨機(jī)性。趙艷琦等［9］采用對偶系統(tǒng)加密技術(shù)提出了一種基于身份的環(huán)簽名方案。該方案結(jié)合了合數(shù)階群上的雙線性運(yùn)算的正交性，從而將安全性規(guī)約為計(jì)算Diffie-Hellman困難問題。上述基于身份的環(huán)簽名方案解決了PKI中證書管理問題，但是又存在新的密鑰托管問題，因?yàn)镻KG掌握著所有實(shí)體的密鑰，有能力對所有實(shí)體間的通信進(jìn)行監(jiān)聽或偽造。

為了解決上述兩個(gè)問題，2003年Al-Riyami和Paterson［10］引入了無證書公鑰密碼學(xué)（CertificateLess Public Key Cryptography， CL-PKC）的概念。在CL-PKC中，用戶的私鑰由密鑰生成中心（Key Generation Center， KGC）生成的部分私鑰和用戶自己選擇的秘密值兩部分組成。因此，即使惡意KGC泄露了KGC產(chǎn)生的部分私鑰，攻擊者也無法獲得整個(gè)私鑰來進(jìn)行攻擊。通過這種方式，CL-PKC不僅消除了ID-PKC系統(tǒng)中的密鑰托管問題，也解決了PKI系統(tǒng)中的證書管理問題。Yuan等［11］提出了一個(gè)基于雙線性映射的無證書閾值簽名方案，但該方案在簽名階段需要（1）次雙線性配對，因此，當(dāng)相對較大時(shí)，簽名階段的計(jì)算開銷相當(dāng)高。張福泰等［12］對無證書加密、簽名、密鑰協(xié)商、簽密等方面進(jìn)行了總結(jié)，指出現(xiàn)有大多數(shù)方案都存在安全模型不合理、證明不嚴(yán)謹(jǐn)、有安全缺陷等問題。Karati等［13］在工業(yè)物聯(lián)網(wǎng)環(huán)境下提出了一種基于雙線性配對的無證書簽名方案。在該方案中，簽名者需執(zhí)行兩次指數(shù)運(yùn)算，驗(yàn)證者執(zhí)行一次雙線性配對和兩次指數(shù)運(yùn)算，因此計(jì)算代價(jià)相對較大。然而，Zhang等［14］在方案［13］的基礎(chǔ)上進(jìn)行了改進(jìn)，提出一種更輕量高效的基于橢圓曲線的無證書簽名方案。并分析了四種類型的簽名偽造攻擊，證明了方案［13］無法實(shí)現(xiàn)所聲稱的安全特性。

綜上所述，現(xiàn)有大多數(shù)環(huán)簽名方案都存在以下問題：

1）證書管理和密鑰托管問題?；趥鹘y(tǒng)PKI和基于IDB-PKC的簽名方案分別存在證書管理問題和密鑰托管問題。

2）計(jì)算代價(jià)高?，F(xiàn)有大多數(shù)環(huán)簽名方案使用了高計(jì)算代價(jià)的雙線性配對運(yùn)算和模指數(shù)操作，計(jì)算代價(jià)高、效率低。

3）易遭受各種惡意攻擊。沒有考慮惡意KGC的攻擊，KGC產(chǎn)生部分密鑰，有能力對所有實(shí)體進(jìn)行監(jiān)聽、偽造等，惡意用戶也可以自行對實(shí)體的公鑰進(jìn)行替換攻擊。

為了解決上述問題，本文提出了一種新的基于橢圓曲線的高效無證書環(huán)簽名（Efficient CertificateLess Ring Signature， ECL-RS）方案，主要工作如下：

1）提出了一種新的基于橢圓曲線的高效無證書環(huán)簽名方案，在不需要公鑰證書的同時(shí)有效解決了密鑰托管問題，具有自發(fā)性和匿名性，可保護(hù)用戶身份和數(shù)據(jù)隱私性。

2）本文方案的安全性基于橢圓曲線離散對數(shù)問題和Diffie-Hellman問題，在隨機(jī)預(yù)言機(jī)模型下證明了ECL-RS方案在公鑰替換攻擊和惡意KGC攻擊下是不可偽造的，并具有正確性和匿名性等屬性。

3）本文方案沒有使用計(jì)算代價(jià)較高的雙線性配對和指數(shù)操作，而是基于計(jì)算代價(jià)低、安全性高、靈活性好的橢圓曲線，與現(xiàn)有相關(guān)無證書環(huán)簽名方案相比，ECL-RS方案具有較低的計(jì)算成本和更高的效率。

1 預(yù)備知識

本章主要介紹相關(guān)的數(shù)學(xué)基礎(chǔ)理論。

1.1　橢圓曲線密碼

ECC的密鑰長度小，加密的文本和簽名長度也小。此外，能更快地生成密鑰，快速地簽名和加解密，在硬件設(shè)備中能更快地獲得橢圓曲線。

1.2　橢圓曲線離散對數(shù)問題

1.3　計(jì)算Diffie-Hellman問題

2 無證書環(huán)簽名方案

本章主要對無證書環(huán)簽名方案中的參數(shù)符號及其含義、無證書環(huán)簽名方案的形式化定義及其安全模型進(jìn)行介紹。

2.1　符號定義

本文所涉及到的相關(guān)符號說明如表1所示。

表1　符號說明

2.2　無證書環(huán)簽名方案的形式化定義

2.3　無證書環(huán)簽名方案的安全模型

若方案滿足以下性質(zhì)，則稱環(huán)簽名方案是安全的。

3）不可偽造性：考慮惡意用戶（敵手Ⅰ）和惡意KGC（敵手Ⅱ）兩種類型的攻擊方法。

Ⅰ型敵手：敵手1無法訪問系統(tǒng)主密鑰，但敵手1可以用隨機(jī)選擇的整數(shù)來替換環(huán)中用戶的公鑰，因?yàn)闆]有公鑰證書來保證用戶公鑰的真實(shí)性和有效性，此種攻擊稱為公鑰替換攻擊。

Ⅱ型敵手：敵手2能夠訪問系統(tǒng)主密鑰，但敵手2不能獲得任何用戶的秘密值和私鑰，也不能替換用戶的公鑰，此種攻擊稱為惡意KGC攻擊。

游戲Ⅰ 在Ⅰ型敵手1和挑戰(zhàn)者之間進(jìn)行交互，詳細(xì)步驟如下。

查詢 敵手1執(zhí)行多項(xiàng)式有限次查詢，每次查詢可能依賴于之前的查詢結(jié)果。

游戲Ⅱ 在敵手2和挑戰(zhàn)者之間進(jìn)行交互，詳細(xì)步驟如下：

查詢2進(jìn)行多項(xiàng)式有界次查詢，查詢操作同游戲Ⅰ中所述，返回與游戲Ⅰ中一致的響應(yīng)。但是，2可以使用系統(tǒng)主密鑰自行計(jì)算任何用戶的部分私鑰。

3 ECL?RS方案

圖1　ECL-RS方案流程

4 ECL?RS方案安全性分析

定理1 ECL-RS方案具備正確性。

定理2 ECL-RS方案具備匿名性。

定理3 ECL-RS方案具備不可偽造性。

查詢

查詢

用戶公鑰替換：同游戲Ⅰ的用戶公鑰替換。

環(huán)簽名查詢：同游戲Ⅰ的環(huán)簽名查詢。

5 ECL?RS方案性能分析

本章將ECL-RS方案與現(xiàn)有文獻(xiàn)［7，18-21］中的部分無證書環(huán)簽名方案進(jìn)行比較。一般情況下，由于普通加減法和隨機(jī)選擇整數(shù)等操作運(yùn)行時(shí)間少，可以忽略不計(jì)，因此僅針對以下幾種操作的運(yùn)行時(shí)間進(jìn)行比較。使用MIRACL庫在華為i5-1135G7處理器，主頻2.40 GHz，16 GB內(nèi)存和Windows 10操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行以下密碼運(yùn)算的運(yùn)行時(shí)間如表2所示。

表2　密碼符號表示及運(yùn)算時(shí)間

表3　六種方案的計(jì)算代價(jià)對比（n=10） 單位： ms

6 結(jié)語

本文提出了一種新的基于橢圓曲線的高效無證書環(huán)簽名方案ECL-RS。該方案采用了安全性高、密鑰短、加密快、運(yùn)算量小且靈活性好的橢圓曲線以降低計(jì)算開銷，具有良好性能。ECL-RS方案的安全性依賴于ECDLP問題和CDH問題，在隨機(jī)預(yù)言機(jī)模型下證明了本方案能夠抵抗Ⅰ/Ⅱ型攻擊，具有匿名性、不可偽造性等安全屬性。性能分析表明，與現(xiàn)有相關(guān)環(huán)簽名方案相比，ECL-RS方案在確保安全性的情況下效率更高，更加適用于輕量級物聯(lián)網(wǎng)應(yīng)用場景。

[1] RIVEST R L， SHAMIR A， TAUMAN Y. How to leak a secret［C］// Proceedings of the 2001 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 2248. Berlin： Springer， 2001： 552-565.

[2] DIFFIE W， HELLMAN M. New directions in cryptography［J］. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654.

[3] GUTMANN P. PKI： it’s not dead， just resting［J］. Computer， 2002， 35（8）： 41-49.

[4] SHIM K A. An efficient ring signature scheme from pairings［J］. Information Sciences， 2015， 300： 63-69.

[5] 張文芳，熊丹，王小敏，等. 基于RSA公鑰密碼體制的可選擇可轉(zhuǎn)換關(guān)聯(lián)環(huán)簽名［J］. 計(jì)算機(jī)學(xué)報(bào)， 2017， 40（5）：1168-1180.（ZHANG W F， XIONG D， WANG X M， et al. Selectively linkable and convertible ring signature based on RSA public key cryptosystem［J］. Chinese Journal of Computers， 2017， 40（5）： 1168-1180.）

[6] SHAMIR A. Identity-based cryptosystems and signature schemes［C］// Proceedings of the 1984 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 196. Berlin： Springer， 1985： 47-53.

[7] WANG K， MU Y， SUSILO W. Identity-based quotable ring signature［J］. Information Sciences， 2015， 321： 71-89.

[8] AU M H， LIU J K， SUSILO W， et al. Realizing fully secure unrestricted ID-based ring signature in the standard model based on HIBE［J］. IEEE Transactions on Information Forensics and Security， 2013， 8（12）： 1909-1922.

[9] 趙艷琦，來齊齊，禹勇，等. 標(biāo)準(zhǔn)模型下基于身份的環(huán)簽名方案［J］. 電子學(xué)報(bào)， 2018， 46（4）： 1019-1024.（ZHAO Y Q， LAI Q Q， YU Y， et al. ID-based ring signature in the standard model［J］. Acta Electronica Sinica， 2018， 46（4）： 1019-1024.）

[10] AL-RIYAMI S S， PATERSON K G. Certificateless public key cryptography［C］// Proceedings of the 2003 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 2894. Berlin： Springer， 2003： 452-473.

[11] YUAN H， ZHANG F， HUANG X， et al. Certificateless threshold signature scheme from bilinear maps［J］. Information Sciences， 2010， 180（23）： 4714-4728.

[12] 張福泰，孫銀霞，張磊，等. 無證書公鑰密碼體制研究［J］. 軟件學(xué)報(bào)， 2011， 22（6）： 1316-1332.（ZHANG F T， SUN Y X， ZHANG L， et al. Research on certificateless public key cryptography［J］. Journal of Software， 2011， 22（6）： 1316-1332.）

[13] KARATI A， ISLAM S H， KARUPPIAH M. Provably secure and lightweight certificateless signature scheme for IIoT environments［J］. IEEE Transactions on Industrial Informatics， 2018， 14（8）： 3701-3711.

[14] ZHANG Y， DENG R H， ZHENG D， et al. Efficient and robust certificateless signature for data crowdsensing in cloud-assisted industrial IoT［J］. IEEE Transactions on Industrial Informatics， 2019， 15（9）： 5099-5108.

[15] KOBLITZ N. Elliptic curve cryptosystems［J］. Mathematics of Computation， 1987， 48（177）： 203-209.

[16] BONEH D， BOYEN X. Short signatures without random oracles［C］// Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 3027. Berlin： Springer， 2004： 56-73.

[17] POINTCHEVAL D， STERN J. Security proofs for signature schemes［C］// Proceedings of the 1996 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 1070. Berlin： Springer， 1996： 387-398.

[18] BOUAKKAZ S， SEMCHEDINE F. A certificateless ring signature scheme with batch verification for applications in VANET［J］. Journal of Information Security and Applications， 2020， 55： No.102669.

[19] YU H， WANG W. Certificateless network coding ring signature scheme［J］. Security and Communication Networks， 2021， 2021： No.8029644.

[20] ZHANG Y， ZENG J， LI W， et al. A certificateless ring signature scheme with high efficiency in the random oracle model［J］. Mathematical Problems in Engineering， 2017， 2017： No.7696858.

[21] WANG Z， FAN J. Flexible threshold ring signature in chronological order for privacy protection in edge computing［J］. IEEE Transactions on Cloud Computing， 2022， 15（9）： 1253-1261.

Efficient certificateless ring signature scheme based on elliptic curve

ZHU Xiuping1，2，3， LIU Yali1，2，3*， LIN Changlu2， LI Tao1，2，3， DONG Yongquan1

（1，，221116，；2（），350117，；3（），541004，）

Ring signature is widely used to solve the problems of user identity and data privacy disclosure because of its spontaneity and anonymity； and certificateless public key cryptosystem can not only solve the problem of key escrow， but also do not need the management of public key certificates； certificateless ring signature combines the advantages of both of the above mentioned， and has extensive research significance， but most of the existing certificateless ring signature schemes are based on the calculation of bilinear pairings and modular exponentiation， which are computationally expensive and inefficient. In order to improve the efficiency of signature and verification stages， a new Efficient CertificateLess Ring Signature （ECL-RS） scheme was proposed， which used elliptic curve with low computational cost， high security and good flexibility. The security statute of ECL-RS scheme stems from a discrete logarithm problem and a Diffie-Hellman problem， and the scheme is proved to be resistant to public key substitution attacks and malicious key generation center attacks under Random Oracle Model （ROM） with unforgeability and anonymity. Performance analysis shows that ECL-RS scheme only needs （+2） （is the number of ring members） elliptic curve scalar multiplication and scalar addition operations as well as （+3） one-way hash operations， which has lower computational cost and higher efficiency while ensuring security.

ring signature; elliptic curve; certificateless ring signature; efficiency; Random Oracle Model (ROM)

1001-9081（2023）11-3368-07

10.11772/j.issn.1001-9081.2022111801

2022?11?04；

2023?01?04；

國家自然科學(xué)基金資助項(xiàng)目（61702237）； 徐州市科技計(jì)劃項(xiàng)目（KC22052）； 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室（福建師范大學(xué)）開放課題（NSCL?KF2021?04）； 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)）研究課題（GCIS202114）； 江蘇師范大學(xué)研究生科研與實(shí)踐創(chuàng)新計(jì)劃項(xiàng)目（2021XKT1396）； 教育部產(chǎn)學(xué)合作協(xié)同育人項(xiàng)目（202101374001）。。

朱秀萍（1997—），女，四川內(nèi)江人，碩士研究生，CCF會員，主要研究方向：公鑰密碼學(xué)、數(shù)字簽名、物聯(lián)網(wǎng)隱私保護(hù)； 劉亞麗（1981—），女，江蘇徐州人，教授，博士，CCF高級會員，主要研究方向：信息安全、認(rèn)證和隱私保護(hù)、區(qū)塊鏈、車載自組織網(wǎng)絡(luò)、密碼算法和協(xié)議； 林昌露（1978—），男，福建大田人，教授，博士生導(dǎo)師，博士，CCF會員，主要研究方向：密碼學(xué)、網(wǎng)絡(luò)安全、秘密共享、安全多方計(jì)算、公鑰密碼學(xué)； 李濤（1998—），男，湖北黃岡人，碩士研究生，主要研究方向：無線射頻識別認(rèn)證、隱私保護(hù)、物聯(lián)網(wǎng)安全、區(qū)塊鏈； 董永權(quán)（1979—），男，江蘇宿遷人，教授，博士，CCF會員，主要研究方向：Web信息管理、Web信息安全。

TP309

A

2023?01?10。

This work is partially supported by National Natural Science Foundation of China （61702237）， Science and Technology Planning Foundation of Xuzhou City （KC22052）， Opening Foundation of Fujian Provincial Key Laboratory of Network Security and Cryptology Research Fund， Fujian Normal University （NSCL-KF2021-04）， Opening Foundation of Guangxi Key Laboratory of Cryptography and Information Security， Guilin University of Electronic Technology （GCIS202114）， Postgraduate Research and Practice Innovation Program of Jiangsu Normal University （2021XKT1396）， Ministry of Education University-Industry Collaborative Education Program of China （202101374001）.

ZHU Xiuping， born in 1997， M. S. candidate. Her research interests include public-key cryptography， digital signature， Internet of Things privacy-preserving.

LIU Yali， born in 1981， Ph. D.， professor. Her research interests include information security， authentication and privacy-preserving， blockchain， vehicular ad-hoc network， cryptographic algorithms and protocols.

LIN Changlu， born in 1978， Ph. D.， professor. His research interests include cryptography， network security， secret sharing， secure multi-party computation， public-key cryptography.

LI Tao， born in 1998， M. S. candidate. His research interests include Radio Frequency Identification （RFID） authentication， privacy protection， Internet of Things security， blockchain.

DONG Yongquan， born in 1979， Ph. D.， professor. His research interests include Web information management， Web information security.