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

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

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

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

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

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

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

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

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

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

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