具有聚合性質(zhì)的無證書代理重簽名方案*

楊小東,楊 平,高國娟,劉婷婷,王彩芬

(西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

代理重簽名由Blaze、Bleumer和Strauss[1]在1998年歐洲密碼學(xué)年會上提出。在這種密碼體制中，一個半可信的代理人(Proxy)可將用戶Alice的簽名轉(zhuǎn)換為用戶Bob對同一個消息的簽名，而代理人不能隨意生成Alice或Bob的簽名。但是，現(xiàn)有的代理重簽名方案大部分都是基于數(shù)字證書的傳統(tǒng)密碼系統(tǒng)和基于身份的密碼體制，存在證書管理開銷過大或密鑰生成中心完全知道用戶的私鑰等問題[2,3]。

無證書代理重簽名融合了代理重簽名和無證書密碼體制的優(yōu)點(diǎn)，不僅能實現(xiàn)簽名的轉(zhuǎn)換，還能有效克服用戶面臨的密鑰托管問題和傳統(tǒng)公鑰密碼體制中龐大證書的管理等問題。國內(nèi)外學(xué)者對代理重簽名進(jìn)行了比較深入的研究，但針對無證書代理重簽名的研究才剛剛起步。Guo等[4]將具有簽名轉(zhuǎn)換功能的代理重簽名與無證書密碼體系相結(jié)合，構(gòu)造了一個無證書代理重簽名方案，但未對方案進(jìn)行嚴(yán)格的安全性證明。Feng等[5]提出了一個可證安全的無證書盲代理重簽名方案，但Hu等[6]指出這類方案存在嚴(yán)重的安全缺陷，受托者能夠偽造任意消息的重簽名。Chen等[7]設(shè)計了一個不依賴于理想隨機(jī)預(yù)言機(jī)的無證書代理重簽名方案，但不具有聚合的特性[8]。

為了節(jié)省帶寬和提高簽名驗證效率，本文將聚合簽名和無證書代理重簽名相結(jié)合，提出了一個具有聚合性質(zhì)的無證書代理重簽名方案，并證明該方案的安全性可規(guī)約到k階多線性計算Diffie-Hellmank-MCDH(Multi-linear Computational Diffie-Hellman)困難問題假設(shè)。通過與已有的無證書代理重簽名方案比較分析，發(fā)現(xiàn)新方案具有較低的計算開銷和通信成本，更適合于移動智能終端等計算源受限的設(shè)備。通過對相關(guān)領(lǐng)域的文獻(xiàn)搜索，目前還沒有關(guān)于具有聚合特性的無證書代理重簽名研究的公開文獻(xiàn)。

2 預(yù)備知識

2.1 多線性映射

對于一個群生成器Γ(1λ,k)，其中1λ為安全參數(shù)，k為生成器允許的雙線性對運(yùn)算個數(shù)，Γ生成一個群組G=(G1,G2,…,Gk)，每個群的階均為p>2λ，gi為Gi的生成元，令g=g1。如果存在一個映射集合{ei,j:Gi×Gj→Gi+j|i,j≥1;i+j≤k}，G中的每個映射都是可計算的，并且滿足以下條件，則稱G是一個多線性映射群[9-11]。

(2)ei,j(gi,gj)=gi+j。

多線性映射可實現(xiàn)雙線性映射的所有功能，同時還具有更強(qiáng)大的功能，比如構(gòu)造任意布爾電路的屬性密碼體制等。但是，目前實現(xiàn)多線性映射的主要技術(shù)是分級編碼系統(tǒng)，存在噪聲隨著編碼的等級快速增長等問題，使得分級編碼系統(tǒng)效率較低。Zhang等[12]綜合分析多線性映射的構(gòu)造思想后發(fā)現(xiàn)，通過“去噪”技術(shù)可有效提高多線性映射的效率。

2.2 k-MCDH假設(shè)

定義1(k-MCDH假設(shè)) 若任何一個多項式時間算法解決k-MCDH問題的概率是可忽略的，則稱k-MCDH問題是困難的[8,13]。

2.3 無證書代理重簽名

一個無證書代理重簽名方案包括以下七個算法[4]：

(1) 系統(tǒng)建立：給定安全參數(shù)1λ，生成系統(tǒng)參數(shù)MPK和密鑰生成中心KGC(Key Generation Center)的主密鑰MSK。

(2) 部分私鑰提取算法：給定MPK、MSK和用戶身份ID，生成ID的部分密鑰dID。

(3) 用戶密鑰生成算法：給定MPK和用戶身份ID，生成對應(yīng)的公私鑰對(pkID,skID)。

(4) 重簽名密鑰生成算法:通過安全信道輸入dA,dB,skA,skB，但代理者無法獲得dA,dB,skA,skB。該算法為代理者生成重簽名密鑰rkA→B，其中skA和dA分別為受托者Alice的私鑰和部分密鑰，skB和dB為委托者Bob的私鑰和部分密鑰。

(5) 簽名算法： 給定消息M、Alice的部分私鑰dA和私鑰skA，生成M的原始簽名σ。

(6) 重簽名算法:輸入Alice對消息M的簽名σA和重簽名密鑰rkA→B，如果σA是M的有效簽名，該算法利用rkA→B將σA轉(zhuǎn)換為Bob對M的簽名σB；否則，輸出⊥。

(7) 簽名驗證:輸入用戶ID和公鑰pk對消息M的簽名σ，如果簽名σ有效，算法輸出1，否則輸出0。

無證書代理重簽名方案的攻擊類型可分為兩類：第一類敵手ΑΙ無法獲取系統(tǒng)的主密鑰MSK，但能替換任意用戶的公鑰；第二類敵手?、蛘莆障到y(tǒng)主密鑰MSK，但沒有替換用戶公鑰的權(quán)限。下面通過挑戰(zhàn)者C和敵手A之間的游戲來定義無證書代理重簽名的不可偽造性。

安全游戲1

(1)初始化：C通過執(zhí)行參數(shù)生成算法建立系統(tǒng)，生成KGC的主密鑰MSK，并給ΑΙ發(fā)送參數(shù)MPK。

(2)詢問階段：C通過以下預(yù)言機(jī)來回答敵手ΑΙ的一系列詢問。

①部分私鑰詢問：輸入用戶身份I，挑戰(zhàn)者C運(yùn)行部分密鑰生成算法，輸出用戶I的部分私鑰dI，并返回給敵手ΑΙ。

②公鑰詢問：輸入用戶身份I，C運(yùn)行用戶密鑰生成算法，生成用戶I的公鑰pkI和私鑰skI，并將pkI返回給敵手ΑΙ。

③私鑰詢問：輸入用戶身份I，如果I已進(jìn)行過公鑰詢問，則將對應(yīng)的skI發(fā)送給ΑΙ；否則，C運(yùn)行用戶密鑰生成算法輸出公鑰pkI和私鑰skI，并將skI返回給敵手ΑΙ。

④公鑰替換詢問：輸入用戶的身份I，敵手ΑΙ計算新的公私鑰對(pk′,sk′)來替換以前的公私鑰對(pkI,skI)。

⑤重簽名密鑰詢問：對于ΑΙ發(fā)起的關(guān)于身份(IA,IB)的重簽名詢問，C進(jìn)行部分私鑰詢問、公鑰詢問和私鑰詢問后，給ΑΙ返回重簽名密鑰生成算法輸出的重簽名密鑰rkA→B。

⑥簽名詢問：ΑΙ輸入身份I和消息M，C詢問部分私鑰詢問、公鑰詢問和私鑰詢問后，將簽名算法輸出的簽名σ返回給敵手ΑΙ。

⑦重簽名詢問：對于ΑΙ輸入的身份IA和IB、消息M以及簽名σA，C進(jìn)行重簽名密鑰詢問后，將重簽名算法輸出的重簽名σB返回給ΑΙ。

(3)偽造階段：敵手ΑΙ輸出(pkI*,M*,σ*)，若滿足以下五個條件，則稱ΑΙ贏得了第一類安全游戲。

①Verify(σ*,M*,I*,pkI*)=1；

②敵手ΑΙ從未詢問過I*的部分私鑰；

③敵手ΑΙ從未詢問過消息M*的簽名詢問；

④敵手ΑΙ從未詢問過(IA,IB)的重簽名密鑰；

⑤(σ*,M*,IA,IB)沒有進(jìn)行過重簽名詢問。

定義2如果敵手ΑΙ在上述游戲中獲勝的優(yōu)勢是可忽略的，則稱方案能夠抵抗第一類攻擊者ΑΙ的偽造攻擊[4,7]。

安全游戲2

(1) 初始化：挑戰(zhàn)者C將建立系統(tǒng)生成的參數(shù)MPK和KGC的主密鑰MSK發(fā)送給敵手?、?。

(2)?、虺瞬贿M(jìn)行部分私鑰詢問和公鑰替換詢問外，與安全游戲1相似，對挑戰(zhàn)者C發(fā)起類似的私鑰詢問、簽名詢問、重簽名密鑰詢問和重簽名詢問。

(3) 偽造階段：敵手ΑⅡ輸出(pkI*,M*,σ*)，若滿足以下四個條件，則稱?、蜈A得了第二類安全游戲。

①Verify(σ*,M*,I*,pkI*)=1；

②?、驈奈丛儐栠^消息M*的簽名詢問；

③?、驈奈丛儐栠^(IA,IB)的重簽名密鑰；

④?、驈奈丛儐栠^(σ*,M*,IA,IB)的重簽名。

定義3若敵手?、蛟谏鲜霭踩螒蛑蝎@勝的優(yōu)勢是可忽略的，則稱方案能夠抵抗第二類攻擊者?、虻膫卧旃鬧4,7]。

3 具有聚合性質(zhì)的無證書代理重簽名方案

3.1 方案描述

(1)系統(tǒng)建立。

(2)部分私鑰生成算法。

(3)用戶密鑰生成算法。

(4)重簽名密鑰生成算法。

(5)簽名算法。

(6)重簽名算法。

(7)簽名驗證算法。

給定用戶身份I、公鑰pk、消息M和簽名σ，如果e(σ,g)=e(H(I,M),pk)不成立，輸出0；否則，說明σ是一個合法簽名，輸出1。

3.2 安全性分析

下面通過模擬2.3節(jié)的兩類安全游戲，證明本方案是存在不可偽造的。定理1和定理2說明新方案是安全的，能有效抵抗針對無證書代理重簽名的兩類偽造攻擊。

定理1如果k-MCDH假設(shè)成立，那么本文新方案能抵抗第一類攻擊者ΑΙ的偽造攻擊。

證明假設(shè)敵手ΑΙ以不可忽略的概率在2.3節(jié)的第一類游戲中獲勝，則挑戰(zhàn)者B將以不可忽略的概率解決k-MCDH困難問題。

挑戰(zhàn)者B獲得一個k-MCDH實例(g,gc1,gc2,…,gck)，其中k=n+l，mi表示簽名消息的第i位，idi表示用戶身份的第i位。敵手ΑΙ和挑戰(zhàn)者B的交互過程如下：

(2) 詢問階段：ΑΙ可以向B發(fā)起一系列以下預(yù)言機(jī)的詢問。

③ 用戶私鑰詢問：當(dāng)ΑΙ詢問用戶I的私鑰skI時，如果表T3中存在(I,skI)，則B返回skI給ΑΙ；否則B從表T2中查詢相應(yīng)的值(I,pkI,xi)，令skI=xi，然后將(I,skI)添加到T3中，并將skI返回給ΑΙ。

④ 公鑰替換詢問：敵手ΑΙ將用戶I的公鑰pkI替換為pkI′時，B首先在T2中查詢(I,pkI,xi)，若含有相應(yīng)的值，則將公鑰替換為pkI=pkI′；否則B對I進(jìn)行公鑰詢問，然后令pkI=pkI′，并將改后的值添加到T2中。

⑦ 重簽名詢問：ΑΙ發(fā)起(b,B,M,σ)的重簽名詢問，如果Verify(Ib,σ,M)=0，B輸出⊥；否則，B將進(jìn)行消息M和身份IB的簽名詢問結(jié)果返回給ΑΙ。

定理2若k-MCDH假設(shè)成立，則本文新方案能抵抗第二類攻擊者?、虻膫卧旃簟?/p>

證明與定理1的證明過程基本相同，唯一的區(qū)別是ΑⅡ知道系統(tǒng)主密鑰，不需要向挑戰(zhàn)者詢問部分私鑰和用戶公鑰替換詢問。當(dāng)ΑⅡ成功輸出新方案的一個偽造時，攻擊者可以利用這個偽造解決k-MCDH問題實例，進(jìn)而證明新方案能抵抗第二類偽造攻擊。

3.3 性能分析

下面將已有的無證書代理重簽名方案與本文新方案進(jìn)行效率和性能比較，如表1所示。假設(shè)每個方案選擇相同長度的大素數(shù)p和群G1，其中L表示群G1中元素的長度，P表示一次雙線性對運(yùn)算，Y表示具有這種性質(zhì)，N表示不具有這種性質(zhì)。

Table 1 Comparison of performance and efficiency表1 性能和效率比較

從表1可以看出，本文新方案的公鑰長度、簽名長度及重簽名長度均為L，簽名驗證需要2次雙線對運(yùn)算。與另外三個方案相比，新方案具有較高的計算效率和較低的存儲開銷。

4 結(jié)束語

基于多線性映射和無證書密碼體制，本文設(shè)計了一種新的無證書代理重簽名方案，實現(xiàn)了簽名驗證的聚合特性，大大減小了簽名驗證的工作量。分析結(jié)果表明，新方案不僅具有較短的簽名和重簽名長度，還解決了證書存儲和密鑰托管等問題[14]。但是，新方案的系統(tǒng)參數(shù)較多，如何設(shè)計具有更高性能和滿足更多安全屬性的無證書代理重簽名方案，將是我們下一步工作的方向。

[1] Blaze M, Bleumer G,Strauss M.Divertible protocols and atomic proxy cryptography[C]∥Proc of Advances in Cryptology(EUROCRYPT ’98),1998:127-144.

[2] Xun Tian-tian,Yu Jia,Yang Guang-yang,et al.Key-insulated certificateless aggregate signature[J].Acta Electronica Sinica,2016,44(5):1111-1116.(in Chinese)

[3] Hu Jiang-hong, Du Hong-zhen,Zhang Jian-zhong.Analysis and improvement of certificateless aggregate signature scheme[J].Computer Engineering and Applications,2016,52(10):80-84.(in Chinese)

[4] Guo D,Ping W,Dan Y.A certificateless proxy re-signature scheme[C]∥Proc of Computer Science and Information Technology,2010:157-161.

[5] Feng Tao,Liang Yi-xin.Provably secure certificateless blind proxy re-signatures[J].Journal on Communications,2012,33(Z1):58-69.(in Chinese)

[6] Hu Xiao-ming, Yang Yin-chun,Liu Yan.Analysis and improvement of a blind proxy re-signature scheme based on standard model[J].Journal of Chinese Computer Systems,2011,32(10):2008-2011.(in Chinese)

[7] Chen L,Chen X Y,Sun Y,et al. A new certificateless proxy re-signature scheme in the standard modle[C]∥Proc of the 7the International Symposium on Computational Intelligence & Design,2014:202-206.

[8] Wang Z W,Xia A D.ID-based proxy re-signature with aggregate property[J].Journal of Information Science and Engineering,2015,31(1):1199-1211.

[9] Chen Fei,Han Yi-liang,Yang Xiao-yun,et al.A signcryption scheme from multilinear map[J].Journal of Wuhan University(Nat Sci Ed),2016,62(2):165-170.(in Chinese)

[10] Cheon J H,Han K,Lee C,et al.Cryptanalysis of the multilinear map over the integers[J].Journal of Vascular Surgery,2015,28(1):113-122.

[11] Gary S, Gentry C, Halevi S.Candidate multilinear maps from ideal lattices and applications[C]∥Proc of Advances in Cryptology(Eurocrypt 2013),2013:1-17.

[12] Zhang Fang-guo.From bilinear pairings to multilinear maps[J].Journal of Cryptologic Research,2016,3(3):211-228.(in Chinese)

[13] Albrecht M R, Farshim P,Hofheinz D,et al.Multilinear maps from obfuscation[M]∥Theory of Cryptography.Berlin:Springer Berlin Heidelberg,2016:1.

[14] Zhou Yan-wei, Yang Bo,Zhang Wen-zheng.Efficient and provide security certificateless aggregate signature scheme[J].Journal of Software,2015,26(12):3204-3214.(in Chinese)

附中文參考文獻(xiàn)：

[2] 尋甜甜,于佳,楊光洋,等.密鑰隔離的無證書聚合簽名[J].電子學(xué)報,2016,44(5):1111-1116.

[3] 胡江紅,杜紅珍,張建中.一個無證書聚合簽名方案的分析與改進(jìn)[J].計算機(jī)工程與應(yīng)用,2016,52(10):80-84.

[5] 馮濤,梁一鑫.可證安全的無證書盲代理重簽名[J].通信學(xué)報,2012,33(Z1):58-69.

[6] 胡小明,楊寅春,劉琰.一種基于標(biāo)準(zhǔn)模型的盲代理重簽名方案的安全性分析和改進(jìn)[J].小型微型計算機(jī)系統(tǒng),2011,32(10):2008-2011.

[9] 陳飛,韓益亮,楊曉元,等.一種基于多線性映射的簽密方案[J].武漢大學(xué)學(xué)報(理學(xué)版),2016,62(2):165-170.

[12] 張方國.從雙線性對到多線性映射[J].密碼學(xué)報,2016,3(3):211-228.

[14] 周彥偉,楊波,張文政.高效可證安全的無證書聚合簽名方案[J].軟件學(xué)報,2015,26(12):3204-3214.