發(fā)布時間：2024-07-11 05:16

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

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

【學位級別】：碩士

【部分圖文】：

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

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

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

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

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

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

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

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

本文編號：4005305