最新的基于格的密碼體制幾乎都直接基于如下兩個平均復雜性的問題:最小整數(shù)解(SmallestInteger Solution,SIS)問題和誤差學習(Learning With Errors,LWE)問題。人們提出了很多求解SIS問題和LWE問題的理論算法,但對于實際應用中的復雜性估計還不足,密碼設計中參數(shù)的選取還比較模糊。此外,平均復雜性的理論已被研究很多年。distNP類是平均復雜性形式的NP類,且有完全問題。Liven證明了所有自然的NP完全問題都有平均復雜性的形式,但是他給出的概率分布是不自然的。本文要研究的三個問題是SIS問題、LWE問題的求解算法和一個平均復雜性的可滿足性(Satisfiability,SAT)問題的構造,并作出了如下三方面的工作:1.給出一個求解SIS問題和一個求解LWE問題的算法,并給出Darmstadt Lattice Challenge 和 Darmstadt LWE Challenge 的實驗結果。實驗結果證明了所述方案的可行性和高效性。2.給出將SIS問題和LWE問題轉換為SAT問題的方法。3.構造一個具有平均復雜性的SAT問題,給出構造的通式以及...

【文章頁數(shù)】：80 頁

【學位級別】：碩士

【部分圖文】：

圖２．１?—個二維格上的離散高斯分布??

近似。所以Ｌ＞ｓ，ｃ也可以被有效得近似。對于不特殊說明的情??況，我們默認ｃ為原點，ｓ等于１。??連續(xù)高斯分布可以離散地推廣到集合上，令??Ｐｓ，ｃ｛＾）?＝?＾ｘ￡ＡＰｓ，ｃ｛．＊＾）??對于格Ａ，定義離散高斯分布ＤＡ，ｓ，ｅ為??Ｖｘ?Ｇ?Ａ，?Ｄａ＾ｃ（ｘ）?＝??如前面所....

圖２．２?—個二維格??

第二章預備知識??定義２．３丄（格）令５?＝?＆１，＆２，．．．，心（：１＾為７１個線性無關的向量組成的??集合，以Ｊ３為基的格￡（Ｂ）?＝?｛＾＾＝１而？?：ａ?Ｇ?Ｚ｝，通常記為Ａ?＝?￡（ｊＢ）。ｎ和??ｍ分別稱為格的秩和維數(shù)。??事實上，格與歐幾里得線性空間定義的區(qū)別在于....

圖２．３?—個三維格??對于兩組線性無關的向量Ｓ和如果即前者中的格點??

第二章預備知識??定義２．３丄（格）令５?＝?＆１，＆２，．．．，心（：１＾為７１個線性無關的向量組成的??集合，以Ｊ３為基的格￡（Ｂ）?＝?｛＾＾＝１而？?：ａ?Ｇ?Ｚ｝，通常記為Ａ?＝?￡（ｊＢ）。ｎ和??ｍ分別稱為格的秩和維數(shù)。??事實上，格與歐幾里得線性空間定義的區(qū)別在于....

圖３．１當ｆｃ?＝?６０，?６?＝?２４和ｆｃ?＝?８０，?６?＝?３０時，得到的比值￥與維數(shù)ｎ的關系??

導數(shù)，可以確定參??數(shù)Ａ：、６的值。??關于存儲空間，因為前一部分利用ＢＫＺ算法，故所需的存儲空間為關于維??數(shù)ｎ的某個多項式；因為后一部分利用遞進高斯篩法，故所需的存儲空間為關于??維數(shù)ｎ的指數(shù)函數(shù)，但遠低于高斯篩法所需的存儲空間。??對?Ｄａｒｍｓｔａｄｔ?Ｌａｔｔｉｃｅ?Ｃ....

本文編號：4005305