幾類新型密碼體制困難問題求解算法的分析與應(yīng)用.pdf

1、密碼學(xué)理論與技術(shù)是保障信息安全的核心。而密碼體制的設(shè)計與分析離不開困難問題和求解困難問題的算法。傳統(tǒng)的基于困難問題構(gòu)造的密碼體制一般考慮因子分解和離散對數(shù)難題。這些密碼體制發(fā)展時間較長，也經(jīng)過了一系列密碼分析技術(shù)的考驗和修正。但是近年來，隨著人們對云計算和后量子時代信息安全的更多樣化和高強度的需求，對新型密碼體制，例如基于編碼問題、格問題的密碼體制的設(shè)計和研究正蓬勃興起。這些密碼體制帶來了很多理論和應(yīng)用上更好的性質(zhì)，但是其安全性有待進(jìn)一

2、步考慮。因此，對這些新型密碼體制困難問題求解算法的探討是當(dāng)前密碼學(xué)領(lǐng)域的研究熱點。
　　本文的研究工作圍繞對幾類新型密碼體制困難問題求解算法的分析及其應(yīng)用展開，主要內(nèi)容和創(chuàng)新點包括:
　　1.本文給出了一個存儲空間限制條件下的更有效的隨機線性碼解碼算法。
　　隨機線性碼的解碼問題，是編碼理論和算法復(fù)雜度理論中最基本的問題之一。作為一個NP-困難問題，其難解性也被用來構(gòu)造密碼體制，例如著名的McEliece公鑰密碼體制等

3、。1994年，Shor證明分解因子和離散對數(shù)問題在量子計算機模型下是多項式時間可求解的，而安全性基于編碼問題等NP-困難問題的密碼體制被普遍認(rèn)為具有抗量子攻擊的特性。作為此類密碼體制設(shè)計的基礎(chǔ)，隨機線性碼的解碼問題和求解算法再次引起研究者的興趣。因而近年來，一系列算法被提出，使得求解這一問題所需的時間復(fù)雜度得到降低。而存儲空間復(fù)雜度，這一衡量算法在實際攻擊中效率的重要評估指標(biāo)，目前的研究尚不充分。
　　為此，我們考慮隨機線性碼的信

4、息集解碼(information set decoding，ISD)算法在存儲空間有限制的條件下的效率。在Finiasz和Sendrier的ISD算法的理論體系結(jié)構(gòu)下，我們利用Shamir等人在2012年美密會上給出的分割技術(shù)(dissectiontechnique)的思想，給出了新的確定性解碼算法，該算法在任一指定的存儲空間界限內(nèi)可達(dá)到更優(yōu)的時間復(fù)雜度。同時，給出了新算法的更優(yōu)性的嚴(yán)格證明。
　　從實踐的角度，由于在密碼分析的背

5、景中，求解困難問題的算法作為敵手破譯能力的標(biāo)準(zhǔn)，更側(cè)重算法在實際實現(xiàn)時的條件，故我們的算法可以作為一個更合理的評估基于編碼的密碼體制安全性的標(biāo)準(zhǔn)。從理論角度，這是對編碼問題，這一理論計算機科學(xué)中的重要問題，進(jìn)行的更深入的時間和存儲空間復(fù)雜度平衡的討論。
　　2.本文給出了隨機整數(shù)格交與并的若干性質(zhì)及其在一類重要的前沿密碼體制——GGH安全性分析中的應(yīng)用。
　　求解格困難問題的算法，作為一種經(jīng)典的公鑰密碼體制分析工具，一直被廣

6、泛的研究。特別是近年來，基于格困難問題構(gòu)造的密碼體制由于具有后量子時代和云計算背景下的眾多理論及實際中的良好性質(zhì)而受到信息安全領(lǐng)域和密碼學(xué)界的高度關(guān)注，更使得格問題及其求解算法成為研究一系列重要密碼體制安全性的根本性手段。
　　在本文中，我們的貢獻(xiàn)可以分為兩層次:
　　首先我們分析了與密碼體制安全性緊密相關(guān)的隨機整數(shù)格的交與并的相關(guān)性質(zhì)。利用格與對偶格的性質(zhì)和整數(shù)矩陣標(biāo)準(zhǔn)型計算與整數(shù)環(huán)中隨機元素互素概率的對應(yīng)關(guān)系，我們得到:

7、以很高的概率，隨機整數(shù)格的交可以保持格的維數(shù)、擴(kuò)大格的體積;并給出對擴(kuò)大后體積的準(zhǔn)確估計。對應(yīng)到密碼分析的背景中，該結(jié)論指出了構(gòu)造一類可以被有效算法求解的格困難問題子問題的具體方法，且結(jié)論成立的條件相符于格密碼體制在實際應(yīng)用環(huán)境中的條件。
　　其次，作為一個應(yīng)用，我們進(jìn)一步分析了Plantard等人于2009年給出的使用最短向量(SVP)求解算法對GGH密碼體制的廣播攻擊，計算了攻擊成功需要的實例個數(shù)，得出了攻擊的效率。我們的結(jié)論

8、從數(shù)學(xué)上嚴(yán)格的解釋了攻擊成功的原因，而Plantard等人僅用實驗數(shù)據(jù)驗證其攻擊的有效性。同時，我們指出并修正了Plantard等人對其攻擊算法描述的一個不完備之處。此外，我們給出了一種新的使用最近向量(CVP)求解算法和格的交技術(shù)的攻擊，補充了Plantard等人原有攻擊中無法給出分析和證明的部分。由于GGH的設(shè)計思想被用于全同態(tài)加密等密碼學(xué)前沿課題，我們的方法和結(jié)論對此評估類前沿密碼體制的安全性和實用性具有參考價值。
　　3.

9、本文對F2上最短線性程序問題及Paar算法的進(jìn)行了理論分析。
　　線性程序的概念源自符號計算。最短線性程序(Shortest Linear Program，SLP)問題是指給出一組域F上的線性表達(dá)式E，找到最短的線性程序來計算E。該問題于2012年被Boyar等人證明是NP-困難問題和MAX SNP-完全問題，故從算法復(fù)雜度理論角度，對該問題的多項式時間近似算法及其近似因子的上下界的研究具有重要性和普適性。
　　當(dāng)域F為二元

10、域F2時，最短線性程序問題轉(zhuǎn)化為能實現(xiàn)一組線性表達(dá)式的無消去電路中XOR門的最小個數(shù)問題。作為通訊和編碼解碼系統(tǒng)的設(shè)計與實現(xiàn)中最普遍的問題之一，該問題近年來被從新型密碼體制安全有效實現(xiàn)的角度被廣泛考慮。Paar算法是求解該問題最常見和有效的近似算法，但其有效性一直沒有得到嚴(yán)格的數(shù)學(xué)證明。
　　基于電路的組合結(jié)構(gòu)，我們對Paar算法給出了在線性表達(dá)式的矩陣行重d=3，4情況下的理論分析，證明了這兩種情況下算法的近似因子;并結(jié)合組合數(shù)