格基規(guī)約理論及其在密碼設(shè)計(jì)中的應(yīng)用.pdf

1、格基規(guī)約是格理論研究的一個(gè)重要內(nèi)容，也是密碼設(shè)計(jì)和分析中的一個(gè)重要工具。在理論研究中，許多格上問題都可以通過格基規(guī)約來求解(或者近似求解)。在密碼學(xué)應(yīng)用中，對(duì)一些密碼方案的分析最終都可以等價(jià)成一個(gè)格基規(guī)約問題。因此研究新型格基規(guī)約算法不僅具有理論價(jià)值，同時(shí)也具有重要的實(shí)用價(jià)值。 把密碼方案的安全基礎(chǔ)建立在已知的數(shù)學(xué)難題上是密碼設(shè)計(jì)常用的一種方法。一個(gè)好的密碼方案除了要求是安全的，還應(yīng)該是高效的。格是一種典型的線性代數(shù)結(jié)構(gòu)，并且格

2、上一些問題的困難性已經(jīng)得到證明。如果利用格上難題設(shè)計(jì)新型密碼方案，那么不僅可以期望方案的安全性能夠得到證明，而且還可以期望格的線性結(jié)構(gòu)能夠使方案具有較高的運(yùn)算速度。因此，在格上構(gòu)造密碼方案得到國內(nèi)外許多學(xué)者的關(guān)注。 本文以現(xiàn)代通信國家重點(diǎn)實(shí)驗(yàn)室開放基金課題“NTRU公開密鑰密碼體制的研究”(No.51436010203QT2201)為基礎(chǔ)，對(duì)格基規(guī)約理論和基于格上難題的新型密碼方案進(jìn)行了研究。本文前半部分研究的重點(diǎn)在格基規(guī)約理論

3、研究。在這部分內(nèi)容中，本文設(shè)計(jì)一種新型的格基規(guī)約算法——l次格基規(guī)約算法。這個(gè)算法得到規(guī)約基的質(zhì)量不僅好于標(biāo)準(zhǔn)LLL算法，而且這個(gè)算法具有計(jì)算花費(fèi)時(shí)間和規(guī)約結(jié)果質(zhì)量之間可以相互轉(zhuǎn)化的特點(diǎn)：通過犧牲更多的運(yùn)算時(shí)間來獲得質(zhì)量更優(yōu)的規(guī)約基。標(biāo)準(zhǔn)LLL算法最多僅能夠解決近似因子為α(n-1)/2的近似最短向量問題(app-SVP)，而相同情況下，l次格基規(guī)約算法最多能夠解決近似因子為α1/2的近似最短向量問題。盡管最短向量問題是NP問題，但是這

4、并不意味著任何一個(gè)格的最短向量求解都是困難的。本文提出了最短向量已知格的概念，研究了判斷一類格中最短向量的兩個(gè)充分條件。討論了如何利用這兩個(gè)條件快速生成最短向量已知格。本文后半部分研究的重點(diǎn)在利用格上難題設(shè)計(jì)構(gòu)造密碼方案。在這部分內(nèi)容中，首先分析了幾個(gè)基于格上難題的公鑰密碼方案，針對(duì)這些方案都存在解密錯(cuò)誤現(xiàn)象，介紹了完備公鑰密碼方案(PPKC)和非完備公鑰密碼方案(IPKC)的概念，分析了PPKC和IPKC在安全特性上的一些差異，提出了

5、針對(duì)IPKC的解密錯(cuò)誤探測(cè)攻擊模型。依據(jù)現(xiàn)代通信國家重點(diǎn)實(shí)驗(yàn)室開放基金課題研究的成果，本文針對(duì)NTRU解密錯(cuò)誤現(xiàn)象設(shè)計(jì)了高效的糾錯(cuò)補(bǔ)償算法。在最后部分，利用前人研究的結(jié)果構(gòu)造了一種基于格上難題的具有碰撞免疫特性的Hash函數(shù)。本文的主要工作有如下幾個(gè)方面： 1.對(duì)密碼學(xué)涉及的格理論知識(shí)進(jìn)行了總結(jié)。分析了格基規(guī)約問題的由來和目前格基規(guī)約算法研究的進(jìn)展。首次提出l次格基規(guī)約的概念，并且設(shè)計(jì)了l次格基規(guī)約算法。通過大量數(shù)值實(shí)驗(yàn)比較了l

6、次格基規(guī)約和標(biāo)準(zhǔn)LLL規(guī)約算法的性能。 2.提出了最短向量已知格的概念。提出并且證明了判斷一類格中最短向量的兩個(gè)充分條件。討論了使用這兩個(gè)充分條件來生成隨機(jī)最短向量已知格的技術(shù)。 3.分析了幾個(gè)基于格上難題的新型公鑰密碼方案，討論了它們各自的特點(diǎn)。介紹了完備公鑰密碼方案和非完備公鑰密碼方案的概念。比較了這兩種方案對(duì)不同攻擊方法抵抗能力上的差別。提出針對(duì)非完備公鑰密碼方案的解密錯(cuò)誤探測(cè)攻擊模型。 4.深入研究了NT