一種支持并行密鑰隔離的無證書聚合簽名方案

楊憶歐，彭長根,3，丁紅發，許德權

(1.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 公共大數據國家重點實驗室，貴州 貴陽 550025；3.貴州大學 密碼學與數據安全研究所，貴州 貴陽 550025；4.貴州財經大學 信息學院，貴州 貴陽 550025)

0 引 言

云計算、大數據和5G等信息技術迅速普及，面向群組的通信需求隨之與日俱增，身份認證是實現群組中多用戶安全通信面臨的首要問題。基于非對稱密碼體制設計的數字簽名因具備認證性、不可抵賴性等性質而成為關鍵的密碼原語。群體的認證需求向數字簽名體制提出了新要求，促使其由原本的雙方參與逐步擴展到多用戶參與。

聚合簽名作為一種面向群體認證的特殊數字簽名技術，在保持傳統數字簽名性質的前提下，兼具簽名壓縮及批量驗證特性，有效縮減了簽名總長度和驗證成本，其在帶寬和資源受限的群組通信場景中優勢突出。2003年，由Boneh等人[1]正式定義了聚合簽名的基本原語，并利用BLS短簽名方案[2]基本構造給出了具體方案。同年，Al-Riyami等人[3]提出無證書公鑰密碼學(certificateless public key cryptography，CL-PKC)的基本思想，用戶密鑰的生成不完全由密鑰生成中心(key generation center，KGC)決定，而是由用戶和KGC共同產生，旨在消除經典公鑰機制中繁瑣的公鑰證書管理及身份基密碼機制(identity-based public key cryptography，ID-PKC)中固有的密鑰托管。

無證書密碼體制的出現使多數公鑰密碼系統在運行效率上有了進一步提升的可能，適用于不同場景的特殊無證書密碼方案[4-6]陸續被提出。用無證書密碼體制構造的聚合簽名(certificateless aggregate signature，CLAS)作為設計面向群體的安全認證協議及技術所需的關鍵密碼部件，吸引學術界開展深入研究。2015年，陳虎等[7]以雙線性映射構造了一個安全性較高的CLAS，在生成聚合簽名之前將提前協商的狀態信息公布給合法簽名者，使任意合法用戶能動態地參與聚合簽名，避免了聚合過程中用戶交互開銷，提升了方案的靈活性與通信效率。2018年，Kumar等[8]針對資源受限的無線醫療傳感網絡設計了一種高效的CLAS，在聚合簽名驗證階段只用了常數量級的三個雙線性配對操作，方案的能量消耗及計算開銷優于同類方案。次年，Kumar等[9]又考慮了車載網中通信帶寬有限的問題，基于自己提出的無證書簽名方案構造了CLAS，利用偽身份的方式實現了車輛用戶的條件隱私保護。雖然使用雙線性映射構造的方案在確保安全性的基礎上能選取長度更短的密鑰，但是此類方案大多有實用性、適用性及效率方面的問題。因此，許多研究者開始考慮非配對的無證書聚合簽名方案的設計。2020年，Zhao等[10]設計了一種適用于計算及能耗有限的輕量級設備的CLAS，并對方案做了詳盡的安全性分析及實驗仿真，表明了方案的實用性。Liu等[11]在同年也提出了一種不含雙線性映射的CLAS，并同時聚合了隨機數及簽名，存儲及計算開銷有較大改善，但該方案并未滿足其所定義的安全要求。

綜上可知，目前的研究主要聚焦于聚合簽名的功能、安全性及效率方面，密鑰的安全性并未受到足夠的重視。某個密鑰如果泄露，敵手便能使用該密鑰執行特定攻擊，由其參與產生的任意簽名都不再被信任。針對這個風險最樸素的解決思路是直接刪除該密鑰及其相關的簽名，然而這對簽名系統資源消耗和浪費非常大。密鑰演化技術為解決密鑰泄漏問題提供了新思路，其基本思想是將密碼系統的生命周期劃分為若干時間片段，分別對每一時間片段的密鑰進行更新，在不同時間片段內使用對應密鑰，即便攻擊者獲取到某一時間片段的密鑰，系統在其他時間片段的運轉依然不受影響。2018年，韋性佳等[12]基于強RSA問題設計了一個前向安全的身份基聚合簽名，在簽名產生時加入了前向安全的思想，進而提高了簽名系統安全性。2019年，Jihye等[13]構造了一種有序聚合簽名方案，其滿足前向安全，并將之用于計算機系統中的審計日志完整性檢測。前向安全理論可解決密鑰泄露的部分問題，但大多數前向安全的簽名方案均存在一個缺陷，即無法保障方案的后向安全性。

前向安全技術的缺陷在Dodis等[14]提出密鑰隔離機制得以彌補。2019年，Xiong等[15]給出了一個無證書并行密鑰隔離簽名方案，為解決智能設備中數據傳輸及共享的認證問題提供了幫助，但并未考慮簽名聚合的可行性。目前針對密鑰隔離機制下聚合簽名方案的研究[16-17]依然不多，如何設計抗密鑰泄露、運行效率較高的聚合簽名方案仍然是當下的難點。

基于上述分析，該文提出了一種支持并行密鑰隔離的無證書聚合簽名方案，記為CL-PKIAS。主要工作分述如下：

首先，通過引入并行密鑰隔離這一安全密鑰更新機制，給出了它在密鑰更新階段的動態更新流程。簽名者以輪替的方式與兩個協助者交互實現部分簽名密鑰更新。并且簽名用戶與KGC、協助者在傳輸部分私鑰及密鑰更新消息時無需安全信道。

其次，基于橢圓曲線密碼體制構造了CL-PKIAS方案，并形式化地給出了方案架構及其安全模型，將其安全性歸結到橢圓曲線群上的離散對數困難問題，基于隨機預言機模型證明了所提方案在適應性選擇消息攻擊下可以抵抗存在性偽造。

最后，性能分析顯示，該方案生成的聚合簽名長度和簽名參與人數不相關。由于避免了復雜的雙線性映射操作，簽名及驗證均基于橢圓曲線循環群進行，故方案在運算效率及通信開銷上具有優勢。

1 基礎知識

1.1 橢圓曲線群

有限素域上滿足y2=x3+ax+b(modp)，a，b∈Fp且4a3+27b2(modp)≠0的點集構成了橢圓曲線E(Fp)。定義G={P|P∈E(Fp)}∪{O}為E(Fp)的點集同無窮遠點O構成的橢圓曲線加法循環群，滿足以下性質：

(1)加法運算：設Q,P∈G，R表示由Q，P確定的直線同橢圓曲線的交點，過R作垂線與橢圓曲線交于R'，則Q+P=R'。

1.2 ECDLP問題

2 方案定義及安全模型

2.1 CL-PKIAS方案的形式化定義

方案形式化地記為多項式概率算法CL-PKIAS=(Setup，Key-Generate，Key-Update，Sign-Generate，Sign-Aggregate，Aggregate-Verify)，其中各算法的工作流程如下：

Setup:輸入安全參數λ，KGC產生并公布公開參數列表params，生成系統主密鑰msk秘密留存。

Key-Generate:由KGC與用戶交互執行該算法，輸入params，用戶Ci的身份信息IDi及時間片段t。

(1)Ci選擇秘密值生成公/私鑰對(upki,uski)；

(2)KGC利用給定信息及系統主密鑰為Ci生成初始部分公私鑰對(ppki,ski,0)；

(3)(ppki,upki)及(ski,0,uski)為Ci的初始完整公/私鑰對。

Key-Update:該算法由用戶Ci依次與兩協助者交互執行，輸入params，Ci身份信息IDi，時間片段t。

(1)Ci根據t指定協助者j(j≡t(mod 2)),利用其私鑰hskj產生更新信息Ui,t,j。

(2)Ci利用Ui,t,j生成臨時部分私鑰ski,t。

Sign-Generate:用戶Ci執行此算法，輸入params，待簽名消息mi,時間片段t的完整臨時簽名密鑰對(uski,ski,t)，簽名者Ci生成簽名Si。

Sign-Aggregate:輸入params，(Ci)i=1,2,…,n對消息(mi)i=1,2,…,n的簽名(Si)i=1,2,…,n，聚合者進行簽名聚合獲得S并輸出。

Aggregate-Verify:輸入params，聚合簽名S，用戶(Ci)i=1,2,…,n對應的完整公鑰，驗證S的合法性，驗證者經判定后輸出true或false。

2.2 CL-PKIAS方案的安全模型

在無證書簽名體制中，用戶的簽名密鑰由兩方產生，偽造一個有效簽名必須獲取完整用戶密鑰。因此，若下述兩類敵手通過任意的選擇消息均無法進行存在性偽造，則表明CL-PKIAS方案是安全的。

(1)基于用戶組及消息組偽造的聚合簽名S*是一個有效聚合簽名。

(1)基于用戶組及消息組偽造的聚合簽名S*是一個有效聚合簽名。

3 CL-PKIAS方案構造

3.1 系統參數初始化(Setup)

3.2 密鑰生成(Key-Generate)

3.3 密鑰更新(Key-Update)

3.4 簽名生成(Sign-Generate)

3.5 簽名聚合(Sign-Aggregate)

3.6 聚合驗證(Aggregate-Verify)

4 安全性分析

在本節中將給出CL-PKIAS方案的EUF-CMA的安全性證明，利用反證法證明其結論，假定挑戰者可給出ECDLP問題的有效解，則敵手能攻破該方案，然而已知實際情況下ECDLP問題是難解的，由逆否定理可知，該方案是安全的，具體證明過程如下所敘：

定理1：CL-PKIAS方案的EUF-CMA安全性如果被任何PPT敵手以不可忽略的優勢ε攻破，1至多可以執行qHi次(其中i=0,1,…,5)Hi預言查詢，qP次部分私鑰查詢，qPK次公鑰查詢，qV次秘密值查詢，qRP次公鑰替換查詢，qSK次協助者密鑰查詢，qS次簽名查詢，則總有挑戰者1在多項式時間內以至少的概率ε'解決ECDLP問題。

H0查詢：若1可以隨時向H0預言機請求關于(IDi,xisP)的查詢至多qH0次，1維護元素為(IDi,xisP,ji)的列表L0以應答1。針對每次查詢，1如果從L0中查找到元素(IDi,xisP,ji)，直接將已有的ji返回給1；否則，隨機選取響應1，并將新項更新至L0。

H1查詢：若1能隨時向H1預言機請求關于(IDi,Xi,Ri)的查詢至多qH1次，1維護元素為的列表L1以應答1。針對每次查詢(IDi,Xi,Ri)，1如果從L1查找到對應元素，用已定義的作為對1的應答；否則，任選擲硬幣選取ci∈{0，1}，設Pr[ci=0]=δ。若ci=0，則反之，選擇隨機數最終以應答1，更新并保存新項至L1。

H2查詢：若1能隨時向預言機請求關于(IDi,Xi,t)的查詢至多qH2次，1維護元素形為(IDi,Xi,t,fi)的列表L1以應答1。針對每次查詢，1如果能從L2中查找到元素(IDi,Xi,t,fi)，則將預先定義的fi返回給1；否則，將作為對1的應答，并保存新項(IDi,Xi,t,fi)至L2。

H3查詢：若1可隨時發出查詢請求從而查詢H3(mi,IDi,Ti,Xi,Vi)至多qH3次，1負責維護元素為(mi,IDi,Ti,Xi,Vi,h1i)的列表L3。針對每次查詢(mi,IDi,Ti,Xi,Vi)，1如果能從L3中發現相應元素，則將已定義的h1i返回給1；否則，將應答1，并添加新項(mi,IDi,Ti,Xi,Vi,h1i)至L3。

H4查詢：若1能隨時向H4預言機請求關于(mi,IDi,Xi,Ti)的查詢至多qH4次，1維護元素為(mi,IDi,Xi,Ti,h2i)的列表L4以應答1。針對每次查詢(mi,IDi,Xi,Ti)，1若從L4中查找到相應元素，則將已定義的h2i返回給1；否則，將作為對1的應答，并添加新項(mi,IDi,Xi,Ti,h2i)至L4。

H5查詢：若1能隨時向H5預言機請求關于(mi,IDi,Ti,mpk)的查詢至多qH5次，1維護元素為(mi,IDi,Ti,mpk,h3i)的列表L5以應答1。針對每次查詢(mi,IDi,Xi,Ti)，1若從L5中查找到相應元素，則以已定義的h3i應答1；否則，將作為對1的應答并添加新項(mi,IDi,Ti,mpk,h3i)至L5。

偽造階段：1的有界次查詢請求得到應答后，可基于和對應的公鑰偽造出一個聚合簽名(V*,U*)。若滿足下述前提，首先簽名有效；其次，存在一個i∈[1,n]使得ci=0，不妨假設i=1，且未對部分私鑰預言機及簽名預言機發起過查詢請求，則1可根據驗證等式輸出ECDLP問題的有效解

如果事件E1表示1未針對提出過部分私鑰查詢，則

事件E2表示1不中斷1提出的任意簽名查詢，則Pr[E2]=(1-δ)qV+qRP+qS；

事件E3指即使1偽造階段能偽造出含有效聚合簽名，1仍不中斷，則Pr[E3]=1/qs+n。

定理2：CL-PKIAS方案的EUF-CMA安全性如果被任何PPT敵手2以不可忽略的優勢ε攻破，2至多可以執行qHi次(其中i=0,1,…,5)Hi預言查詢，qPK次公鑰查詢，qV次秘密值查詢，qSK次臨時簽名密鑰查詢，qS次簽名查詢，則總有挑戰者2在多項式時間內以至少ε'的概率解決ECDLP問題。

查詢攻擊階段：除H1查詢，公鑰查詢，臨時簽名密鑰查詢外，2其他預言查詢的執行過程與定理1一致。

H1查詢：若2能隨時向H1預言機請求關于(IDi,Xi,Ri)的查詢至多qH1次，2維護元素為的列表L1以應答2。針對每次查詢(IDi,Xi,Ri)，2如果從L1查找到已定義的對應元素，則直接以其回應2；否則，隨機選取響應2，并把新項保存至L1。

如果事件E1表示2未針對提出過部分私鑰查詢，則

事件E2表示2不中斷2提出的任意臨時簽名密鑰查詢，則Pr[E2]=(1-δ)qPK+qSK；

事件E3表示2不中斷2提出的任意簽名查詢，則Pr[E3]=(1-δ)qS；

事件E4指即使2偽造階段能偽造出含有效聚合簽名，2仍不中斷，則Pr[E4]=1/qs+n。

證畢。

綜上可得，無法構造出以不可忽略的優勢解決ECDLP困難問題的算法，故該方案的EUF-CMA安全性不能為1，2所攻破。

5 性能分析

為對該方案的性能進行準確評估,在配置為Intel(R)Core(TM)i5-6200 CPU @ 2.40 GHz，內存4 GB，Windows10 64位操作系統的實驗環境下利用JPBC庫為基礎進行實驗對照分析。該文選取的密碼參數均與密鑰長度為1 024比特的RSA體制保持同等安全，以實現相同指標下的性能比對分析。基于雙線性映射的密碼操作所使用的曲線是嵌入度為2的超奇異橢圓曲線E(Fp):y2=x3+x，其中q是不少于512比特的素數，p=2159+217+1是160比特的Solinas素數，p,q滿足q+1=12pr，G1表示基于該曲線的q階雙線性群，群元素長度為128字節，記作|G1|。選取Koblitz曲線實現橢圓曲線加法循環群上密碼運算操作，其在有限域F2163上形為y2=x3+ax2+b，其中p,q為160比特的素數，b為163比特的隨機數且a=1，G表示基于該曲線的q階加法循環群，群元素長度為40字節，記作|G|。表1定義了密碼操作符號，并通過運行1 000次實驗取其平均值的方式給出了單次密碼運算的所用耗時。

表1 單次密碼操作的執行時間

表2從理論上分析了各方案的計算性能。文獻[8]方案中，聚合簽名開銷為2n個基于雙線性群的乘法運算Tbm，4n個基于雙線性群的加法運算Tba，一個映射到點的散列函數運算TH；聚合驗證成本為三個雙線性運算，n個基于雙線性群的乘法運算Tbm，2n-1個基于雙線性群的加法運算Tba，兩個映射到點的散列函數運算TH。文獻[11]方案中，聚合簽名開銷為2n個基于ECC的倍點運算Tem，3n個基于ECC的加法運算Tea；聚合驗證成本為2n個基于ECC的倍點運算Tem，3(n-1)個基于ECC的加法運算Tea。文獻[16]方案中，聚合簽名開銷為3n個基于雙線性群的乘法運算Tbm，2n個基于雙線性群的加法運算Tba，一個映射到點的散列函數運算TH；聚合驗證成本為四個雙線性運算，2n個基于雙線性群的乘法運算Tbm及加法運算Tba，一個映射到點的散列函數運算TH。文中方案聚合簽名開銷為n個基于ECC的倍點運算Tem，2n個基于ECC的加法運算Tea；聚合驗證代價為3n+1個基于ECC的倍點運算Tem，2n-1個基于ECC的加法運算Tea。

表2 各方案的計算開銷對比

利用表1中的實驗數據，針對文中方案及文獻[8,11,16]方案，采用消息數目遞增的方式進行實驗，實驗性能對比如圖1、2所示。文中方案在聚合簽名階段的計算性能優于其他三個方案，與它耗時最接近的文獻[11]方案相比，其效率提升了大約20%；在聚合驗證階段，文中方案的運行效率優于有雙線性映射運算的方案，相較于文獻[11]方案效率偏低，然而，文中方案是在犧牲效率的前提下增加了并行密鑰隔離功能，在一些應用場景中能夠有效降低密鑰泄露的威脅，因此這種時間消耗是能夠被接受的。

表3列出了各方案的功能對比及通信開銷，文獻[8]方案中，聚合簽名所占字節長度為128(n+1) byte,其簽名長度與參與簽名人數相關，文獻[11]方案中，聚合簽名所占字節長度保持在80 byte,但以上兩個方案均未考慮密鑰泄露問題。文獻[16]方案中，聚合簽名長度固定為256 byte，并且引入密鑰隔離機制以保障簽名方案的前向及后向安全。文中方案的聚合簽名長度為固定的60 byte，進一步加入并行密鑰隔離機制確保密鑰頻繁更新的安全性，同時在生成部分私鑰時，不需要構建安全信道就能實現與協助者及KGC的交互，增強了方案的實用性。

表3 各方案的通信開銷及功能對比

6 結束語

該文探討了密鑰泄露對無證書聚合簽名安全性的威脅，并針對性地將并行密鑰隔離機制引入到方案的密鑰更新階段，以便能夠動態地對臨時簽名密鑰進行更新，并利用橢圓曲線密碼體制構造了CL-PKIAS，利用ECDLP問題的困難性在隨機預言模型下給出了該方案的安全性分析。由性能分析可知，該方案在滿足安全要求的前提下具有更低的通信及運算成本。

值得注意的是，該方案實現了數據的認證性，數據的機密性并未考慮。下一步需要考慮的是如何將其擴展到無證書聚合簽密，以提高在分布式群組安全通信場景中的適用性。