Hash函數(shù)族的構(gòu)造與群簽名方案安全性的研究.pdf

1、數(shù)字簽名作為密碼學(xué)基本元語(yǔ),廣泛應(yīng)用于認(rèn)證,授權(quán)和抗抵賴,在密碼學(xué)的理論與應(yīng)用中占有重要地位.因?yàn)橹苯訉?duì)長(zhǎng)消息進(jìn)行簽名效率較低,為提高效率,數(shù)字簽名總是和密碼Hash函數(shù)結(jié)合使用.作為一種組合結(jié)構(gòu),分離Hash函數(shù)族與強(qiáng)分離Hash函數(shù)族的構(gòu)造是組合設(shè)計(jì)理論在密碼學(xué)中具體應(yīng)用的一個(gè)重要研究課題.這是因?yàn)樵诿艽a學(xué)中,分離Hash函數(shù)族與強(qiáng)分離Hash函數(shù)族對(duì)構(gòu)造無(wú)覆蓋族, FP碼,SFP碼和IPP碼起到重要作用156,85,89,94,9

2、6,97]. 另一方面,群簽名是數(shù)字簽名的一個(gè)重要內(nèi)容,是研究將簽名用戶的匿名性和簽名的可追蹤性有機(jī)結(jié)合起來(lái)的學(xué)術(shù)課題.群簽名將密碼學(xué)中兩個(gè)看似矛盾的性質(zhì)匿名性和追蹤性統(tǒng)一在一起,充分體現(xiàn)了密碼學(xué)的神奇作用,在數(shù)字合同,電子選舉,電子投標(biāo)和電子現(xiàn)金[17,18,23,24,45,53,62,84]等一系列實(shí)際生活中具有廣泛并且重要的應(yīng)用價(jià)值.對(duì)群簽名方案的安全性進(jìn)行分析,改進(jìn)群簽名方案以及設(shè)計(jì)出更加安全有效的群簽名方案成為密碼學(xué)

3、研究的重要課題. 本文研究?jī)?nèi)容是應(yīng)用有限域上的代數(shù)曲線構(gòu)造Hash函數(shù)族,分析群簽名方案的安全性以及應(yīng)用Shor量子算法分解RSA模. 設(shè)n與m是整數(shù)且2≤m≤n,集合X和y的階分別為n與m.設(shè)F={f|f:X→y},且|f|=N,則稱F為(N,n,m).Hash函數(shù)族.Hash函數(shù)族F如果滿足任意X<,1>,X<,2>∈,X<,1>∩X2=φ,|X|=ω1且|X<,2>|=ω2,至少存在一個(gè)函數(shù)f∈F滿足f(X<,1>

4、)∩f(X<,2>)=φ,稱Hash函數(shù)族F為(N,n,m,{ω<,1>,<,ω>2})-分離Hash函數(shù)族,記為SHF(N;n,m,{ω<,1>,ω<,2>}).設(shè)N(n,m,{ω<,1>,ω<,2>})表示SHF(N;n,m,{ω<,1>,ω<,2>})存在的最小值N.應(yīng)用概率與組合方法,我們得到:對(duì)給定的正整數(shù)m,ω<,1>和ω<,2>,N(n,m,{ω<,1>,ω<,2>})=θ(log n).然而,這個(gè)存在性定理的證明是非構(gòu)造

5、性的.構(gòu)造出滿足上面漸近性結(jié)果的分離Hash函數(shù)族是一個(gè)很有難度的研究課題.盡管許多學(xué)者在這方面做過(guò)工作[56,85,89,94,97,100],但他們都是應(yīng)用組合設(shè)計(jì)的技巧進(jìn)行遞規(guī)構(gòu)造,無(wú)法進(jìn)一步提高函數(shù)的性能. 在第三章,應(yīng)用有限域上的代數(shù)曲線,我們給出構(gòu)造分離Hash函數(shù)族的方法.特別地,將我們基于Garcia-Stichtenoth曲線的構(gòu)造方法與D.R.Stinson等人197I提出的乘積構(gòu)造方法相結(jié)合,對(duì)任意給定的整

6、數(shù)m,叫1和叫2,我們構(gòu)造出滿足Ⅳ=(=)(10g n)的一個(gè)無(wú)限類分離Hash函數(shù)族.對(duì)任意給定的整數(shù)m和w,我們得到滿足碼長(zhǎng)N=O(logn)的無(wú)限類FP碼和SFP碼.進(jìn)而本質(zhì)地改進(jìn)了應(yīng)用組合方法得到的結(jié)果[85,97],并給出文章[89]中第五個(gè)公開(kāi)問(wèn)題的一個(gè)答案. 在第四章,應(yīng)用有限域上的代數(shù)曲線,我們給出構(gòu)造強(qiáng)分離Hash函數(shù)族的方法.應(yīng)用Garcia-Stichtenoth曲線的構(gòu)造方法與我們證明的強(qiáng)分離Hash函數(shù)

7、族的乘積構(gòu)造方法相結(jié)合,對(duì)任意給定的整數(shù)m,w<,1>和w<,2>,得到滿足N=O(logn)的一個(gè)無(wú)限類強(qiáng)分離Hash函數(shù)族.對(duì)任意給定的整數(shù)m和w,我們得到滿足碼長(zhǎng)N=O(logn)的無(wú)限類IPP碼.對(duì)任意給定的整數(shù)m,w和t,我們得到滿足碼長(zhǎng)N=O(logv)的無(wú)限類廣義IPP碼.本質(zhì)地改進(jìn)了關(guān)于強(qiáng)分離Hash函數(shù)族的漸近性結(jié)論[85]和IPP碼的漸近性結(jié)果[85,100]. 因?yàn)橛邢抻蛏系拇鷶?shù)曲線存在多項(xiàng)式時(shí)間的構(gòu)造方法

8、,本文對(duì)分離Hash函數(shù)族和強(qiáng)分離Hash函數(shù)族以及FP碼,SFP碼,IPP碼和廣義IPP碼的構(gòu)造達(dá)到了界N-O(logn),提供了最好的漸近行為,給出多項(xiàng)式時(shí)間的構(gòu)造方法. 第五章分析了Kim-Park-Won群簽名方案,Lee-Chang群簽名方案,改進(jìn)的Tseng-Jan群簽名方案,Wang-Fu群簽名方案,Zhang-Wu-Wang群簽名方案和.Xia-Yuo群簽名方案的安全性,證明這些方案是不安全的.我們從分析這些方案

9、的安全性過(guò)程中總結(jié)出兩個(gè)有用的技巧:隨機(jī)擾動(dòng)法,指數(shù)分析法.隨機(jī)擾動(dòng)法是指在保證簽名驗(yàn)證方程成立的前提下,對(duì)某些簽名數(shù)據(jù)作適當(dāng)?shù)碾S機(jī)變換使得追蹤方程不成立.指數(shù)分析法是指在固定底數(shù)的情況下,為了消除指數(shù)位置上的挑戰(zhàn)值,對(duì)相應(yīng)的指數(shù)進(jìn)行分析并逐步推出各個(gè)指數(shù)應(yīng)具有的表達(dá)式. 第六章首先介紹群簽名在電子商務(wù)中的應(yīng)用,然后分析文獻(xiàn)[24l中提出的一個(gè)基于群簽名方案的電子貨幣系統(tǒng)Canard-Traore公平電子現(xiàn)金方案的安全性.文獻(xiàn)[

10、24]的作者聲稱Canard-Traore公平電子現(xiàn)金方案的安全性依賴于強(qiáng)RSA假設(shè)和Diffie-Hellman假設(shè).我們證明該方案的安全性僅依賴于一個(gè)公開(kāi)參數(shù)選取的區(qū)間長(zhǎng)度. 應(yīng)用量子計(jì)算機(jī),Shor在文獻(xiàn)[88]中證明了大整數(shù)因子分解問(wèn)題存在多項(xiàng)式時(shí)間算法.對(duì)給定整數(shù)n,在模n乘法群中,Shor確定了尋找元素的階的算法.應(yīng)用隨機(jī)算法[69],大整數(shù)因子分解問(wèn)題可以約化為尋求元素階的問(wèn)題,所以該算法是可行的.但有一點(diǎn)值得強(qiáng)調(diào)