杜紅珍,溫巧燕
?
無證書強指定驗證者多重簽名
杜紅珍1,溫巧燕2
(1. 寶雞文理學院數(shù)學與信息科學學院,陜西寶雞 721013;2. 北京郵電大學網(wǎng)絡與交換技術國家重點實驗室,北京 100876)
為了滿足在司法行政、電子政務等領域的應用需求,提出了無證書強指定驗證者多重簽名的概念和敵手模型,利用雙線性對構造了第一個無證書強指定驗證者多重簽名方案,在計算雙線性Diffie-Hellman問題和計算Diffie-Hellman問題假設下證明了該方案是存在性不可偽造的,而且該方案滿足強指定驗證者簽名和多重簽名應具備的性質。方案執(zhí)行效率高,生成的指定驗證者多重簽名長度僅為160 bit,簽名驗證時需要的雙線性對運算個數(shù)是固定的,僅需一個雙線性對。所以,即使在計算資源與網(wǎng)絡帶寬受限的無線網(wǎng)絡中方案也非常實用。
無證書公鑰密碼學;指定驗證者多重簽名;不可偽造性;雙線性對
2003年,Al-Riyami等[1]提出了無證書公鑰密碼學(CL-PKC, certificateless public key cryptography),CL-PKC性能優(yōu)良,汲取了傳統(tǒng)公鑰密碼體制和基于ID的密碼體制的優(yōu)點,因為它不需要附帶證書來認證用戶的公鑰,從而去掉了維護證書的費用,同時又不存在密鑰托管問題,所以對CL-PKC的研究很有理論意義和實際應用價值。目前已有很多的無證書加密、簽名方案[2~8]被提出。
普通數(shù)字簽名的驗證權是不可控的,即只要有簽名人的公鑰就可以檢驗簽名的有效性,但在有些環(huán)境如電子投招標、電子購物、電子拍賣和知識產(chǎn)權保護等應用中,簽名人希望由自己指定簽名驗證者,從而控制簽名的驗證權。為了滿足這種應用,Jakobsson等[9]提出了指定驗證者簽名(DVS, designated verifier signature)的概念。在文獻[9]中,Jakobsson等還提出了強指定驗證者簽名(SDVS, strong designated verifier signature)。在一個SDVS方案中,簽名驗證時要用到指定驗證者的私鑰,所以除了簽名人指定的驗證者以外,其他人都不能驗證簽名的有效性。2003年,Steinfeld等[10]提出了廣義指定驗證者簽名(UDVS, universal designated verifier signature)的概念,UDVS與SDVS的主要區(qū)別是:前者允許任何一個(普通)簽名持有者(不一定是簽名者本人)根據(jù)自己的意愿來指定簽名驗證者,再將該(普通)簽名轉化為指定驗證者簽名。而后者是簽名人自己確定簽名的驗證者,再直接生成指定驗證者簽名。
目前,在CL-PKC下研究指定驗證者簽名的成果頗豐。2006年,Huang等[11]利用雙線性對提出了第一個無證書SDVS方案。2008年,Chen等[12]構造了一個無證書SDVS方案,生成的簽名長度可壓縮到160 bit。He等[13]構造了一個無需雙線性對的無證書SDVS方案。李繼國等[14]提出了一個基于證書的SDVS方案,簽名的長度僅160 bit。Ming等[15]給出了無證書UDVS的概念。Du等[16]提出了第一個高效的無證書指定驗證者代理簽名方案。Hafizul等[17]在CL-PKC下提出了一個廣義指定驗證者多重簽名方案,然而,該方案缺陷較多,比如作者概念不清,誤稱他們提出了一個無證書強指定驗證者多重簽名方案,且方案不能抵抗惡意但被動KGC的攻擊。2015年,張玉磊等[18]在CL-PKC下提出了一個廣義指定驗證者聚合簽名方案,該方案生成的聚合簽名長度為320 bit,簽名驗證需要的雙線性對個數(shù)固定,僅需4個對,所以方案執(zhí)行效率較高。
多重簽名(MS, multi-signature)的概念由Itakura等[19]提出,MS是一種多方參與的特殊簽名,允許多個簽名人在同一個消息上進行簽署,生成的多重簽名的長度遠小于每個人對的普通簽名的長度之和,且的驗證代價同樣大大低于驗證多個所需計算量。多重簽名在電子政務、電子病歷、蜂窩電話、電子射頻技術、傳感器等領域應用廣泛。
隨著新型網(wǎng)絡形態(tài)和網(wǎng)絡服務的出現(xiàn),研究多方參與的特殊簽名已成為密碼學界一個新熱點。本文在CL-PKC下將指定驗證者簽名與多重簽名結合,提出了一種特殊簽名——無證書強指定驗證者多重簽名(CL-SDVMS, certificateless strong designated verifier multi-signature),它允許多個用戶對同一個消息生成多重簽名,且該多重簽名的有效性只有這多個用戶指定的驗證者才能驗證,其他第三方都無法驗證簽名。與強指定驗證者簽名類似,一個安全的CL-SDVMS方案應該具備強壯性(第三方不可驗證性)、不可偽造性、不可傳遞性和簽名源的隱匿性?,F(xiàn)實生活中,CL-SDVMS有很多應用場景,比如多個目擊者想要向法官揭發(fā)某個犯罪嫌疑人,但為了防止遭到報復,目擊者們就指定該法官為簽名驗證者,采用CL-SDVMS方案來檢舉犯罪嫌疑人,這樣,只有該法官可以驗證簽名的有效性,從而相信簽名的真實性。同時CL-SDVMS的不可傳遞性也使目擊者得到保護,因為其他人不會相信簽名是目擊者生成而不是法官生成的。CL-SDVMS在司法行政如呈報減刑、假釋等工作和電子政務等領域有很好的應用前景。
本文首先提出了CL-SDVMS的定義和安全模型,接著利用雙線性對構造了第一個CL-SDVMS方案,該方案滿足強壯性、不可偽造性、不可傳遞性和簽名源的隱匿性。方案執(zhí)行效率高,因為它是非交互的,且簽名的驗證僅需一個雙線性對,另外,生成的指定驗證者多重簽名長度固定,不會隨簽名人數(shù)的增加而增長。
1) 雙線性對
2) 計算Diffie-Hellman(CDH)問題
3) 計算雙線性Diffie-Hellman(CBDH)問題
迄今為止,CDH問題和CBDH問題仍是困難的。
3.1 CL-SDVMS方案的形式化定義
定義1 CL-SDVMS方案的參與實體:一個私鑰生成中心(KGC),個簽名用戶和一個由這個用戶指定的驗證者。CL-SDVMS方案由以下6個算法構成。
1) 系統(tǒng)建立(Setup)算法:輸入一個安全參數(shù),輸出系統(tǒng)主密鑰和系統(tǒng)參數(shù),該算法由KGC執(zhí)行。
2) 部分私鑰生成(Partial-Private-Key-Extract)算法:由KGC執(zhí)行,輸入、和身份, 返回用戶的部分私鑰。
3) 用戶密鑰生成(User-Key-Generate)算法:由用戶執(zhí)行,輸入、,輸出該用戶的秘密值和公鑰(x,Pk)。
6) 簽名模擬(Simulation)算法:該算法由指定驗證者執(zhí)行,輸入,,set=,,,指定驗證者的部分私鑰/秘密值(D,x),輸出一個與個簽名人生成的不可區(qū)分的簽名副本。
3.2 CL-SDVMS方案的安全模型
在一個CL-SDVMS方案中,存在2種具備不同攻擊力的敵手A1和A2。第一種敵手A1模擬惡意用戶,他掌握用戶的秘密值,可以替換任意用戶的公鑰,但不知道系統(tǒng)主密鑰和用戶的部分私鑰。第2種敵手A2模擬的是惡意但被動(malicious-but- passive)KGC,他擁有系統(tǒng)主密鑰并可以求出用戶的部分私鑰,但不知道用戶的秘密值,且不能替換用戶的公鑰。
下面通過引入挑戰(zhàn)者X?和敵手A(A1或A2)之間的Game來模擬CL-SDVMS的不可偽造性安全模型。
1) Setup:X?運行Setup算法生成系統(tǒng)主密鑰和公開參數(shù),秘密保存,將發(fā)送給A。如果A是第2種敵手A2,則發(fā)送和給A2。
2) Query:A可以適應性詢問以下預言機。
Hash詢問:當A詢問任意一個散列函數(shù)值時,X輸出相應的散列值給A。
Partial-Private-Key-Extract詢問:輸入,X返回部分私鑰給A(此預言機僅針對A1,A2不需要詢問該預言機,因為它知道用戶的部分私鑰)。
Sign詢問:A輸入簽名者/指定驗證者身份(ID,ID),公鑰(Pk,Pk), 消息,身份集set,X?運行Sign算法生成相應的部分簽名,再返回給A。
Verify 詢問:A輸入簽名者/指定驗證者身份(ID,ID),公鑰(Pk,Pk),消息/簽名(,),身份集set,X運行Verify算法判斷的有效性,再輸出“1”或“0”給A。
①如果A是第一種敵手A1,中至少有一個)和指定驗證者沒有提交給Partial-Private-Key-Extract預言機,且(,,)沒有提交給Sign預言機,則A獲勝;
②如果A是第2種敵手A2,中至少有一個)和指定驗證者沒有提交給Secret-Value-Extract預言機,且(,,)沒有提交給Sign預言機,則A獲勝。
定義2 如果不存在概率多項式時間敵手A(A1或A2)在以上Game中能以不可忽略的優(yōu)勢獲勝,則一個CL-SDVMS方案在適應性選擇消息攻擊下是存在性不可偽造的(EUF-CL-SDVMS-CMA2安全)。
4.1 基本方案
本節(jié)構造了一個無證書強指定驗證者多重簽名方案,由下面6個算法組成。
5) 驗證算法:輸入,,,指定驗證者ID(其部分私鑰D=sQ,秘密值x)計算如下。
6) 簽名模擬算法:對消息,指定驗證者ID可以生成有效的指定驗證者多重簽名副本。
下面給出方案正確性的證明。
4.2 方案的安全性分析
4.2.1 不可偽造性
定理1 在Random Oracle模型和CBDH及CDH難題假設下,本文的CL-SDVMS方案在2類敵手A1和A2的攻擊下是EUF-CL-SDVMS-CMA2安全的。
定理1由引理1和引理2推出。
引理1 在Random Oracle模型下,假定有敵手A1在概率多項式時間內(nèi)以優(yōu)勢攻破了本文CL-SDVMS方案,記A1最多詢問Create-User,Partial-Private-Key-Extract,Sign和Verify的次數(shù)分別為、、和,則存在一個算法X,使用A1為黑盒子,在時間內(nèi),以的優(yōu)勢解決CBDH難題,是1群上一個標量乘時間,是一個雙線性對運算時間,inv是計算Z*上一個求逆時間。
證明 本CL-SDVMS方案涉及個簽名用戶和一個由這個用戶指定的驗證者ID,不妨假設除用戶以外,其余?1個用戶都被敵手A1賄賂(本文賦予了敵手更強的攻擊能力,此處模擬的是一種極端情形,實際場景中一般不少于一個誠實者)。設X為挑戰(zhàn)者,給定群上CBDH問題的任意實例,其中,,,未知,X最終目的是輸出值。
Create-user:A1輸入,X調(diào)出列表查看,如果用戶已被創(chuàng)立,X只需將的公鑰Pk返回給A1;否則,X執(zhí)行如下。
Partial-Private-Key-Extract:當A1輸入(以下默認用戶已被創(chuàng)立),X調(diào)出列表,如果,則返回、;否則,停止模擬,輸出failure。
Public-Key-Replace:當A1輸入()進行公鑰替換詢問,X調(diào)出列表,用替換Pk,即Pk=再替換對應的秘密值。
Secret-Value-Extract:A1輸入,X調(diào)出列表,返回給A1。
Sign:A1輸入簽名者/指定驗證者的身份(ID,ID)和公鑰(Pk,Pk), 消息,身份集set,X執(zhí)行如下。
1) 如果ID≠ ID,ID時,X調(diào)出列表list()、列表list和列表list,計算,返回指定驗證者簽名給A1。
Verify:A1輸入簽名者/指定驗證者的身份(ID,ID)和公鑰(Pk,Pk)、消息/指定驗證者簽名(,)、身份集set,驗證如下。
Forgery:最后,敵手A1偽造了一個在消息上關于的有效指定驗證者多重簽名*,其中,個簽名者的身份/公鑰為()),指定驗證者身份/公鑰為()。若和,則X停止模擬,輸出failure;否則,,且,下面不妨假設I=。
從而,X可以計算???
即X可以解決CBDH難題,但目前CBDH問題是困難的,所以規(guī)約出本文方案是EUF-CL-SDVMS- CMA2安全的。
下面計算X成功的概率。用E1、E2、E3、E4、E5表示5個事件如下。
1) E1:X回答A1的詢問時沒有失敗。
2) E2:X回答A1的詢問時沒有失敗。
3) E3:X回答A1的詢問時沒有失敗。
4) E4:A1成功地偽造了1個在消息上的指定驗證者多重簽名*,其中,個簽名者的身份為,指定驗證者身份為。
5) E5:在發(fā)生情況下,有和。
顯然,
則
當事件E1、E2、E3、E4、E5都發(fā)生時,X獲勝,其概率為。
將X在Game中每次應答時進行的運算時間加起來可得
引理2 在Random Oracle模型下,假定有敵手A2在概率多項式時間內(nèi)以優(yōu)勢攻破了本文CL-SDVMS方案,記A2最多詢問Create-User、Secret-Value-Extract、Sign和Verify的次數(shù)分別為、、和,則存在一個算法X,使用A2為黑盒子,在時間內(nèi),以的優(yōu)勢解決CDH難題,是G1群上一個標量乘時間,是一個雙線性對運算時間。
Create-user:A2輸入,X調(diào)出列表查看,如果用戶已被創(chuàng)立,A只需將的公鑰Pk返回給A2;否則,X選2個隨機數(shù),計算,,用戶的部分私鑰,。接著計算用戶的公鑰如下。
Secret-Value-Extract:A2輸入,如果,X調(diào)出列表,返回給A2;否則,輸出failure。
Sign:A2輸入簽名者/指定驗證者的身份(ID,ID)和公鑰(Pk,Pk), 消息,身份集set,X調(diào)出列表()、列表和列表list,計算,返回指定驗證者簽名給A2。
Verify:A2輸入簽名者/指定驗證者的身份(ID,ID)和公鑰(Pk,Pk), 消息/指定驗證者簽名(,)、身份集set,X調(diào)出列表()、列表和列表list,檢驗,如果等式成立則返回“1”,表示簽名有效;否則,返回“0”,說明簽名無效。
Forgery:最后,敵手A2偽造了一個在消息上關于的有效指定驗證者多重簽名,其中,個簽名者的身份/公鑰為()),指定驗證者身份/公鑰為(),若和,則X停止模擬,輸出failure;否則,,且,下面不妨假設ID=。X調(diào)出列表或list,查看記錄或,如果或list中沒有這樣的記錄,則失敗退出;否則,就有,從而X得到值,即X可以解決CDH難題,但目前CDH問題仍是困難的,所以,可規(guī)約為本文方案在A2攻擊下是EUF-CL- SDVMS-CMA2安全的。另外,X成功的概率計算方法與引理1的相同,此處不再贅述。
4.2.2 強壯性(第三方不可驗證性)
4.2.3 簽名源隱匿性
簽名源隱匿性是指給定一個消息/指定驗證者多重簽名對(,),即使第三方Coral知道個簽名人和指定驗證者ID的私鑰,也不能判斷出是ID還是ID生成的。
本文CL-SDVMS方案滿足簽名源隱匿性,下面對Coral賦予不同的攻擊能力,分以下2種情況證明該性質。
1) Coral模擬敵手A:A擁有系統(tǒng)參數(shù),簽名人和指定驗證者ID的公鑰,且掌握?1個簽名人ID的私鑰(即部分私鑰和秘密值。
2) Coral模擬敵手T:T除了具備A的攻擊能力外,他還掌握所有簽名人和指定驗證者ID的私鑰。
但是,如果用ID的私鑰可以計算,其中,,。
綜上,本文的CL-SDVMS方案滿足簽名源隱匿性。
4.2.4 不可傳遞性
不可傳遞性是指指定驗證者ID雖然可以驗證多重簽名的有效性,但他不能使任何第三方相信就是個簽名人所簽,因為ID可以通過簽名模擬算法生成與不可區(qū)分的簽名副本。
顯然,由簽名源隱匿性可推出CL-SDVMS方案滿足不可傳遞性。因為給定簽名,即使第三方知道個簽名人和指定驗證者ID的私鑰,也不能判斷出是ID還是ID生成的,所以,如果指定驗證者ID給他出示時,他不能相信就是所簽。
4.3 方案的性能分析
Hafizul Islam SK方案[17]是一個無證書廣義指定驗證者多重簽名方案,與本文方案最為接近,所以將本文CL-SDVMS方案與文獻[17]方案進行了比較,如表1所示。其中,Sm、Pr分別表示群G1上1次標量乘計算、1次雙線性對計算,其他運算耗時較短,此處忽略不計。
表1 方案性能比較(共n個簽名用戶)
4.3.1 效率分析
由于雙線性對計算最昂貴,1次雙線性對計算耗時至少是標量乘計算時間的20倍以上[20],即1(、分別表示一個雙線性對運算與一個標量乘運算時間),則本文方案簽名和驗證的計算總時間量為,文獻[17]方案的計算總時間量為。顯然,,如取簽名人數(shù)=5,則本文方案的簽名和驗證總耗時是文獻[17]方案的56.1%。
另外,本文生成的簽名長度為160 bit,文獻[17]方案為320 bit,即本文方案傳輸簽名的帶寬比文獻[17]方案節(jié)省了50%。
綜上,本文方案的計算與通信代價大大低于文獻[17]方案。
4.3.2 安全性分析
1) 本文方案滿足不可偽造性,但文獻[17]方案不能抵抗惡意但被動的KGC的偽造攻擊。
2) 本文方案是非交互的,即簽名前或簽名過程中都不需要參與方交互信息來生成簽名。文獻[17]方案是交互的,在簽名生成過程中需要每個簽名人給其他簽名人廣播信息,且只有收到其他簽名人的廣播信息后才可以繼續(xù)實施簽名,這種交互的方案實用性不好。
由1)和2)可見,本文方案是一個性能良好的安全高效的CL-SDVMS方案。
CL-SDVMS在司法行政如呈報減刑、假釋等工作和電子政務等領域有很好的應用前景。本文提出了第一個非交互、緊湊的CL-SDVMS方案,經(jīng)證明方案滿足強壯性、不可偽造性、不可傳遞性和簽名源隱匿性。另外,該方案的實施所需計算量與通信量都很小,非常適合計算資源、網(wǎng)絡帶寬受限的新型無線網(wǎng)絡環(huán)境。接下來的工作是構造無需雙線性對的高效CL-SDVMS方案。
[1] AL-RIYAMI S, PATERSON K G. Certificateless public key cryptography[C]//ASIACRYPT 2003, LNCS 2894, Springer-Verlag.c2003: 452-473.
[2] YUM D H, LEE P J. Generic construction of certificateless encryption[C]//ICCSA 2004. LNCS 3043, Springer-Verlag, c2004:802-811.
[3] HE D B, HUANG B, CHEN J H. New certificateless short signature scheme[J]. Information Security IET, 2013, 7(2):113-117.
[4] YUAN Y, WANG C. Certificateless signature scheme with security enhanced in the standard model [J]. Information Processing Letters, 2014, 114, 492-499.
[5] DU H Z, WEN Q Y. Security analysis of two certificateless short signature schemes [J]. IET Information Security, 2014, 8(4): 230-233.
[6] CHEN Y C, TSO R, HORNG G, et al. Strongly secure certificateless signature: cryptanalysis and improvement of two schemes [J]. Journal of Information Science and Engineering, 2015, 31: 297-314.
[7] YEH K H, TSAI K Y, FAN C Y. An efficient certificateless signature scheme without bilinear pairings[J]. Multimed Tools Appl. Doi: 10.1007/s11042-014-2154-4.
[8] SEO S H, NABEEL M, DING X Y, et al. An efficient certificateless encryption for secure data sharing in public clouds[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(9):2107-2119.
[9] JAKOBSSON M, SAKO K, IMPAGLIAZZO R. Designated verifier proofs and their applications[C]//Advances in Cryptology-Eurocrypt 1996. LNCS 1070, Berlin, Springer-Verlag, c1996: 142-154.
[10] STEINFELD R, BULL L, WANG H, PIEPRZYK J .Universal designated verifier signatures[C]//Advanced in Asiacrypt’03, Berlin: Springer-Verlag, c2003: 523-542.
[11] HUANG X Y, SUSILO W, MU Y and ZHANG F T. Certificateless designated verifier signature schemes[C]//SNDS 2006, IEEE Computer, c2006: 15-19.
[12] CHEN H, SONG R S, ZHANG F T, et al. An efficient certificateless short designated verifier signature scheme[C]//WiCOM, IEEE, c2008: 1-6.
[13] HE D B, CHEN J H. An efficient certificateless designated verifier signature scheme[J]. International Arab Journal of Information Technology, 2013, 10(4): 389-396.
[14] 李繼國, 錢娜, 黃欣沂, 等. 基于證書強指定驗證者簽名方案[J]. 計算機學報, 2012, 35(8): 1579-1587.
LI J G, QIAN N, HUANG X Y,et al. Certificate-based strong designated verifier signature scheme[J]. Chinese Journal of Comupters, 2012, 35(8): 1579-1587.
[15] MING Y, SHEN X Q, WANG Y M. Certificateless universal designated verifier signature schemes[J]. The Journal of China Universities of Posts and Telecommunications, 2007,14(3): 85-90.
[16] DU H Z, WEN Q Y. Efficient certificateless designated verifier signatures and proxy signatures[J]. Chinese Journal of Electronics, 2009, 18(1): 95-100.
[17] HAFIZUL I S, BISWAS G P. Certificateless strong designated verifier multisignature scheme using bilinear pairings[C]//International Conference on Advances in Computing, Communications and Informatics. c2012: 540-546.
[18] 張玉磊, 周冬瑞, 李臣意, 等. 高效的無證書廣義指定驗證者聚合簽名方案[J]. 通信學報, 2015, 36(2): 1-8.
ZHANG Y L, ZHOU D R, LI C Y, et al. Efficient certificateless aggregate signature scheme with universal designated verifier[J]. Journal on Communications, 2015, 36(2): 1-8.
[19] ITAKURA K and NAKAMURA K. A public-key cryptosystem suitable for digital multisignatures[J]. NEC Research and Development, 1983, (71):1-8.
[20] CHEN L, CHENG Z, SMART N P. Identity-based key agreement protocols from pairings[J]. International Journal of Information Security, 2007, 6(4): 213-241.
Certificateless strong designated verifier multi-signature
DU Hong-zhen1, WEN Qiao-yan2
(1. School of Mathematics and Information Science, Baoji University of Arts and Sciences, Baoji 721013, China; 2. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)
In order to satisfy the application requirements in the fields of judicial administration, e-government, etc., the definition and security model for certificateless strong designated verifier multi-signature were proposed. Then, the first certificateless strong designated verifier multi-signature scheme from bilinear pairings was constructed and it was proved that the scheme is existentially unforgeable under the computational bilinear Diffie-Hellman assumption and the computational Diffie-Hellman assumption. Moreover, the scheme meets the properties of both strong designated verifier signatures and multi-signatures. The scheme achieves high efficiency since the length of designated verifier multi-signature generated by the scheme is only 160 bits and the computational cost of bilinear pairings necessary for verification algorithm is constant, i.e., one bilinear pairing. So, it can be applied in wireless networks of the limited computing resources and network bandwidth.
certificateless public key cryptography, designated verifier multi-signature, unforgeability, bilinear pairing
TP309
A
10.11959/j.issn.1000-436x.2016112
2015-12-27;
2016-05-11
國家自然科學基金資助項目(No.61402015, No.61402275);陜西省教育廳專項科研基金資助項目(No.15JK1022);陜西省自然科學基礎研究基金資助項目(No.2015JM6263)
The National Natural Science Foundation of China (No.61402015, No.61402275), The Scientific Research Project of Shaanxi Provincial Educations Department (No.15JK1022), The Basic Research Project of Natural Science in Shaanxi Province (No.2015JM6263)
杜紅珍(1978-),女,陜西扶風人,博士,寶雞文理學院副教授,主要研究方向為密碼學、物聯(lián)網(wǎng)安全和數(shù)字簽名技術。
溫巧燕(1959-),女,陜西西安人,北京郵電大學教授、博士生導師,主要研究方向為密碼學與信息安全。