格基規(guī)約理論及其在密碼設計中的應用.pdf

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

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

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

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

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

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