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

1、數(shù)字簽名作為密碼學基本元語,廣泛應用于認證,授權和抗抵賴,在密碼學的理論與應用中占有重要地位.因為直接對長消息進行簽名效率較低,為提高效率,數(shù)字簽名總是和密碼Hash函數(shù)結合使用.作為一種組合結構,分離Hash函數(shù)族與強分離Hash函數(shù)族的構造是組合設計理論在密碼學中具體應用的一個重要研究課題.這是因為在密碼學中,分離Hash函數(shù)族與強分離Hash函數(shù)族對構造無覆蓋族, FP碼,SFP碼和IPP碼起到重要作用156,85,89,94,9

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

3、研究的重要課題. 本文研究內容是應用有限域上的代數(shù)曲線構造Hash函數(shù)族,分析群簽名方案的安全性以及應用Shor量子算法分解RSA模. 設n與m是整數(shù)且2≤m≤n,集合X和y的階分別為n與m.設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,至少存在一個函數(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>}).設N(n,m,{ω<,1>,ω<,2>})表示SHF(N;n,m,{ω<,1>,ω<,2>})存在的最小值N.應用概率與組合方法,我們得到:對給定的正整數(shù)m,ω<,1>和ω<,2>,N(n,m,{ω<,1>,ω<,2>})=θ(log n).然而,這個存在性定理的證明是非構造

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

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

7、族的乘積構造方法相結合,對任意給定的整數(shù)m,w<,1>和w<,2>,得到滿足N=O(logn)的一個無限類強分離Hash函數(shù)族.對任意給定的整數(shù)m和w,我們得到滿足碼長N=O(logn)的無限類IPP碼.對任意給定的整數(shù)m,w和t,我們得到滿足碼長N=O(logv)的無限類廣義IPP碼.本質地改進了關于強分離Hash函數(shù)族的漸近性結論[85]和IPP碼的漸近性結果[85,100]. 因為有限域上的代數(shù)曲線存在多項式時間的構造方法

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

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

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