隨著量子計(jì)算的飛速發(fā)展,傳統(tǒng)的公鑰密碼體制難以抵抗未來量子計(jì)算機(jī)的攻擊。為了保障未來的信息安全,研究能夠抵抗量子攻擊的密碼體制刻不容緩。格密碼體制是眾多能夠抵抗量子攻擊密碼體制方案中的佼佼者。作為密碼體制的核心,與格相關(guān)的困難問題是眾多學(xué)者重點(diǎn)研究的對(duì)象。對(duì)于格困難問題求解算法的研究不僅可以為格密碼的安全性提供保障,同時(shí)獲得的求解算法也可以針對(duì)其它密碼體制進(jìn)行攻擊。本文針對(duì)格中的最短向量問題與最近向量問題進(jìn)行研究,對(duì)求解該問題的一類高效算法——啟發(fā)式篩法進(jìn)行優(yōu)化。本文的第一個(gè)研究?jī)?nèi)容是使用機(jī)器學(xué)習(xí)衍生的K-Means位置敏感哈希對(duì)NV-Sieve與GaussSieve兩種啟發(fā)式篩法進(jìn)行優(yōu)化,得到了三項(xiàng)研究成果。第一,分析并通過實(shí)驗(yàn)驗(yàn)證了 K-Means LSH具有比CP LSH更好的性能;第二,使用K-Means LSH對(duì)兩種篩法進(jìn)行了優(yōu)化,并且通過實(shí)驗(yàn)說明該優(yōu)化方式比Thijs Laarhoven等學(xué)者提出的基于CP LSH優(yōu)化的CP Sieve具有更高的效率與靈活性;第三,對(duì)優(yōu)化后的NV-Sieve進(jìn)行了推廣,使其能夠求解最近向量問題。本文的第二個(gè)研究?jī)?nèi)容是針對(duì)GaussSieve... 

【文章來源】：中國(guó)科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

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

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

【部分圖文】：

圖５．５?ＬＳＨ對(duì)比

Ｈ（Ｎ）??１８?－?－?ｔ?ｐ２?ｆｏｒ?ｋＭｅａｎｓ－ＬＳＨ（Ｎ）??？?ｐ１?ｆｏｒ?ｋＭｅａｎｓ－ＬＳＨ（２Ｎ）??１６?－?＜?■?ｐ２?ｆｏｒ?ｋＭｅａｎｓ－ＬＳＨ（２Ｎ）??１４－??１２－?？．???？ｓ?？＇??ｐｉ（％）１０■?、？一?？??８－??６－??２－?Ｔ?ｗ??＾?—卜；?ｍｉ??〇?Ｉ?１?Ｉ?１?Ｉ?１?Ｉ?１?Ｉ?１??３０?４０?５０?６０?７０??ｄｉｍ??圖５．５?ＬＳＨ對(duì)比圖１??１：對(duì)于高維空間中隨機(jī)選取的向量對(duì)，絕大部分分布在以為中心的鄰域內(nèi)。??以３０維為例，隨機(jī)生成１０萬對(duì)向量，有超過９萬對(duì)的向量落在該鄰域內(nèi)，??并且這個(gè)趨勢(shì)隨著維數(shù)的增加會(huì)更明顯。??２：對(duì)于高維空間與；ｒ／３的臨界角度，利用貪心算法能夠放置的點(diǎn)與維度呈指數(shù)??關(guān)系，遠(yuǎn)大于我們需要的中心點(diǎn)數(shù)目。??回到＆的定義來看，對(duì)于向量對(duì)，如果我們考慮單個(gè)哈希函??數(shù)＆，很容易可以看出，在中心點(diǎn)集分布密集的區(qū)域內(nèi)容易出現(xiàn)結(jié)??合上面的事實(shí)。對(duì)于從哈希函數(shù)族中隨機(jī)選取的哈希函數(shù)其中心點(diǎn)集在??（ｔ／，ｙ）附近大概率是稀疏的。因此才有Ｋ－Ｍｅａｎｓ?ＬＳＨ的；＾遠(yuǎn)大于ＣＰ?ＬＳＨ的；ｖ??這也可以解釋隨著火的增大，中心點(diǎn)集密集區(qū)域變大，所以／＾值會(huì)變校類似??的也可以解釋ｐ２變化的趨勢(shì)。??雖然越�。猎酱�，但是實(shí)際使用中并不是尺越小越好。圖５．６展示了；Ｖｐ２??的趨勢(shì)�？梢钥闯�，隨著欠的增大與維數(shù)》的增大，ＴＶ／＾會(huì)有明顯增加的趨勢(shì)。??因此在實(shí)際使用中還是要綜合考慮參數(shù)的選齲??５．３基于Ｋ－Ｍｅａｎｓ?ＬＳＨ優(yōu)化的篩法性能測(cè)試??本節(jié)中

２Ｋ＝２Ｎ?０．３６９８１?／ｙ??ｋ＝２?Ｋ＝３Ｎ?０．３５５４５??＞＾３２－?ｋ＝２Ｋ＝４Ｎ?０．３３９３３?，，??ｃｍ?ｋ＝３?Ｋ＝Ｎ?０．３２６０２?＇．Ｊｆｆ?，－Ｍ??￥３０－??Ｉ?２８：??〇２６＿?，４ｙ＾??２４?－??－ｗ??２０－??ｂ?ｉ?Ｌ?ｉ?■?ｉ?Ｊ?ｉ?？?ｉ?？?ｉ?■?ｉ?１?ｉ?■?ｉ??３０?３５?４０?４５?５０?５５?６０?６５?７０?７５??ｄｉｍ??圖?５．７?Ｏｐｅｒａｔｉｏｎｓ?對(duì)比??從圖５．８中我們可以看出，Ｋ－Ｍｅａｎｓ?Ｓｉｅｖｅ需要消耗略多的空間。這是因?yàn)殡m??然尺＝２？與ＣＰ?ＬＳＨ實(shí)際上具有相同大小的中心點(diǎn)集，然而ＣＰ?ＬＳＨ只需要存??儲(chǔ)的旋轉(zhuǎn)矩陣，因此在ＬＳＨ的存儲(chǔ)上只需要Ｋ－Ｍｅａｎｓ?ＬＳＨ—半的消耗。但??是從結(jié)果對(duì)比來看，存儲(chǔ)空間的損耗可以接受。??該算法還有一定的優(yōu)化空間，其優(yōu)化空間有下面兩點(diǎn)：??１：從實(shí)驗(yàn)結(jié)果來看，對(duì)于略高維度的空間，對(duì)于相同的ｋ，增大Ｋ對(duì)于漸進(jìn)復(fù)??雜度的影響是明顯的。這說明中心點(diǎn)集與維度》之間的關(guān)系在最優(yōu)情況下??很可能不是線性的，因此，中心點(diǎn)集的大小或許可以進(jìn)一步優(yōu)化。??２：雖然計(jì)算Ｋ－Ｍｅａｎｓ?ＬＳＨ與計(jì)算ＣＰ?ＬＳＨ的時(shí)間復(fù)雜度相同，但是由于ＣＰ?ＬＳＨ??只需要存儲(chǔ)ｎ?的旋轉(zhuǎn)矩陣便能實(shí)現(xiàn)尺＝２／ｊ的等效效果。因此中心點(diǎn)集??或許可以選取為具有特殊性質(zhì)又不影響其分布的點(diǎn)集，以實(shí)現(xiàn)節(jié)約存儲(chǔ)的??效果的優(yōu)化。??綜上所述，Ｋ－Ｍｅａｎｓ?Ｓｉｅｖｅ作為ＣＰ?Ｓｉｅｖｅ的推廣是成功的，同時(shí)受限于球面??布點(diǎn)問題的困難性，該算法的潛力并未被完全發(fā)掘�？紤]到Ｋ－Ｍｅａｎｓ?


本文編號(hào)：3256056