本文關(guān)鍵詞：幾類新型密碼體制困難問題求解算法的分析與應(yīng)用，由筆耕文化傳播整理發(fā)布。

【摘要】：密碼學(xué)理論與技術(shù)是保障信息安全的核心。而密碼體制的設(shè)計(jì)與分析離不開困難問題和求解困難問題的算法。傳統(tǒng)的基于困難問題構(gòu)造的密碼體制一般考慮因子分解和離散對數(shù)難題。這些密碼體制發(fā)展時(shí)間較長,也經(jīng)過了一系列密碼分析技術(shù)的考驗(yàn)和修正。但是近年來,隨著人們對云計(jì)算和后量子時(shí)代信息安全的更多樣化和高強(qiáng)度的需求,對新型密碼體制,例如基于編碼問題、格問題的密碼體制的設(shè)計(jì)和研究正蓬勃興起。這些密碼體制帶來了很多理論和應(yīng)用上更好的性質(zhì),但是其安全性有待進(jìn)一步考慮。因此,對這些新型密碼體制困難問題求解算法的探討是當(dāng)前密碼學(xué)領(lǐng)域的研究熱點(diǎn)。本文的研究工作圍繞對幾類新型密碼體制困難問題求解算法的分析及其應(yīng)用展開,主要內(nèi)容和創(chuàng)新點(diǎn)包括：1.本文給出了一個(gè)存儲空間限制條件下的更有效的隨機(jī)線性碼解碼算法。隨機(jī)線性碼的解碼問題,是編碼理論和算法復(fù)雜度理論中最基本的問題之一。作為一個(gè)NP-困難問題,其難解性也被用來構(gòu)造密碼體制,例如著名的McEliece公鑰密碼體制等。1994年,Shor證明分解因子和離散對數(shù)問題在量子計(jì)算機(jī)模型下是多項(xiàng)式時(shí)間可求解的,而安全性基于編碼問題等NP-困難問題的密碼體制被普遍認(rèn)為具有抗量子攻擊的特性。作為此類密碼體制設(shè)計(jì)的基礎(chǔ),隨機(jī)線性碼的解碼問題和求解算法再次引起研究者的興趣。因而近年來,一系列算法被提出,使得求解這一問題所需的時(shí)間復(fù)雜度得到降低。而存儲空間復(fù)雜度,這一衡量算法在實(shí)際攻擊中效率的重要評估指標(biāo),目前的研究尚不充分。為此,我們考慮隨機(jī)線性碼的信息集解碼(information set decoding,ISD)算法在存儲空間有限制的條件下的效率。在Finiasz和Sendrier的ISD算法的理論體系結(jié)構(gòu)下,我們利用Shamir等人在2012年美密會上給出的分割技術(shù)(dissection technique)的思想,給出了新的確定性解碼算法,該算法在任一指定的存儲空間界限內(nèi)可達(dá)到更優(yōu)的時(shí)間復(fù)雜度。同時(shí),給出了新算法的更優(yōu)性的嚴(yán)格證明。從實(shí)踐的角度,由于在密碼分析的背景中,求解困難問題的算法作為敵手破譯能力的標(biāo)準(zhǔn),更側(cè)重算法在實(shí)際實(shí)現(xiàn)時(shí)的條件,故我們的算法可以作為一個(gè)更合理的評估基于編碼的密碼體制安全性的標(biāo)準(zhǔn)。從理論角度,這是對編碼問題,這一理論計(jì)算機(jī)科學(xué)中的重要問題,進(jìn)行的更深入的時(shí)間和存儲空間復(fù)雜度平衡的討論。2.本文給出了隨機(jī)整數(shù)格交與并的若干性質(zhì)及其在一類重要的前沿密碼體制——GGH安全性分析中的應(yīng)用。求解格困難問題的算法,作為一種經(jīng)典的公鑰密碼體制分析工具,一直被廣泛的研究。特別是近年來,基于格困難問題構(gòu)造的密碼體制由于具有后量子時(shí)代和云計(jì)算背景下的眾多理論及實(shí)際中的良好性質(zhì)而受到信息安全領(lǐng)域和密碼學(xué)界的高度關(guān)注,更使得格問題及其求解算法成為研究一系列重要密碼體制安全性的根本性手段。在本文中,我們的貢獻(xiàn)可以分為兩層次：首先我們分析了與密碼體制安全性緊密相關(guān)的隨機(jī)整數(shù)格的交與并的相關(guān)性質(zhì)。利用格與對偶格的性質(zhì)和整數(shù)矩陣標(biāo)準(zhǔn)型計(jì)算與整數(shù)環(huán)中隨機(jī)元素互素概率的對應(yīng)關(guān)系,我們得到：以很高的概率,隨機(jī)整數(shù)格的交可以保持格的維數(shù)、擴(kuò)大格的體積；并給出對擴(kuò)大后體積的準(zhǔn)確估計(jì)。對應(yīng)到密碼分析的背景中,該結(jié)論指出了構(gòu)造一類可以被有效算法求解的格困難問題子問題的具體方法,且結(jié)論成立的條件相符于格密碼體制在實(shí)際應(yīng)用環(huán)境中的條件。其次,作為一個(gè)應(yīng)用,我們進(jìn)一步分析了Plantard等人于2009年給出的使用最短向量(SVP)求解算法對GGH密碼體制的廣播攻擊,計(jì)算了攻擊成功需要的實(shí)例個(gè)數(shù),得出了攻擊的效率。我們的結(jié)論從數(shù)學(xué)上嚴(yán)格的解釋了攻擊成功的原因,而Plantard等人僅用實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證其攻擊的有效性。同時(shí),我們指出并修正了Plantard等人對其攻擊算法描述的一個(gè)不完備之處。此外,我們給出了一種新的使用最近向量(CVP)求解算法和格的交技術(shù)的攻擊,補(bǔ)充了Plantard等人原有攻擊中無法給出分析和證明的部分。由于GGH的設(shè)計(jì)思想被用于全同態(tài)加密等密碼學(xué)前沿課題,我們的方法和結(jié)論對此評估類前沿密碼體制的安全性和實(shí)用性具有參考價(jià)值。3.本文對F2上最短線性程序問題及Paar算法的進(jìn)行了理論分析。線性程序的概念源自符號計(jì)算。最短線性程序(Shortest Linear Program,SLP)問題是指給出一組域F上的線性表達(dá)式E,找到最短的線性程序來計(jì)算E。該問題于2012年被Boyar等人證明是NP-困難問題和MAX SNP-完全問題,故從算法復(fù)雜度理論角度,對該問題的多項(xiàng)式時(shí)問近似算法及其近似因子的上下界的研究具有重要性和普適性。當(dāng)域F為二元域F2時(shí),最短線性程序問題轉(zhuǎn)化為能實(shí)現(xiàn)一組線性表達(dá)式的無消去電路中XOR門的最小個(gè)數(shù)問題。作為通訊和編碼解碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)中最普遍的問題之一,該問題近年來被從新型密碼體制安全有效實(shí)現(xiàn)的角度被廣泛考慮。Paar算法是求解該問題最常見和有效的近似算法,但其有效性一直沒有得到嚴(yán)格的數(shù)學(xué)證明�；陔娐返慕M合結(jié)構(gòu),我們對Paar算法給出了在線性表達(dá)式的矩陣行重d=3,4情況下的理論分析,證明了這兩種情況下算法的近似因子；并結(jié)合組合數(shù)學(xué)技巧給出了SLP電路最小尺寸的一個(gè)下界,進(jìn)而得到Paar算法與平凡的實(shí)現(xiàn)算法的對比。由于d=3的實(shí)例對應(yīng)證明困難性時(shí)使用的實(shí)例類型,d=4的實(shí)例對應(yīng)實(shí)際工程中常用的常重碼參數(shù)取法,我們的結(jié)論證明了Paaar算法有效性中重要的一部分,也是對Boyar等人于2012年提出的公開問題的部分解決。
【關(guān)鍵詞】：隨機(jī)線性碼 存儲空間限制 隨機(jī)格的交 GGH密碼體制 最短線性程序問題 Paar算法
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TN918.1
【目錄】：

• 摘要4-7
• Abstract7-12
• 主要符號對照表12-14
• 第1章 緒論14-21
• 1.1 國內(nèi)外研究現(xiàn)狀16-18
• 1.2 本文主要創(chuàng)新點(diǎn)18-19
• 1.3 文章結(jié)構(gòu)19-21
• 第2章 預(yù)備知識21-38
• 2.1 線性碼的基本概念21-25
• 2.2 格的基本概念25-29
• 2.3 Hermite標(biāo)準(zhǔn)型、Smith標(biāo)準(zhǔn)型29-35
• 2.4 最短線性程序問題35-38
• 第3章 存儲空間限制條件下的信息集解碼算法38-60
• 3.1 隨機(jī)線性碼的解碼問題與存儲空間限制條件38-40
• 3.2 FS-ISD算法概述40-46
• 3.3 新的信息集解碼算法46-59
• 3.3.1 算法思想的來源46
• 3.3.2 新的算法46-48
• 3.3.3 復(fù)雜度分析48-55
• 3.3.4 算法對比55-59
• 3.4 小結(jié)59-60
• 第4章 隨機(jī)整數(shù)格的交及其在格密碼體制安全性分析中的應(yīng)用60-82
• 4.1 隨機(jī)整數(shù)格交與并的若干性質(zhì)60-72
• 4.1.1 隨機(jī)整數(shù)格的概念61
• 4.1.2 隨機(jī)整數(shù)格交與并的維數(shù)61-65
• 4.1.3 隨機(jī)整數(shù)格的并的體積65-67
• 4.1.4 隨機(jī)整數(shù)格的交的體積67-72
• 4.2 對格密碼體制GGH廣播攻擊的進(jìn)一步分析72-81
• 4.2.1 GGH密碼體制簡介72-73
• 4.2.2 Plantard等人對GGH的廣播攻擊73-74
• 4.2.3 對使用SVP求解算法攻擊方法的完善74-78
• 4.2.4 新的使用CVP(BDD)求解算法的攻擊78-81
• 4.3 小結(jié)81-82
• 第5章 對F_2上最短線性程序問題及Paar算法的理論分析82-94
• 5.1 Paar算法概述82-86
• 5.2 SLP電路最小尺寸的下界估計(jì)86-89
• 5.3 Paar算法的近似因子89-93
• 5.3.1 行重參數(shù)d=3的情形90-92
• 5.3.2 行重參數(shù)d=4的情形92-93
• 5.4 小結(jié)93-94
• 第6章 結(jié)論和研究計(jì)劃94-96
• 參考文獻(xiàn)96-105
• 致謝105-108
• 個(gè)人簡歷、在學(xué)期間完成的學(xué)術(shù)論文與研究成果108-109
• 學(xué)位論文評閱及答辯情況表109

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 孫艷華;王浩;張延華;;格縮減輔助MIMO檢測的非線性量化[J];北京郵電大學(xué)學(xué)報(bào);2010年01期

2 孫艷華;王浩;張延華;;復(fù)數(shù)域格縮減的MIMO檢測算法研究[J];電子科技大學(xué)學(xué)報(bào);2010年05期

3 曹海燕;李君;李光球;;基于可靠性累積概率的球形譯碼排序[J];電子學(xué)報(bào);2012年07期

4 劉經(jīng)南;于興旺;張小紅;;基于格論的GNSS模糊度解算[J];測繪學(xué)報(bào);2012年05期

5 LIU Hongwei;CAO Wenming;;Public Proof of Cloud Storage from Lattice Assumption[J];Chinese Journal of Electronics;2014年01期

6 毛新宇;程宇新;項(xiàng)海格;;混合的深度優(yōu)先及寬度優(yōu)先球形譯碼算法[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

7 張麗敏;;云環(huán)境下一種低成本的數(shù)據(jù)安全存儲和處理框架[J];電信科學(xué);2015年02期

8 楊孝鵬;馬文平;張成麗;;一種新型基于環(huán)上帶誤差學(xué)習(xí)問題的認(rèn)證密鑰交換方案[J];電子與信息學(xué)報(bào);2015年08期

9 毛新宇;范偉亮;王志軍;;簡化的固定復(fù)雜度球型譯碼算法[J];北京郵電大學(xué)學(xué)報(bào);2015年04期

10 ;Probability method for cryptanalysis of general multivariate modular linear equation[J];Science in China(Series F:Information Sciences);2009年10期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 ;A Computationally Efficient Exact ML Sphere Decoder[A];第九屆全國青年通信學(xué)術(shù)會議論文集[C];2004年

2 ;A Computationally Efficient Exact ML Sphere Decoder[A];第九屆全國青年通信學(xué)術(shù)會議論文集[C];2004年

3 劉海濤;程型清;李道本;;低復(fù)雜度復(fù)球譯碼檢測算法[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 楊玉慶;3GPP LTE下行接收系統(tǒng)的數(shù)字信號處理與VLSI實(shí)現(xiàn)研究[D];復(fù)旦大學(xué);2011年

2 陳睿;OFDM和MIMO系統(tǒng)中的預(yù)編碼技術(shù)研究[D];西安電子科技大學(xué);2011年

3 于興旺;多頻GNSS精密定位理論與方法研究[D];武漢大學(xué);2011年

4 伍前紅;可信密碼學(xué)計(jì)算的關(guān)鍵技術(shù)及其在電子商務(wù)中的應(yīng)用[D];西安電子科技大學(xué);2004年

5 余位馳;格基規(guī)約理論及其在密碼設(shè)計(jì)中的應(yīng)用[D];西南交通大學(xué);2005年

6 王興林;MIMO-OFDM系統(tǒng)中接收機(jī)及信道估計(jì)技術(shù)研究[D];北京郵電大學(xué);2006年

7 梁鵬;VLST-OFDM無線通信系統(tǒng)中檢測等問題的研究[D];北京郵電大學(xué);2006年

8 王保倉;幾類快速公鑰密碼的設(shè)計(jì)與分析[D];西安電子科技大學(xué);2006年

9 劉陳;無線通信系統(tǒng)中的空時(shí)編碼技術(shù)[D];東南大學(xué);2005年

10 李穎;平衰落信道下多天線系統(tǒng)中的信號檢測算法研究[D];國防科學(xué)技術(shù)大學(xué);2006年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 姜彤;LTE上行多用戶MIMO系統(tǒng)檢測算法研究[D];西安電子科技大學(xué);2011年

2 劉龍;無線MIMO系統(tǒng)檢測算法研究[D];西安電子科技大學(xué);2011年

3 雷勝;MIMO系統(tǒng)中信號檢測算法研究[D];北京郵電大學(xué);2011年

4 于婧;基于LTE的MIMO實(shí)現(xiàn)方案及檢測算法研究[D];南京郵電大學(xué);2011年

5 于健鵬;MIMO無線通信系統(tǒng)中迭代檢測技術(shù)研究[D];上海交通大學(xué);2012年

6 鞠春暉;高性能軟輸出K-Best MIMO檢測器的設(shè)計(jì)與實(shí)現(xiàn)[D];上海交通大學(xué);2012年

7 沈小祥;MIMO-OFDM系統(tǒng)聯(lián)合檢測算法研究[D];南京郵電大學(xué);2012年

8 楊祥;多用戶STBC/SFBC碼的性能研究[D];杭州電子科技大學(xué);2012年

9 許f愑，

本文編號：282872