發(fā)布時(shí)間：2020-06-30 17:04

【摘要】：近年來,學(xué)術(shù)界對量子計(jì)算機(jī)的研究逐漸深入,大素?cái)?shù)分解問題(Prime Factorization)和離散對數(shù)問題(Discrete Logarithm)因此開始變得不再那么困難。然而,當(dāng)今廣泛使用的公鑰密碼體制的安全大都依賴于這兩個(gè)問題的困難性,因此,設(shè)計(jì)抗量子計(jì)算機(jī)攻擊的“后量子時(shí)代”密碼體制吸引了密碼學(xué)界越來越多的研究興趣。在已經(jīng)提出的幾種“后量子時(shí)代”密碼體制中,格密碼體制逐漸成為近年來頂級密碼會(huì)議和期刊上的研究熱點(diǎn)。最短向量問題(Shortest Vector Problem,簡稱SVP)是格理論(或者說,數(shù)的幾何)中最重要的問題之一,幾種基于格的公鑰密碼體制(Lattice-Based Cryptography)的安全性都依賴于最短向量問題(SVP)問題的困難性。本文圍繞最短向量問題(SVP)展開深入研究,提出了格中短向量在BKZ約化基下的y-稀疏表示,然后利用這種短向量表示的稀疏性提出了解決最短向量問題(SVP)的若干算法,包括SVP遺傳算法,SVP模擬退火算法,SVP分段枚舉算法,以及SVP隨機(jī)采樣算法。本文的創(chuàng)新點(diǎn)主要包括:?首先,本文提出了在BKZ約化基下的格中短向量的整數(shù)y-稀疏表示,同時(shí)通過理論證明得到格中短向量的這種表示中各個(gè)整數(shù)分量的上界及其稀疏性;這種格中短向量的稀疏性具有獨(dú)立的研究價(jià)值。?其次,本文首次將“遺傳算法”和“模擬退火算法”等計(jì)算智能(Computational Intelligence)的思想應(yīng)用于最短向量問題(SVP),通過馬爾科夫分析和實(shí)驗(yàn)驗(yàn)證,這兩種算法在解決最短向量問題(SVP)方面收到良好的效果。?最后,本文基于格中短向量的y-稀疏表示提出了分段的概念,利用分段情況下的短向量稀疏表示中非零分量個(gè)數(shù)的升序排列,提出了SVP分段枚舉算法。實(shí)驗(yàn)顯示,與當(dāng)前著名SVP枚舉算法相比,這種SVP分段枚舉算法是目前較為快速而有效的SVP枚舉算法。
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O413;TN918

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 高志榮;熊承義;笪邦友;;改進(jìn)的基于殘差加權(quán)的稀疏表示人臉識別[J];中南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

2 陳才扣;喻以明;史俊;;一種快速的基于稀疏表示分類器[J];南京大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

3 耿耀君;張軍英;;一種基于投影稀疏表示的基因選擇方法[J];哈爾濱工程大學(xué)學(xué)報(bào);2011年08期

4 熊承義;汪淑賢;高志榮;;基于字典優(yōu)化的稀疏表示人臉識別[J];中南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

5 戴平陽;洪景新;李翠華;詹小靜;;一種基于稀疏表示的判別式目標(biāo)跟蹤算法[J];廈門大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年04期

6 趙佳佳;唐崢遠(yuǎn);楊杰;劉爾琦;周越;;基于圖像稀疏表示的紅外小目標(biāo)檢測算法[J];紅外與毫米波學(xué)報(bào);2011年02期

7 柯激情;祝磊;厲力華;韓斌;鄭智國;孟旭莉;;基于稀疏表示算法的蛋白質(zhì)質(zhì)譜數(shù)據(jù)特征選擇[J];生物物理學(xué)報(bào);2012年08期

8 王立國;劉丹鳳;趙亮;;基于高光譜圖像稀疏表示的彩色可視化模型(英文)[J];Applied Geophysics;2013年02期

9 宋琳;程詠梅;趙永強(qiáng);;基于稀疏表示模型和自回歸模型的高光譜分類[J];光學(xué)學(xué)報(bào);2012年03期

10 羅燕龍;劉偉盛;戴平陽;李翠華;;基于局部稀疏表示模型的海上紅外目標(biāo)跟蹤方法[J];廈門大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年03期

相關(guān)會(huì)議論文 前3條

1 何愛香;劉玉春;魏廣芬;;基于稀疏表示的煤矸界面識別研究[A];虛擬運(yùn)營與云計(jì)算——第十八屆全國青年通信學(xué)術(shù)年會(huì)論文集（上冊）[C];2013年

2 樊亞翔;孫浩;周石琳;鄒煥新;;基于元樣本稀疏表示的多視角目標(biāo)識別[A];2013年中國智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第五分冊）[C];2013年

3 葛鳳翔;任歲玲;郭鑫;郭良浩;孫波;;微弱信號處理及其研究進(jìn)展[A];中國聲學(xué)學(xué)會(huì)水聲學(xué)分會(huì)2013年全國水聲學(xué)學(xué)術(shù)會(huì)議論文集[C];2013年

相關(guān)博士學(xué)位論文 前10條

1 李進(jìn)明;基于稀疏表示的圖像超分辨率重建方法研究[D];重慶大學(xué);2015年

2 王亞寧;基于信號稀疏表示的電機(jī)故障診斷研究[D];河北工業(yè)大學(xué);2014年

3 姚明海;視頻異常事件檢測與認(rèn)證方法研究[D];東北師范大學(xué);2015年

4 黃國華;蛋白質(zhì)翻譯后修飾位點(diǎn)與藥物適應(yīng)癥預(yù)測方法研究[D];上海大學(xué);2015年

5 王瑾;基于稀疏表示的數(shù)據(jù)收集、復(fù)原與壓縮研究[D];北京工業(yè)大學(xué);2015年

6 李濤;遙感影像稀疏表示中的字典學(xué)習(xí)算法及其應(yīng)用[D];華中科技大學(xué);2015年

7 丁丹;格中短向量的y-稀疏表示和最短向量問題的算法研究[D];清華大學(xué);2015年

8 李小薪;稀疏表示的分段匹配尋蹤方法[D];華南理工大學(xué);2009年

9 何艷敏;稀疏表示在圖像壓縮和去噪中的應(yīng)用研究[D];電子科技大學(xué);2011年

10 宋相法;基于稀疏表示和集成學(xué)習(xí)的若干分類問題研究[D];西安電子科技大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 吳麗璇;基于稀疏表示的微聚焦X射線圖像去噪方法[D];華南理工大學(xué);2015年

2 趙孝磊;基于圖像分塊稀疏表示的人臉識別算法研究[D];南京信息工程大學(xué);2015年

3 黃志明;基于辨別式稀疏字典學(xué)習(xí)的視覺追蹤算法研究[D];華南理工大學(xué);2015年

4 張鈴華;非約束環(huán)境下的稀疏表示人臉識別算法研究[D];南京信息工程大學(xué);2015年

5 賀妍斐;基于稀疏表示與自適應(yīng)倒易晶胞的遙感圖像復(fù)原方法研究[D];南京信息工程大學(xué);2015年

6 楊爍;電能質(zhì)量擾動(dòng)信號的稀疏表示/壓縮采樣研究[D];西南交通大學(xué);2015年

7 應(yīng)艷麗;基于低秩稀疏表示的目標(biāo)跟蹤算法研究[D];西南交通大學(xué);2015年

8 梁曉捷;基于網(wǎng)絡(luò)攝像頭與稀疏表示分類法的實(shí)時(shí)人臉識別系統(tǒng)應(yīng)用研究[D];五邑大學(xué);2015年

9 張宏樂;語音信號稀疏表示方法研究[D];太原理工大學(xué);2016年

10 崔保良;基于稀疏表示的協(xié)同入侵檢測[D];廣東工業(yè)大學(xué);2011年

本文編號：2735566