基于強(qiáng)變色龍Hash函數(shù)的緊致安全簽名通用構(gòu)造

李 飛 高 偉 王貴林 謝冬青 唐春明

1(魯東大學(xué)數(shù)學(xué)與統(tǒng)計(jì)科學(xué)學(xué)院 山東煙臺(tái) 264025) 2(廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室(廣州大學(xué)) 廣州 510006) 3(華為新加坡研究所謝爾德實(shí)驗(yàn)室 新加坡 117674) (miss＿lifei@163．com)

2017-06-10；

2017-07-28

國家自然科學(xué)基金項(xiàng)目(61202475)；廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室開放課題(GDXXAQ2016-02)；山東省統(tǒng)計(jì)科研重點(diǎn)課題(KT16022)；魯東大學(xué)博士人才科研基金項(xiàng)目(2017) This work was supported by the National Natural Science Foundation of China (61202475), the Open Project of Guangdong Provincial Key Laboratory of Information Security Technology (GDXXAQ2016-02), the Shandong Provincial Statistics Key Project (KT16022), and the Ludong University Research Foundation for Doctoral Talents (2017).

基于強(qiáng)變色龍Hash函數(shù)的緊致安全簽名通用構(gòu)造

李 飛1,2高 偉1,2王貴林3謝冬青2唐春明2

1(魯東大學(xué)數(shù)學(xué)與統(tǒng)計(jì)科學(xué)學(xué)院 山東煙臺(tái) 264025)2(廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室(廣州大學(xué)) 廣州 510006)3(華為新加坡研究所謝爾德實(shí)驗(yàn)室 新加坡 117674) (miss＿lifei@163．com)

可證明安全性已經(jīng)成為構(gòu)造和分析密碼方案的一個(gè)基本要求.研究可證明安全密碼學(xué)領(lǐng)域的一個(gè)經(jīng)典問題，即如何在隨機(jī)預(yù)言模型下構(gòu)造可證明安全的數(shù)字簽名方案，而且其安全性可緊致地規(guī)約為某個(gè)基礎(chǔ)數(shù)學(xué)問題的困難性.首先提出一種新密碼原型，稱作強(qiáng)變色龍Hash函數(shù);然后基于強(qiáng)變色龍Hash函數(shù)，給出緊致安全數(shù)字簽名方案的一般化構(gòu)造框架及其變形，分別對(duì)應(yīng)帶狀態(tài)和無狀態(tài)2種情形;接著證明了這2種通用方案的安全性均可規(guī)約為底層強(qiáng)變色龍Hash函數(shù)的抗碰撞性.利用 RSA,CDH,IF等具體假設(shè)下的強(qiáng)變色龍Hash函數(shù)，通過所提出的一般化構(gòu)造技術(shù)，可以模塊化地構(gòu)造相應(yīng)的具體的緊致安全簽名方案.2類經(jīng)典的緊致安全簽名方案構(gòu)造范式，即Fiat-Shamir(FS)類和Full-Domain-Hash(FDH)類，可大致統(tǒng)一在所提出的構(gòu)造框架中，而且本框架可將FDH類緊致安全簽名方案解釋為相應(yīng)FS類緊致簽名方案的優(yōu)化形式.

數(shù)字簽名；可證明安全；緊致安全性；隨機(jī)預(yù)言模型；變色龍Hash函數(shù)；全域Hash簽名

在現(xiàn)代密碼學(xué)中具備可證明安全性[1]是公鑰加密[2]、數(shù)字簽名[3]、密鑰交換[4]等公鑰密碼方案設(shè)計(jì)的最基本原則之一.緊致安全性則是可證明安全性要求的進(jìn)一步提升[1].本文力圖發(fā)展一種新的通用框架，可以基于某種底層困難問題通過模塊化方式構(gòu)造緊致安全的數(shù)字簽名方案，代替?zhèn)鹘y(tǒng)的僅能實(shí)現(xiàn)松散安全性歸約的先Hash后求逆的構(gòu)造簽名框架.進(jìn)一步地，這個(gè)框架所基于的底層困難問題應(yīng)該是一個(gè)非常基礎(chǔ)且具有高度概括性的密碼原型，最好是能在陷門置換的基礎(chǔ)上增加一些最必要的密碼學(xué)性質(zhì)，而這些密碼學(xué)性質(zhì)恰恰又是使得安全性證明達(dá)到緊致要求的必要條件.事實(shí)上，這就是本文所提出一種新型密碼原型，稱作強(qiáng)變色龍Hash函數(shù).本文結(jié)合實(shí)例作了相關(guān)比較及分析，從而說明本文所給出的緊致安全簽名的一般性構(gòu)造框架具有高度概括性，既可導(dǎo)出具體的FDH類[5]緊致安全簽名方案，又可導(dǎo)出具體的FS類[6]緊致安全簽名方案.特別值得注意是，F(xiàn)DH類簽名方案和FS類簽名方案，在密碼學(xué)的相關(guān)研究領(lǐng)域中通常被認(rèn)為是2類相互獨(dú)立的一般性簽名構(gòu)造框架.本文結(jié)果表明，至少在緊致安全簽名構(gòu)造方面，二者是統(tǒng)一的：本文的統(tǒng)一框架下，F(xiàn)DH緊致簽名方案基本可以看作是對(duì)應(yīng)的FS類簽名方案的優(yōu)化結(jié)果.

本文的主要貢獻(xiàn)包括3個(gè)方面：

1) 作為理論基礎(chǔ)，本文提出了一種新的密碼原型，稱作強(qiáng)變色龍Hash函數(shù)，既可以看作經(jīng)典變色龍Hash函數(shù)概念的推廣，又可看作陷門置換的推廣，從而兼具這2種重要密碼原型的基本密碼性質(zhì).特別需要指出的是，強(qiáng)變色龍Hash函數(shù)的可逆性在傳統(tǒng)變色龍Hash函數(shù)的相關(guān)研究中極少提到，這主要是因?yàn)樽兩圚ash函數(shù)的原有應(yīng)用環(huán)境只是需要該密碼原型的抗碰撞性和“變色龍”性質(zhì).然而強(qiáng)變色龍Hash函數(shù)的可逆性在本文簽名方案的構(gòu)造中起到了不可或缺的基礎(chǔ)性作用.

2) 本文提出一種可證明安全簽名方案的一般性構(gòu)造框架，而且安全性歸約達(dá)到了緊致性要求.這個(gè)基礎(chǔ)型可證明安全簽名框架是帶狀態(tài)的，即要求簽名者記錄所有簽名歷史，避免對(duì)同一個(gè)消息產(chǎn)生2種不同的簽名.因此，本文給出了這種一般性簽名方案的改進(jìn)方法，可以非常容易地實(shí)現(xiàn)不帶狀態(tài)的緊致安全簽名方案.

3) 作為上述一般性簽名框架的應(yīng)用，本文以基于RSA的簽名方案為例，給出了3個(gè)緊致安全的RSA簽名方案，并將這些具體簽名方案與現(xiàn)有的FS類和FDH類簽名方案進(jìn)行比較，從而表明以上理論框架可以導(dǎo)出FS類簽名方案和FDH類簽名方案，其技術(shù)水平與直接構(gòu)造的同類緊致安全簽名方案持平.同時(shí)，這一理論結(jié)果也在某種程度上“否定”了FS類緊致安全簽名方案的構(gòu)造，這是因?yàn)樵诒疚牡睦碚摽蚣芟拢現(xiàn)DH類簽名方案可以看作對(duì)應(yīng)FS類數(shù)字簽名方案的優(yōu)化結(jié)果.

1 研究背景與相關(guān)工作

1988年，Goldwasser等人[7]以形式化方式給出了數(shù)字簽名的經(jīng)典定義，此定義使用了漸進(jìn)安全性(asymptotic security)的描述方法：所謂一個(gè)安全性證明就是一個(gè)歸約算法，它調(diào)用一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的簽名偽造算法構(gòu)造出一個(gè)解決底層困難問題的多項(xiàng)式時(shí)間算法，進(jìn)而由反證法得出安全性證明.漸進(jìn)安全性證明在理論上講是很好的，但是其實(shí)際應(yīng)用卻存在很大局限.當(dāng)需要評(píng)估一個(gè)數(shù)字簽名方案在給定的具體安全參數(shù)和具體攻擊資源等條件下的實(shí)際安全性時(shí)，漸進(jìn)安全性就不再適用.

受實(shí)際應(yīng)用環(huán)境對(duì)數(shù)字簽名安全強(qiáng)度精確化要求的驅(qū)動(dòng)，Bellare和Rogaway[5]在1996年提出了具體安全性(concrete security)的概念，其特點(diǎn)是力圖給出偽造簽名的困難程度與解決底層數(shù)學(xué)問題的困難程度之間的精確關(guān)系.在具體安全性框架下，可以進(jìn)一步考慮安全歸約的緊致性(tightness).在文獻(xiàn)[8]中提到，如果偽造簽名的難度與攻擊底層數(shù)學(xué)問題的難度非常接近，則稱該歸約是緊致的，否則稱該歸約是松散的.換句話說，對(duì)于緊致安全歸約來說，簽名偽造算法的成功概率和運(yùn)行時(shí)間與解決底層困難問題的成功概率和運(yùn)行時(shí)間可看作是大致相同.通過本文后面所給數(shù)字簽名方案的安全性歸約，可以更加具體地認(rèn)識(shí)和理解安全性歸約的“漸進(jìn)”、“具體”、“緊致”、“松散”等抽象概念的含義.

就數(shù)字簽名方案的安全性證明是否依賴隨機(jī)預(yù)言假設(shè)，可證明安全數(shù)字簽名方案可分為隨機(jī)預(yù)言模型下安全類和標(biāo)準(zhǔn)模型下安全類.所謂隨機(jī)預(yù)言假設(shè)[9]是在密碼方案的安全性證明中，把某個(gè)密碼學(xué)意義下Hash函數(shù)理想化為一個(gè)完全隨機(jī)函數(shù)，也就是假設(shè)存在一個(gè)各方均可訪問的隨機(jī)預(yù)言機(jī)，對(duì)于每次詢問所返回的Hash值都是完全隨機(jī)的，而且同一個(gè)數(shù)值的Hash值總是相同的.通常認(rèn)為，Hash函數(shù)僅有抗碰撞性，隨機(jī)預(yù)言模型假設(shè)該函數(shù)具有完全隨機(jī)性，而函數(shù)的隨機(jī)性是密碼學(xué)對(duì)函數(shù)性質(zhì)的最高要求，可見隨機(jī)預(yù)言假設(shè)是一個(gè)非常強(qiáng)的假設(shè).因此，在可證明安全密碼學(xué)研究領(lǐng)域，有一派研究是致力于標(biāo)準(zhǔn)安全密碼方案的構(gòu)造.目前，人們已經(jīng)構(gòu)造了不少標(biāo)準(zhǔn)模型下安全的數(shù)字簽名方案，例如文獻(xiàn)[10-13]所給出的簽名方案.與隨機(jī)預(yù)言模型下安全的數(shù)字簽名方案相比，這些標(biāo)準(zhǔn)安全的數(shù)字簽名方案往往效率較低，實(shí)際應(yīng)用中受到很大限制.本文主要考慮隨機(jī)預(yù)言模型下安全數(shù)字簽名的構(gòu)造問題，重點(diǎn)關(guān)注這些簽名方案安全性歸約的緊致性.隨機(jī)預(yù)言模型下安全的數(shù)字簽名方案基本分為2類:

1) FDH類，即全域Hash類簽名方案基本都是按照以下框架構(gòu)造的.令f是一個(gè)陷門置換函數(shù)，其陷門(即函數(shù)f的逆變換)記作f-1.令RO是一個(gè)隨機(jī)預(yù)言機(jī)，可將定義域{0,1}*的值映射到函數(shù)f的值域中的一個(gè)隨機(jī)值.對(duì)于全域Hash簽名方案[5,9]，消息m的簽名形式為σ=f-1(RO(m))，其簽名驗(yàn)證是看等式f(σ)=RO(m)是否成立.令(ε,t)分別是偽造簽名算法的成功概率和運(yùn)行時(shí)間，而(ε′,t′)分別是解決底層困難問題的算法的成功概率和運(yùn)行時(shí)間，這里解決底層問題的算法即是安全性證明的歸約算法，是調(diào)用簽名偽造算法作子函數(shù)來構(gòu)造的.對(duì)于一個(gè)可證明安全數(shù)字簽名方案及其安全歸約來說，所謂歸約(或者說安全性)緊致通常是指ε≈c1ε′,t≈c2t′,其中c1,c2均是較小常數(shù).所謂歸約松散，往往是指這些系數(shù)是歸約算法中某些參數(shù)的函數(shù)，如系數(shù)是敵手訪問隨機(jī)預(yù)言機(jī)次數(shù)的二次多項(xiàng)式.系數(shù)c1,c2有時(shí)稱作(概率、時(shí)間)緊致系數(shù).

當(dāng)陷門置換函數(shù)f是RSA函數(shù)時(shí)，即f(x)=xemodn，得到了具體的FDH簽名方案，記作RSA-FDH.對(duì)于RSA-FDH，Bellare和Rogway[5]在 1996年分析了具體安全性，但是所給出歸約非常松散，即t≈t′,ε≈(qs+qh)ε′,此處，qs和qh分別表示在定義安全性的游戲過程中敵手所作簽名詢問次數(shù)和隨機(jī)預(yù)言機(jī)詢問次數(shù).2000年，Coron[14]給出了更加緊致的安全性歸約(也就是更加緊致的安全性證明)，所給出的概率關(guān)系式為t≈t′,ε≈qsε′,即系數(shù)中不再含有隨機(jī)預(yù)言機(jī)訪問次數(shù)qh.其安全性歸約的緊致性得以提升的關(guān)鍵是利用了RSA函數(shù)的隨機(jī)自歸約性質(zhì)(random self-reducibility)[15].為了進(jìn)一步提升歸約緊致性，即去掉上式系數(shù)中的qs，Bellare和Rogway[5]提出RSA-FDH簽名方案的一種改進(jìn)形式，稱作PSS，并指出其安全性歸約是緊致的，即ε≈ε′.文獻(xiàn)[5]的核心思想是對(duì)簽名過程進(jìn)行隨機(jī)化，即在簽名中引入一個(gè)隨機(jī)因子r.在2002年，Coron[16]作了進(jìn)一步分析，在保證歸約緊致性基本不變的情況下，可以進(jìn)一步優(yōu)化隨機(jī)因子r的長度.2002年，Dodis和Reyzin[15]對(duì)以上結(jié)果進(jìn)行了系統(tǒng)的理論化整理，所依賴的基本密碼原型為無爪置換(claw-free permutations)：

① 如果作為構(gòu)建模塊的陷門置換函數(shù)f僅僅是一個(gè)黑盒形式的陷門置換，即僅考慮函數(shù)的陷門性質(zhì)，不考慮其他具體的特殊性質(zhì)，如文獻(xiàn)[14-15]所提到的RSA函數(shù)的隨機(jī)自歸約性，那么相應(yīng)的FDH簽名所能達(dá)到的歸約緊致性只能是ε≈(qs+qh)ε′.

② 如果陷門函數(shù)f可以看作是無爪置換所誘導(dǎo)的，那么FDH簽名的歸約緊致性可以進(jìn)一步優(yōu)化為ε≈qsε′.

③ 在陷門函數(shù)f由無爪置換誘導(dǎo)，且簽名中引入隨機(jī)因子r的情況下，隨機(jī)化后的FDH簽名的歸約緊致性可以再進(jìn)一步優(yōu)化為ε≈ε′，此時(shí)的簽名形式為σ=(f-1(RO(m,r)),r).

2003年，Katz和Wang[17]改進(jìn)了FDH類簽名方案，其改進(jìn)后的簽名形式為σ=(f-1(RO(m,b)),b)，其歸約緊致性基本達(dá)到最優(yōu)，即ε≈ε′，而隨機(jī)因子b只需 1比特.其代價(jià)是：所給的基礎(chǔ)簽名方案是帶狀態(tài)的，即需要簽名者記錄所有已經(jīng)簽過的消息及簽名，以免對(duì)同一個(gè)消息產(chǎn)生2個(gè)不同的簽名.同時(shí)，他們還給出了一般性轉(zhuǎn)換方法，可以將此帶狀態(tài)的簽名方案轉(zhuǎn)換為不帶狀態(tài)形式.

借鑒以上基于陷門置換構(gòu)造FDH類簽名方案的思想及實(shí)現(xiàn)緊致安全性的技術(shù)框架，基于BLS短簽名[18]，同樣可以構(gòu)造出相應(yīng)的變形方案且實(shí)現(xiàn)緊致安全性[17].值得注意的是BLS簽名及其緊致安全的變形方案所依賴的底層困難問題是CDH假設(shè)，這并不是陷門置換.如何給出一個(gè)比陷門置換更具概括性的密碼原型，并進(jìn)一步擴(kuò)展類似于隨機(jī)自歸約的性質(zhì)，并分析這些性質(zhì)與緊致歸約之間的理論聯(lián)系是緊致安全簽名方案構(gòu)造理論的一個(gè)重要方面，也是本文的一個(gè)理論性目標(biāo).

2) FS類簽名方案開始于Fiat和Shamir[6]，可以看作是與FDH類簽名并列的另外一種簽名構(gòu)造框架.FS類簽名包括了基于離散對(duì)數(shù)的簽名方案，而離散對(duì)數(shù)問題并不存在陷門.前面介紹的FDH類簽名所依托的困難問題則必須有陷門.下面首先給出FS類簽名的一般性構(gòu)造框架.

一個(gè)經(jīng)典身份認(rèn)證方案由3個(gè)操作過程構(gòu)成：

步驟1. 證明方發(fā)送承諾值Y給驗(yàn)證方，通常Y的計(jì)算需要用到保密的隨機(jī)串y;

步驟2. 驗(yàn)證方發(fā)送隨機(jī)選取的一個(gè)足夠長度的挑戰(zhàn)值c給驗(yàn)證方;

步驟3. 證明方利用其私鑰及之前的內(nèi)部隨機(jī)信息y計(jì)算并發(fā)送一個(gè)應(yīng)答值z(mì)給驗(yàn)證方，驗(yàn)證方檢驗(yàn)對(duì)話副本(Y,c,z)是否合法.

1999年，Micali和Reyzi[8]提出了一種稱作SWAP的通用型轉(zhuǎn)化框架，可以模塊化地構(gòu)造具有緊致安全性的FS類簽名方案.SWAP轉(zhuǎn)換框架與以上Fiat-Shamir轉(zhuǎn)換框架在形式上類似，可看作Fiat-Shamir轉(zhuǎn)換的變形，因此也將其歸為FS類簽名.SWAP轉(zhuǎn)換框架對(duì)于底層的典型身份認(rèn)證方案提出了特殊要求：證明方在不需要知曉y(計(jì)算承諾時(shí)所選擇的隨機(jī)秘密值)的條件下，可以直接由承諾Y和挑戰(zhàn)c計(jì)算出應(yīng)答值z(mì).在SWAP轉(zhuǎn)換框架中，簽名形式為(c,z).若(Y,c,z)是合法的協(xié)議副本，則(c,z)就是合法簽名，此處Y=H(c,m)，H是密碼學(xué)意義下的Hash函數(shù)(在安全性證明中需理想化為隨機(jī)預(yù)言機(jī)).Micali和Reyzin[8]利用SWAP轉(zhuǎn)換構(gòu)造了一種基于整數(shù)分解難題的簽名方案，其安全性歸約關(guān)系為ε≈ε′，其中ε′表示歸約算法解決整數(shù)分解問題的成功概率.

2016年，Abdalla等人[22]提出了所謂的損耗性身份認(rèn)證方案，并證明了針對(duì)這類損耗性身份認(rèn)證方案應(yīng)用Fiat-Shamir轉(zhuǎn)換，可以得到緊致安全的數(shù)字簽名方案.分別基于理想格上的最短向量問題、c確定型離散對(duì)數(shù)問題(c-decisional discrete logarithm)和子集和問題(subset sum)等數(shù)學(xué)難題，Abdalla等人給出3種具體的損耗性身份認(rèn)證方案[22]及對(duì)應(yīng)的緊致安全簽名方案.大致來說，在一個(gè)損耗性身份認(rèn)證方案中，證明方的公鑰可以采用2種不可區(qū)分形式中的任何一種，分別稱為正常型(normal)和損耗型(lossy).對(duì)于文獻(xiàn)[22]所給出的數(shù)字簽名方案來說，安全性歸約的關(guān)系式表示為ε≈ε′，此處ε′是敵手成功攻破損耗性身份認(rèn)證方案的密鑰不可區(qū)分性質(zhì)的概率，ε仍然是偽造簽名算法的成功概率，可見此類簽名方案也達(dá)到了緊致安全性.值得注意的是，一般來說，損耗性身份認(rèn)證方案的密鑰不可區(qū)分性質(zhì)往往與確定性(decisional)困難問題相關(guān).從這類簽名所依賴的具體困難問題來看，其應(yīng)用范圍具有很大限制性.

2016年Bellare等人[23]研究了由身份認(rèn)證方案到緊致安全簽名的一般化構(gòu)造框架，這是FS轉(zhuǎn)換框架的改進(jìn)模式.Bellare等人首先給出了身份認(rèn)證方案的安全性定義框架，而這一框架又細(xì)分出4種具體形式，然后給出了3種FS類轉(zhuǎn)換框架并分析、比較了這些框架的相關(guān)指標(biāo).需要指出的是身份認(rèn)證方案并不是最底層的密碼方案，其安全性定義及安全性分析是非常復(fù)雜的.從密碼學(xué)理論角度看，把緊致安全簽名方案的構(gòu)造歸為某類更加簡(jiǎn)練的密碼原型的構(gòu)造(例如作為一種底層構(gòu)造模塊，本文給出的強(qiáng)變色龍Hash函數(shù)就比身份認(rèn)證方案更為簡(jiǎn)練)是需要進(jìn)一步研究的理論課題.

另外，Goh和Jarecki在2003年提出了一種基于CDH困難問題的FS類簽名方案[24]，之后針對(duì)該方案又作了進(jìn)一步的改進(jìn)[25].這2個(gè)FS類簽名方案的安全性歸約均基本達(dá)到了最優(yōu)緊致性，即ε≈ε′，此處ε′是歸約算法解決CDH困難問題的成功概率，而ε仍然是偽造簽名算法的成功概率.在文獻(xiàn)[17]中，Katz和Wang還提出了一種基于DDH困難問題 (decisional Diffie-Hellman)的FS類簽名，其安全性可緊致地歸約為DDH問題的困難性，在簽名長度和計(jì)算效率方面均優(yōu)于文獻(xiàn)[24-25]所給的基于CDH困難問題的FS類簽名方案.

2 預(yù)備知識(shí)

本節(jié)介紹數(shù)字簽名語法定義及安全性定義[5,7].

定義1. 一個(gè)數(shù)字簽名方案

DS=(S.Gen,S.Sign,S.Vrf)

由3個(gè)概率多項(xiàng)式時(shí)間算法組成：

1) (pk,sk)←S.Gen(1λ).這是密鑰生成算法.輸入安全參數(shù) 1λ，輸出公鑰pk和私鑰sk.

2)σ←S.Sign(sk,m).這是數(shù)字簽名生成算法.輸入待簽名消息m和私鑰sk，輸出簽名σ.

3)b←S.Vrf(pk,m,σ).這是數(shù)字簽名驗(yàn)證算法.輸入消息m、簽名σ和公鑰pk，輸出一個(gè)比特b，表示σ是否合法.

定義2. 稱一個(gè)數(shù)字簽名方案在選擇消息攻擊下是(t,ε) 不可偽造的，如果對(duì)于任何的運(yùn)行時(shí)間不超過t的偽造者A，下述概率不等式總成立：

Pr[S.Vrf(pk,m*,σ*)=1∧m*?S*|

(sk,pk)←RS.Gen(1k);

(σ*,m*)←RAOS ign()(pk)]<ε,

此處S*表示偽造者已經(jīng)索得簽名的所有消息集合，即不存在偽造算法滿足運(yùn)行時(shí)間小于等于t，成功概率大于等于ε.

3 強(qiáng)變色龍Hash函數(shù)

本節(jié)提出強(qiáng)變色龍Hash函數(shù)的定義，并給出3個(gè)具體方案.

3.1強(qiáng)變色龍Hash函數(shù)定義

定義3. 一個(gè)強(qiáng)變色龍Hash函數(shù)(族):

SCH=(H.Gen,H.Hash,H.Ivt)

由3個(gè)概率多項(xiàng)式時(shí)間算法組成：

1) (hk,itd)←H.Gen(1λ).該算法為密鑰生成算法，其輸入為安全參數(shù)λ，其輸出是Hash密鑰hk和求逆陷門itd.Hash密鑰hk決定了消息集合S、隨機(jī)種子集合R和Hash值集合H.每個(gè)Hash密鑰都確定了變色龍Hash函數(shù)(族)中的一個(gè)具體變色龍Hash函數(shù).在不產(chǎn)生歧義的情況下，一個(gè)Hash函數(shù)可以指一個(gè)Hash函數(shù)族，也可以指一個(gè)具體的Hash函數(shù).

2) (h,r)←H.Hash(hk,s).該算法為強(qiáng)變色龍Hash函數(shù)的Hash算法.對(duì)于待Hash消息s∈RS及Hash密鑰hk，選擇一個(gè)隨機(jī)數(shù)r∈RR，然后計(jì)算Hash值h←Hashh k(s,r)∈H，最后返回Hash值及隨機(jī)種子(h,r).此處，明確區(qū)分了隨機(jī)化算法H.Hash(hk,s)和確定算法Hashh k(s,r).二者本質(zhì)上沒有區(qū)別，只是為了相關(guān)敘述的方便.

3)r←H.Ivt(hk,itd,h,s).此算法稱作強(qiáng)變色龍Hash函數(shù)的求逆算法.對(duì)于給定的Hash值h和被Hash消息s，該算法計(jì)算隨機(jī)種子r∈RR使得h=Hashh k(s,r).該算法的存在性正是強(qiáng)變色龍Hash函數(shù)的“強(qiáng)變色性”的形式化描述.也就是說，借助陷門itd，該算法能夠提供相應(yīng)的隨機(jī)值r，從而可以將任意Hash值h解讀為任意消息s的Hash值，特別是此時(shí)不需要知道h的另外原象.

抗碰撞性：稱強(qiáng)變色龍Hash函數(shù)(族)是抗碰撞的，如果對(duì)于任何運(yùn)行時(shí)間不超過的概率多項(xiàng)式時(shí)間敵手A，下面過程的成功概率總滿足：

即不存在碰撞算法滿足運(yùn)行時(shí)間小于等于t，成功概率大于等于ε.

為了更好地理解這一新概念,對(duì)于上述形式化定義,下面分析強(qiáng)變色龍Hash函數(shù)與其他相關(guān)密碼學(xué)概念之間的關(guān)系.

1) 強(qiáng)變色龍Hash函數(shù)和傳統(tǒng)變色龍Hash函數(shù)[26]二者之間的關(guān)系.對(duì)于強(qiáng)變色龍Hash函數(shù)來說，其陷門可以用來對(duì)任意的Hash值h，求出原象對(duì)(s′,r′)；而對(duì)于傳統(tǒng)變色龍Hash函數(shù)來說，其陷門可以用來對(duì)任意的原象對(duì)(s,r)，求出第二原象對(duì)(s′,r′).換句話說，用強(qiáng)變色龍Hash函數(shù)的陷門可以任意求逆(從多個(gè)符合條件的原象中，選擇一個(gè))，而傳統(tǒng)變色龍Hash函數(shù)，其陷門可以計(jì)算碰撞.通常，求逆算法必定可以平凡地導(dǎo)出求碰撞算法，反之則不然.因此，以上定義稱為強(qiáng)變色龍Hash函數(shù).需要特別指出的是，有些具體的變色龍Hash函數(shù)本身也是強(qiáng)變色龍Hash函數(shù)，但是當(dāng)時(shí)應(yīng)用環(huán)境并未牽涉到“強(qiáng)”變色性，因此并未明確提出該性質(zhì).

2) 作為一種底層的密碼原型概念，強(qiáng)變色龍Hash函數(shù)可以看作陷門單向函數(shù)概念的拓展.事實(shí)上，在函數(shù)Hashh k(s,r)和H.Ivt(hk,itd,h,s)中固定變量s，將會(huì)自然誘導(dǎo)出一個(gè)陷門單向函數(shù)f及其逆函數(shù)g:

fh k,s(r)=Hashh k(s,r)，r∈R，

gh k,s,itd(h)=H.Ivt(hk,itd,h,s)，h∈H.

3) 作為一種基礎(chǔ)密碼原型，強(qiáng)變色龍Hash函數(shù)可以看作無爪置換(claw-free permutations)[15]的一種擴(kuò)展.事實(shí)上，對(duì)于函數(shù)Hashh k(s,r)，分別給變量s不同的賦值s=s0,s=s1，將會(huì)自然誘導(dǎo)出相應(yīng)的一對(duì)函數(shù):

fh k,s0(r)=Hashh k(s0,r)，r∈R，

fh k,s1(r)=Hashh k(s1,r)，r∈R.

對(duì)于上述函數(shù)對(duì)，根據(jù)抗碰撞性質(zhì)，計(jì)算r0,r1使得fh k,s0(r0)=fh k,s1(r1) 在計(jì)算上是不可行的.從而,{(fi:R→H,gi:R→H)|fi(r)=fh k,s0(r),fi(r)=fh k,s1(r),r∈R}構(gòu)成了一個(gè)無爪置換族[15].簡(jiǎn)言之，無爪置換族是強(qiáng)變色龍族Hash函數(shù)的簡(jiǎn)化形式.特別地，當(dāng)s的取值集合S只有2個(gè)元素，自然得出無爪置換族.

3.2強(qiáng)變色龍Hash函數(shù)的具體方案

本節(jié)給出強(qiáng)變色龍Hash函數(shù)的3個(gè)具體構(gòu)造，分別基于CDH,RSA和IF等常見困難問題.通過這些具體構(gòu)造，容易得出初步結(jié)論：

1) 從刻劃密碼學(xué)概念的角度來講，強(qiáng)變色龍Hash函數(shù)是對(duì)傳統(tǒng)變色龍Hash函數(shù)的加強(qiáng)，而且強(qiáng)化后的性質(zhì)將在后續(xù)簽名方案構(gòu)造中發(fā)揮重要作用.

2) 從方案構(gòu)造角度來說，以往的某些變色龍Hash函數(shù)本身具有“強(qiáng)變色”的性質(zhì)，只是由于缺乏該性質(zhì)的應(yīng)用背景驅(qū)動(dòng)，而沒有提出“強(qiáng)變色”性質(zhì)的抽象概念.

本節(jié)只是給出函數(shù)的方案描述，各相關(guān)性質(zhì)易于驗(yàn)證，其證明不作贅述.

3.2.1SCH-CDH: 基于雙線性對(duì)的強(qiáng)變色龍Hash函數(shù)構(gòu)造

根據(jù)文獻(xiàn)[27]中基于雙線性對(duì)的無密鑰泄漏變色龍Hash函數(shù)，容易得出強(qiáng)變色龍Hash函數(shù)：

1)H.Gen(1λ).選取2個(gè)乘法群G,GT及相關(guān)雙線性對(duì)e:G×G→GT，隨機(jī)選擇α,β←Rq，并計(jì)算其中G=〈g〉，|G|=q，q是素?cái)?shù).令Hash密鑰和求逆陷門為

hk=(g,gα,gβ)，

itd=α.

2)H.Hash(hk,s).對(duì)于給定的Hash密鑰hk=(g,gα,gβ)，待Hash消息s∈q，隨機(jī)選擇γ←Rq，并計(jì)算r=(gαγ,gγ)，然后計(jì)算Hash值:

h=Hashg,gα,gβ(s,r)=(gβ)sgγ.

之后返回Hash值h及隨機(jī)信息r=(gα γ,gγ).只有當(dāng)h=(gβ)sgγ和e(g,r′)=e(r″,gα)(此式用于保證的確存在γ使得r=(r′,r″)=(gαγ,gγ))同時(shí)成立時(shí)，才認(rèn)為h為s的Hash值.

3)H.Ivt(hk,itd,h,s).對(duì)于給定的Hash值h和被Hash消息s，計(jì)算：

r″=h(gβ)-s,

r′=r″α.

最后輸出r=(r′,r″).輸出值的正確性為

Hashg,gα,gβ(s,r)=(gβ)sgγ=(gβ)sh(gβ)-s=h，
e(g,r′)=e(r″,gα).

3.2.2SCH-RSA: 基于RSA困難問題的強(qiáng)變色龍Hash函數(shù)構(gòu)造

根據(jù)文獻(xiàn)[28]中基于RSA的無密鑰泄漏變色龍Hash函數(shù)，容易得出強(qiáng)變色龍Hash函數(shù)：

1)H.Gen(1λ).根據(jù)輸入的安全參數(shù)λ，選擇同樣長度的不同素?cái)?shù)p,q，并計(jì)算n=pq;然后，選擇足夠大的素?cái)?shù)e>l，此處參數(shù)l保證e足夠大;接著計(jì)算d，使得ed=1 mod (p-1)(q-1);最后，隨機(jī)選擇x←Rq，并計(jì)算求逆陷門和Hash密鑰:

itd=d,

hk=(n,e,xe).

2)H.Hash(hk,s).給定Hash密鑰hk和被Hash消息s∈e，該算法選擇r←R*n，計(jì)算Hash值為

h=Hashh k(s,r)=(xe)sremodn.

之后，返回Hash值及隨機(jī)信息(h,r).

3)H.Ivt(hk,itd,h,s).對(duì)于給定的Hash值h和被Hash消息s，利用陷門信息itd=d，計(jì)算隨機(jī)種子：

r=(h(xe)-s)dmodn.

該輸出值的正確性為

Hashh k(s,r)=(xe)sremodn=

(xe)s(h(xe)-s)d emodn=hmodn.

3.2.3SCH-IF: 基于整數(shù)分解難題的強(qiáng)變色龍Hash函數(shù)構(gòu)造

根據(jù)文獻(xiàn)[29]中基于IF的無密鑰泄漏變色龍Hash函數(shù)，容易得出強(qiáng)變色龍Hash函數(shù)：

1)H.Gen(1λ).首先隨機(jī)選擇同樣長度的不同素?cái)?shù)p,q，使得p,q=3 mod 4，計(jì)算n=pq，確定一個(gè)輔助的整數(shù)型參數(shù)τ.如此形式的RSA模n通常稱作Blum-Williams整數(shù)或Blum整數(shù)[1,23].隨機(jī)選擇x∈QRn，令Hash密鑰hk和求逆陷門itd分別為

hk=(n,τ,x2τ),itd=(p,q).

2)H.Hash(hk,s).給定待Hash消息s∈R2τ和Hash密鑰hk，隨機(jī)選擇r←R*n，然后計(jì)算Hash值：

h=Hashh k(s,r)=(x2τ)sr2τmodn.

之后，輸出Hash值h及隨機(jī)信息r.

3)H.Ivt(hk,itd,h,s).對(duì)于Hash值h和被Hash消息s，該算法利用陷門信息itd=(p,q)，計(jì)算與之對(duì)應(yīng)的隨機(jī)信息：

r=(h×(x2τ)-s)modn.

該輸出值的正確性為

Hashh k(s,r)=(x2τ)sr2τmodn=

(x2τ)s(h(x2τ)-s)modn=hmodn.

4 帶狀態(tài)的緊致安全簽名方案

本節(jié)提出由強(qiáng)變色龍Hash函數(shù)構(gòu)造緊致安全簽名方案的2種一般性框架，分別對(duì)應(yīng)帶狀態(tài)和不帶狀態(tài)2種情形，并在隨機(jī)預(yù)言模型下分析其緊致安全性.

4.1帶狀態(tài)的緊致安全簽名方案

給定任意一個(gè)強(qiáng)變色龍Hash函數(shù)族SCH=(H.Gen,H.Hash,H.Ivt)，可以構(gòu)造如下帶狀態(tài)的數(shù)字簽名方案，記作SCH-2-DS0:

1)S.Gen(1λ).首先，運(yùn)行強(qiáng)變色龍Hash函數(shù)的密鑰生成算法(hk,itd)←RH.Gen(1λ)，令簽名公鑰和私鑰分別為

pk=hk,

sk=itd.

2)S.Sign(sk,m).對(duì)于待簽名的消息m∈M，首先檢查該消息是否已經(jīng)簽過.如果是，則返回之前的簽名;否則，根據(jù)簽名的公鑰pk=hk和私鑰sk=itd，計(jì)算

h←H1(m),

r←H.Ivt(hk,itd,h,s).

然后返回簽名σ←(s,r).同時(shí)，記錄此次的消息及其簽名.注意，每次簽名前需要檢查之前的簽名，且在簽名后作記錄，就是所謂的帶狀態(tài)性(stateful).簡(jiǎn)言之，該簽名方案就是對(duì)消息的普通Hash值進(jìn)行變色龍Hash函數(shù)的求逆.這種數(shù)字簽名構(gòu)造框架與最通常的Full-Domain-Hash簽名[9,14]非常相似.

3)S.Vrf(pk,m,σ).對(duì)于給定的公鑰pk=hk，驗(yàn)證σ=(s,r)是否為消息m的合法簽名，即驗(yàn)證是否成立:

H1(m)=Hashh k(s,r).

定理1. 如果底層的強(qiáng)變色龍Hash函數(shù)SCH=(H.Gen,H.Hash,H.Ivt)是(t′,ε′)抗碰撞的，那么上述簽名方案:

SCH-2-DS0=(S.Gen,S.Hash,S.Vrf)

就是(t,ε)存在性不可偽造的，其中:

t′=t+qHash×tHash,

其中，qHash表示敵手訪問隨機(jī)預(yù)言機(jī)OH1(·)的次數(shù)，而tHash表示H.Hash(·)的運(yùn)行時(shí)間.

證明. 證明采用反證法.對(duì)于簽名方案SCH-2-DS0，假設(shè)存在一個(gè)存在性偽造算法F，其運(yùn)行時(shí)間為t，其概率為ε，敵手攻擊簽名方案的具體過程在定義2已經(jīng)給出.下面構(gòu)造一個(gè)針對(duì)底層強(qiáng)變色龍Hash函數(shù)SCH的尋找碰撞算法，記作C，其概率為ε′，其運(yùn)行時(shí)間約為t′.算法C模擬簽名安全性定義中的挑戰(zhàn)者，以子程序形式調(diào)用偽造算法F，最后給出一對(duì)碰撞.

首先，作為強(qiáng)變色龍Hash函數(shù)的攻擊者，C從它自己的挑戰(zhàn)者處獲得Hash密鑰hk，令簽名公鑰為pk=hk，并把該公鑰pk及其相關(guān)的輔助性公開參數(shù)發(fā)送給F.C初始化一個(gè)計(jì)數(shù)器f=0，用來跟蹤記錄在整個(gè)游戲期間各方訪問隨機(jī)預(yù)言機(jī)OH1(·)的次數(shù)，對(duì)重復(fù)消息的Hash函數(shù)值(隨機(jī)預(yù)言機(jī)返回的值)只計(jì)一次.

C按照如下方式來模擬簽名預(yù)言機(jī).不失一般性，我們假設(shè)所有提供給簽名預(yù)言機(jī)OS ign(·)的待簽名消息各不相同.為了模擬簽名OS ign(m)，C首先訪問隨機(jī)預(yù)言機(jī)OH1(·)，獲得Hash值H1(m)，此處的隨機(jī)預(yù)言機(jī)也是由C本身模擬.根據(jù)上述對(duì)于隨機(jī)預(yù)言機(jī)OH1(·)的模擬過程，存在(s,r)使得H1(m)=Hashh k(s,r)，而(s,r)正是由C本身選取.因此，C知曉(s,r)，可直接把消息m的簽名定為σ←(s,r)，并將σ作為應(yīng)答返回給偽造者F.上述模擬與實(shí)際的簽名算法完全一致.

最后，敵手F返回消息m*及其偽造簽名σ*.如S.Vrf(pk,σ*,m*)≠1，C則中斷算法執(zhí)行，宣布失敗;如果S.Vrf(pk,σ*,m*)=1，根據(jù)方案SCH-2-DS0中S.Vrf的算法描述，可以知道h*=Hashh k(s*,r*)，此處σ*=(s*,r*).根據(jù)H1(m*)的隨機(jī)預(yù)言機(jī)模擬過程，C知道另外一對(duì)碰撞值(s*′,r*′)使得:

Hashh k(s*,r*)=Hashh k(s*′,r*′).

C把(s*′,r*′)和(s*,r*)作為一對(duì)碰撞傳給他本身的挑戰(zhàn)者.如此以來，只要(s*′,r*′)≠(s*,r*)，那么C就攻破了強(qiáng)變色龍Hash函數(shù)的抗碰撞性質(zhì).

再來分析C的運(yùn)行時(shí)間.C的運(yùn)行時(shí)間包括偽造算法F的運(yùn)行時(shí)間和C模擬簽名預(yù)言機(jī)和隨機(jī)預(yù)言機(jī)的時(shí)間.其中，一次簽名預(yù)言機(jī)的模擬主要就是一次隨機(jī)預(yù)言機(jī)的模擬，而隨機(jī)預(yù)言機(jī)的一次模擬就是一次Hash函數(shù)Hashh k(s,r)的計(jì)算，其運(yùn)行時(shí)間記作tHash.同時(shí)，對(duì)于C中的一些瑣碎的計(jì)算不予考慮，如某些結(jié)果的記錄和查詢.因此，C的運(yùn)行時(shí)間為t′=t+qHash×tHash.因此，所構(gòu)造算法C是一個(gè)運(yùn)行時(shí)間為t′、成功概率為ε′的計(jì)算碰撞算法，這與變色龍Hash函數(shù)的(t′,ε′)抗碰撞性矛盾.

證畢.

4.2不帶狀態(tài)的緊致安全簽名方案

基于以上的帶狀態(tài)緊致安全簽名方案SCH-2-DS0，作如下修改可以得到一個(gè)不帶狀態(tài)的緊致安全簽名方案，記作SCH-2-DS1.

在簽名算法中，將操作h←H1(m)改為

h←H1(m,s,s′)，

在驗(yàn)證算法S.Vrf(pk,m,σ)中，根據(jù)以上密鑰生成算法和簽名算法中的改動(dòng)作相應(yīng)的修改.鑒于這些修改的平凡性，此處不作贅述.

定理2. 如果底層的強(qiáng)變色龍Hash函數(shù)

SCH=(H.Gen,H.Hash,H.Ivt)

是(t′,ε′)抗碰撞的，那么上述簽名方案

SCH-2-DS1=(S.Gen,S.Hash,S.Vrf)

就是(t,ε)存在性不可偽造的，其中:

t′=t+qHash×tHash,

其中，qHash表示敵手訪問隨機(jī)預(yù)言機(jī)OH1(·)的次數(shù)，而tHash表示H.Hash(·)的運(yùn)行時(shí)間.

證明. 與定理1的證明類似，此處從略.

證畢.

4.3緊致安全簽名方案實(shí)例

本節(jié)以基于RSA難題的強(qiáng)變色龍Hash函數(shù)為例，首先設(shè)計(jì)一個(gè)基于RSA的具體簽名方案，然后考慮這一簽名方案的變形，并比較這些方案與現(xiàn)有的相關(guān)方案.借此說明，上述基于強(qiáng)變色龍Hash函數(shù)的一般化簽名方案具有良好的理論概括性和實(shí)際應(yīng)用價(jià)值.

對(duì)于前面提出的基于RSA假設(shè)的強(qiáng)變色龍Hash函數(shù)SCH-RSA，應(yīng)用上述的數(shù)字簽名構(gòu)造框架SCH-2-DS0，得到帶狀態(tài)數(shù)字簽名方案DS-RSA：

1)S.Gen(1λ).本方案相關(guān)符號(hào)與前面強(qiáng)變色龍Hash函數(shù)SCH-RSA一致，公鑰和私鑰分別為

pk=(n,e,xe),

sk=(x,d),

2)S.Sign(sk,m).假設(shè)消息m之前未曾簽過，計(jì)算簽名

σ=(H1(m)d×x-s,s)，

3)S.Vrf(pk,m,σ).為了驗(yàn)證σ=(s,r)是否為消息m的簽名，只需驗(yàn)證是否成立等式:

H1(m)=(xe)sremodn.

上述簽名是直接套用簽名框架SCH-2-DS0的結(jié)果，因此具有帶狀態(tài)的缺點(diǎn).利用不帶狀態(tài)的簽名框架SCH-2-DS1，并作適當(dāng)優(yōu)化，可以構(gòu)造出如下2個(gè)基于RSA假設(shè)的不帶狀態(tài)簽名方案.

σ=(H1(m,s,s′)d×x-s,s,s′)，

σ=(H1(m,s′)d,s′)，

由以上2式顯然可見，在計(jì)算上講，只是有一次模乘法的差別，這與d次模冪運(yùn)算相比，基本可以忽略.因此，計(jì)算差別可以忽略.在簽名長度上看，二者的簽名長度只有1比特的差別，考慮到緊致性方面的極細(xì)微差別，1比特的差別基本可以忽略.

σ=(H1(m,s)d×x-s,s),

此處s←Re.以上簽名形式與文獻(xiàn)[8]中基于RSA的緊致安全簽名方案完全一致，該方案是把文獻(xiàn)[8]的一般化簽名框架(稱之為SWAP轉(zhuǎn)換)應(yīng)用在GQ身份認(rèn)證方案[30]而得到的.注意:SWAP提出的背景是為了解決Fiat-Shamir類簽名方案的緊致安全性問題.事實(shí)上，一般的Fiat-Shamir類簽名方案都不具有緊致安全性.SWAP轉(zhuǎn)換是Fiat-Shamir轉(zhuǎn)換的一種變形，僅適用于一類特殊的身份認(rèn)證方案，可以將其轉(zhuǎn)化為緊致安全的FS類簽名方案.

4.4緊致安全簽名構(gòu)造框架的理論意義

通過4.3節(jié)具體例子，對(duì)于本文提出的基于強(qiáng)變色龍Hash的一般化簽名方案的構(gòu)造框架，作4項(xiàng)探討：

1) 根據(jù)4.3節(jié)基于RSA難題的3個(gè)具體簽名方案，同樣可以模塊化地構(gòu)造出基于雙線性群上CDH 難題的具體簽名方案和基于整數(shù)分解難題的具體簽名方案，既包含F(xiàn)DH類緊致安全簽名，又包括FS類緊致安全簽名.

2) 本文所提出的基于強(qiáng)變色龍Hash函數(shù)的緊致安全簽名的框架，在理論上統(tǒng)一了FDH類和FS類 這2類緊致安全簽名方案，從而指出了緊致安全簽名方案要求底層密碼原型所必須具有的最關(guān)鍵性質(zhì).事實(shí)上，在數(shù)字簽名構(gòu)造理論領(lǐng)域，人們通常把FS類簽名和FDH類簽名看作2類獨(dú)立的簽名構(gòu)造技術(shù).

3) 在本文所提出的框架下，F(xiàn)S類緊致安全簽名[8]和PDH類緊致安全簽名，可以看作是以不同方式調(diào)整框架中的相關(guān)參數(shù)而形成的不同的特殊結(jié)果.特別是，F(xiàn)DH類簽名方案可以看作是比相應(yīng)的FS類簽名方案更為優(yōu)化的形式.從這層意義上講，本文的一般性理論結(jié)果粗略地否定了FS類緊致安全簽名研究分支[3]的研究意義.

4) 本文所提出的框架具有非常高的概括性，從而具有廣泛的應(yīng)用性，其根本原因是最為底層的密碼原型具有很高抽象性和概括性.事實(shí)上，它可以誘導(dǎo)出陷門置換、無爪置換[15]等非常基礎(chǔ)的密碼原型.

5 結(jié) 論

本文研究了可證明安全密碼學(xué)領(lǐng)域的一個(gè)經(jīng)典問題，即如何由底層困難問題出發(fā)，高效且直觀地構(gòu)造緊致安全數(shù)字簽名方案.首先擴(kuò)展了傳統(tǒng)變色龍Hash函數(shù)的概念，提出了強(qiáng)變色龍Hash函數(shù)的密碼原型，用作底層困難問題的抽象模型，力圖刻劃底層困難問題的基礎(chǔ)密碼性質(zhì)，而這些性質(zhì)又是實(shí)現(xiàn)緊致安全簽名的關(guān)鍵所在.進(jìn)而提出了一種直觀、簡(jiǎn)練的轉(zhuǎn)換框架，可將強(qiáng)變色龍Hash函數(shù)轉(zhuǎn)換為帶狀態(tài)的緊致安全簽名方案.進(jìn)一步給出了對(duì)應(yīng)的不帶狀態(tài)緊致安全簽名方案變形，并指出所提出的通用構(gòu)造框架在某種程度上統(tǒng)一了FS類和FDH類2種經(jīng)典的數(shù)字簽名構(gòu)造框架(就緊致安全簽名的情況來說)，而之前密碼學(xué)領(lǐng)域通常認(rèn)為它們是互相獨(dú)立的2種簽名構(gòu)造范式.同時(shí)在本文所給的一般性框架下，F(xiàn)DH類緊致簽名還可以看作相應(yīng)FS類緊致簽名的優(yōu)化變形.

[1] Feng Dengguo. Research on theory and approach of provable security[J]. Journal on Software, 16(10): 1743-1756 (in Chinese)

(馮登國. 可證明安全性理論與方法研究[J]. 軟件學(xué)報(bào), 2005, 16(10): 1743-1756)

[2] Xu Peng, Cui Guohua, Lei Fengyu. An efficient and provably secure IBE scheme without bilinear pairing[J]. Journal on Computer Research and Development, 2008, 45(10): 1687-1695 (in Chinese )

(徐鵬, 崔國華, 雷鳳宇. 非雙線性映射下一種實(shí)用的和可證明安全的IBE方案[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(10): 1687-1695)

[3] Chen Ming, Yuan Shaoliang. Provably secure identiy-based multi-proxy signature scheme in standard model[J]. Journal of Computer Research and Development, 2016, 53(8): 1879-1892 (in Chinese )

(陳明, 袁少良. 標(biāo)準(zhǔn)模型下可證明安全的基于身份多代理簽名[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8): 1879-1892)

[4] Wen Weiqiang, Wang Libin. A strongly secure lattice-based key exchange protocol[J]. Journal of Computer Research and Development, 2015, 52(10): 2258-2269 (in Chinese)

(溫偉強(qiáng), 王立斌. 基于格問題的強(qiáng)安全密鑰交換協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(10): 2258-2269)

[5] Bellare M, Rogaway P. The exact security of digital signatures-how to sign with RSA and Rabin[G] //LNCS 1070: Advances in Cryptology (EUROCRYPT 1996). Berlin: Springer, 1996: 399-416

[6] Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems[G] //LNCS 263: Advances in Cryptology (CRYPTO’86). Berlin: Springer, 1987: 186-194

[7] Goldwasser S, Micali S, Rivest R. A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM Journal on Computing, 1988, 17(2): 281-308

[8] Micali S, Reyzin L. Improving the exact security of digital signature schemes[J]. Journal of Cryptology, 1999, 15(1): 1-18

[9] Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of ACM Conf on Computer & Communication Security. New York: ACM, 1993: 62-73

[10] Cramer R, Shoup V. Signature schemes based on the strong RSA assumption[J]. ACM Trans on Information & System Security, 1999, 3(3): 161-185

[11] Gennaro R, Halevi S, Rabin T. Secure Hash-and-sign signatures without the random oracle[G] //LNCS 1592: Advances in Cryptology (EUROCRYPT’99). Berlin: Springer, 1999: 123-139

[12] Hohenberger S, Waters B. Short and stateless signatures from the RSA assumption[G] //LNCS 5677: Advances in Cryptology (CRYPTO 2009). Berlin: Springer, 2009: 654-670

[13] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[J]. Journal of Cryptology, 2012, 25(4): 601-639

[14] Coron J S. On the exact security of full domain Hash[G] //LNCS 1880: Advances in Cryptology (CRYPTO 2000). Berlin: Springer, 2000: 229-235

[15] Dodis Y, Reyzin L. On the power of claw-free permutation[G] //LNCS 2576: Proc of the 3rd Int Conf on Security in Communication Networks. Berlin: Springer, 2002: 55-73

[16] Coron J S. Optimal security proofs for PSS and other signature schemes[G] //LNCS 2332: Advances in Cryptology (EUROCRYPT 2002). Berlin: Springer, 2002: 272-287

[17] Katz J, Wang Nan. Efficiency improvements for signature schemes with tight security reductions[C] //Proc of the 10th ACM Conf on Computer and Communications Security. New York: ACM, 2003: 155-164

[18] Boneh D, Lynn B, Shacham H. Short signatures from the weil pairing[J]. Journal of Cryptology, 2004, 17(4): 297-319

[19] Bellare M, Palacio A. GQ and schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks[G] //LNCS 2442: Advances in Cryptology (CRYPTO’02). Berlin: Springer, 2002: 162-177

[20] Pointcheval D, Stern J. Security arguments for digital signatures and blind signatures[J]. Journal of Cryptology, 2000,13(3): 361-396

[21] Schnorr C P. Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991, 4(3): 161-174

[22] Abdalla M, Fouque P A, Lyubashevsky V, et al. Tightly-secure signatures from lossy identification schemes[J]. Journal of Cryptology, 2016, 29(3): 597-631

[23] Bellare M, Poettering B, Stebila D. From identification to signatures, tightly: A framework and generic transforms[G] //LNCS 10032: Advances in Cryptology (Asiacrypt 2016). Berlin: Springer, 2017: 435-464

[24] Goh E J, Jarecki S. A signature scheme as secure as the Diffie-Hellman problem[G] //LNCS 2656: Advances in Cryptology (EUROCRYPT 2003). Berlin: Springer, 2003: 401-415

[25] Goh E J, Jarecki S, Katz J, et al. Efficient signature schemes with tight reductions to the Diffie-Hellman problems[J]. Journal of Cryptology, 2007, 20(4): 493-514

[26] Krawczyk H, Rabin T. Chameleon signatures[C] //Proc of Network and Distributed System Security Symposium (NDSS 2000). Reston, VA: Internet Society, 2000: 143-154

[27] Chen Xiaofeng, Zhang Fangguo, Tian Haibo, et al. Discrete logarithm based chameleon hashing and signatures without key exposure[J]. Computers & Electrical Engineering, 2011, 37(4): 614-623

[28] Ateniese G, Medeiros B. On the key exposure problem in chameleon hashes[G] //LNCS 3352: Proc of Security in Communication Networks (SCN 2004). Berlin: Springer, 2004: 165-179

[29] Gao Wei, Wang Xueli, Xie Dongqing. Chameleon hashes without key exposure based on factoring[J]. Journal of Computer Science and Technology, 2007, 22(1): 109-113

[30] Quisquater J J, Guillou L C. A paradoxical identity-based signature scheme resulting from zero-knowledge[G] //LNCS 403: Advances in Cryptolgy (CRYPTO’88). Berlin: Springer, 1988: 216-231

GenericTightlySecureSignatureSchemesfromStrongChameleonHashFunctions

Li Fei1,2, Gao Wei1,2, Wang Guilin3, Xie Dongqing2, and Tang Chunming2

1(SchoolofMathematicsandStatistics,LudongUniversity,Yantai,Shandong264025)2(GuangdongProvincialKeyLaboratoryofInformationSecurityTechnology(GuangzhouUniversity),Guangzhou510006)3(ShieldLaboratory,SingaporeResearchCenterofHuawei,Singapore117674)

Provable security has become one basic requirement for constructing and analyzing cryptographic schemes. This paper studies the classical issue in the field of provable security, namely how to construct provably secure digital signature schemes with tight security reduction from certain basic mathematical hard problems in the random oracle model. This paper first proposes a new cryptographic primitive called a strong chameleon Hash function. Based on a strong chameleon Hash function, we present a generic framework and its variant respectively for constructing a stateful and stateless digital signature scheme with tight security. We prove that these generic digital signature schemes are both secure under the assumption that the underlying chameleon Hash function is collision resistant in the random oracle model. By applying these generic construction methods to some concrete chameleon Hash functions under common mathematical assumptions such as RSA, CDH and IF (integer factorization), the corresponding digital signature schemes with tight security can be modularly obtained. The two existing classic paradigms to generically construct tightly secure signature schemes, i.e. Fiat-Shamir signatures and Full-Domain-Hash signatures, can be roughly unified by our generic frameworks. Furthermore, under our generic frameworks, a tightly secure signature scheme following the Fiat-Shamir methodology can be seen as the optimized variant of the corresponding tightly secure signature scheme following the Full-Domain-Hash framework.

digital signature; provable security; tight security; random oracle model; chameleon Hash function;full domain Hash signature

TP309

LiFei, born in 1977. PhD from Guangzhou University. Her main research interests include public key cryptography, algebra, and number theory.

GaoWei, born in 1978. PhD from Hunan University. Associate professor. His main research interests include public key cryptography, cloud security and applied mathematics (mygaowei@163.cm).

WangGuilin, born in 1968. PhD from Institute of Software, Chinese Academy of Sciences. Senior researcher. His main research interests include public key cryptography, cloud security and network security (Wang.Guilin@huawei.com).

XieDongqing, born in 1965. PhD from Hunan University. Professor. Member of CCF. His main research interests include applied cryptography, cloud security and network security (dongqing_xie@hotmail.com).

TangChunming, born in 1972. PhD. Professor. His main research interests include applied cryptography, cloud security and applied mathematics (ctang@gzhu.edu.cn).