基于格的密碼方案的研究與設(shè)計.pdf

1、公鑰密碼體制是保障電子商務(wù)、電子政務(wù)中信息安全的主要手段?；诖笳麛?shù)分解和離散對數(shù)困難問題構(gòu)造公鑰密碼體制是目前常用的一些密碼體制，如RSA加密體制。但這些密碼體制中都包含復(fù)雜運算，因此效率較低，這也是一直制約公鑰密碼體制發(fā)展的重要因素之一。另外大整數(shù)分解和離散對數(shù)問題已經(jīng)被證明不能抵御量子攻擊和亞指數(shù)攻擊。因此必須尋求更加高效、安全的公鑰密碼體制。1996年Ajtai開創(chuàng)性地提出了基于最差情況下格問題的困難假設(shè)構(gòu)造密碼方案的可能性，為

2、構(gòu)造新型的公鑰密碼體制提供了一條嶄新的思路。
　　 一個n維格是R''上的離散加法子群。基于格構(gòu)造的密碼方案是建立在某個格問題的困難假設(shè)基礎(chǔ)上的，其中最基本的困難問題是最短向量問題SVP，從目前的研究和實驗結(jié)果可推測不存在求解近似因子為多項式的格問題的多項式時間算法和多項式時間量子算法。基于格問題構(gòu)造的密碼方案除了能夠抵御量子攻擊之外，Ajtai等還證明了某類格中一些問題的平均難度等價于格上一類NP問題的難度。因此在這些格問題基

3、礎(chǔ)上建立的公鑰密碼體制，其任意一個實例的安全性與其最難實例的安全性相同。這種優(yōu)良特性是目前大部分公鑰密碼體制所不具備的。而且由于格是一種線性結(jié)構(gòu)，其上的運算大多是線性運算，因此可以期望利用格上難題構(gòu)建的新型公鑰密碼體制具有更快的運算速度。本文通過對格及相關(guān)知識的研究后，詳細分析了已有基于格的公鑰密碼方案，借鑒其中的一些方法和構(gòu)造思路，構(gòu)造了新的基于格的密碼方案。
　　 為構(gòu)造新的基于格的密碼方案，本文首先研究了格的基本知識和性質(zhì)

4、。對目前在格問題研究中廣泛應(yīng)用的離散高斯分布技術(shù)進行深入研究，并將Gentry提出的在格上的離散高斯分布中取點的SampleD算法應(yīng)用于方案設(shè)計中。由Ajtai定義的困難隨機格即q模格，是目前基于格的公鑰密碼體制構(gòu)造中占主導(dǎo)地位的兩種類型的整數(shù)格，對此類格及其重要性質(zhì)的研究奠定了本文方案的構(gòu)造基礎(chǔ)。文中所有方案都是建立在q模格之上的。直接基于格上困難問題構(gòu)造公鑰密碼體制是比較困難的，目前基于格構(gòu)造的公鑰密碼體制是建立在一些一般情況困難問

5、題之上，這些問題已被證明一般情況下的困難性和最差情況下特定格問題的困難性等價被證明。常見的問題是LWE問題、SIS和ISIS問題。本文研究分析了基于這些問題構(gòu)造的密碼方案，其中基于LWE問題構(gòu)造的方案包括最初由Regev提出的基于LWE的公鑰加密方案，Gnentry等提出的基于身份的加密方案，Peikert等使用Lossy trapdoor functions方法構(gòu)造的基于LWE的CCA2加密方案；基于SIS和ISIS問題構(gòu)造的方案主要

6、包括Gentry等定義的原像選取陷門函數(shù)以及他們基于原像選取陷門函數(shù)構(gòu)造的數(shù)字簽名方案。此組原像選取陷門函數(shù)也是本文構(gòu)造基于SIS和ISIS的公鑰加密方案的基礎(chǔ)。本文研究和構(gòu)造的主要方案如下：
　　 (1)基于LWE的加密方案的研究和構(gòu)造：Regev首次使用量子算法證明了LWE問題和最差情況GapSVP問題困難性是等同的，同時構(gòu)造了單比特LWE方案，通過對此方案的研究，了解了基于LWE構(gòu)造公鑰加密方案的思想。本文根據(jù)Peiker

7、t等提出的多比特LWE方案和Gentry等提出的對偶LWE加密方案構(gòu)造了多比特對偶LWE加密方案。Gentry在SIS和ISIS的困難假設(shè)基礎(chǔ)上構(gòu)造了基于格的原像選取陷門函數(shù)，并將此原像陷門函數(shù)應(yīng)用于基于身份加密方案中，負責(zé)完成由身份生成對應(yīng)私鑰的操作，在Gentry提出的基于LWE單比特IBE方案基礎(chǔ)上，本文構(gòu)造了多比特IBE方案。最后使用Boneh等提出的將CCA2安全的公鑰加密方案建立在CPA安全的基于身份的加密方案基礎(chǔ)上的構(gòu)造方

8、法，以多比特IBE加密方案為基礎(chǔ)，構(gòu)造了基于LWE的CCA2公鑰加密方案。上述方案是基于LWE判定問題構(gòu)造的，Peikert使用非量子算法證明了LWE搜索問題和近似SVP問題的某種變體的困難性是等價的，并以LWE搜索問題為基礎(chǔ)，定義了一組陷門函數(shù)，進而構(gòu)造了CCA2安全的加密方案?；贚WE搜索問題構(gòu)造新的密碼方案，也是基于格的密碼學(xué)研究的一個新方向。
　　 (2)基于SIS和ISIS的公鑰加密方案的研究和構(gòu)造：基于SIS和IS

9、IS問題構(gòu)造的公鑰密碼方案，主要是以Gentry定義的原像選取陷門函數(shù)為基礎(chǔ)而構(gòu)造的公鑰密碼方案，目前所知的方案是Gnetry基于原像選取陷門函數(shù)構(gòu)造的數(shù)字簽名方案。但還沒有基于原像選取陷門函數(shù)構(gòu)造的公鑰加密方案，本文以此原像選取陷門函數(shù)為基礎(chǔ)，使用Peikert等提出的證據(jù)恢復(fù)解密(Witness-RecoveringDecryption)方法，構(gòu)造了CPA安全的加密方案。通過對原像選取陷門函數(shù)能夠滿足雙射函數(shù)的性質(zhì)的證明，進一步利用

10、Rosen提出的基于一組CorrelatedProducts安全的雙射陷門函數(shù)構(gòu)造CCA1和CCA2公鑰加密方案的方法，在CPA方案的基礎(chǔ)上，利用原像選取陷門函數(shù)構(gòu)造了CCA1和CCA2安全公鑰加密方案。
　　 (3)基于格的代理簽名方案構(gòu)造：本文研究了Cash等提出的基于LWE的分層IBE方案，其中提出了一種比較實用的技術(shù)一格基派生技術(shù)，此技術(shù)是在某個格的一組短基已知的情況下，使用這組短基來生成另外一個維數(shù)更高的格的一組短基的

11、技術(shù)。格基派生技術(shù)實際上是Gentry時定義的原像選取陷門函數(shù)技術(shù)的推廣。由于一組短基實際上就是陷門函數(shù)的陷門，因此，格基派生技術(shù)可以在基于格的密碼方案構(gòu)造時得到很好的應(yīng)用。本文將格基派生技術(shù)應(yīng)用于代理簽名中代理密鑰的生成，結(jié)合Gentry等提出的基于原像選取函數(shù)構(gòu)造的數(shù)字簽名方案，構(gòu)造了基于格的代理簽名方案和多級代理簽名方案。
　　 本文構(gòu)造的基于格的密碼方案豐富了目前基于格的公鑰密碼體制的應(yīng)用和研究，后期我們還將進一步基于格