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

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

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

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

【部分圖文】：

圖５．５?ＬＳＨ對比

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

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


本文編號：3256056