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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

圖２．２?—個(gè)二維格??

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

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

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

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

導(dǎo)數(shù)，可以確定參??數(shù)Ａ：、６的值。??關(guān)于存儲(chǔ)空間，因?yàn)榍耙徊糠掷茫拢耍谒惴ǎ仕璧拇鎯?chǔ)空間為關(guān)于維??數(shù)ｎ的某個(gè)多項(xiàng)式；因?yàn)楹笠徊糠掷眠f進(jìn)高斯篩法，故所需的存儲(chǔ)空間為關(guān)于??維數(shù)ｎ的指數(shù)函數(shù)，但遠(yuǎn)低于高斯篩法所需的存儲(chǔ)空間。??對(duì)?Ｄａｒｍｓｔａｄｔ?Ｌａｔｔｉｃｅ?Ｃ....

本文編號(hào)：4005305