李小偉開題報告

成都理工大學(xué)2009級碩士學(xué)位研究生畢業(yè)論文開題報告to開題報告to論文題目：布爾函數(shù)非線性度相關(guān)分析導(dǎo)師：范安東學(xué)生：李小偉專業(yè)：計算數(shù)學(xué)研究方向：信息安全中的計算方法成都理工大學(xué)管理科學(xué)學(xué)院2011年9月1、選題依據(jù)及意義1.1國內(nèi)外研究現(xiàn)狀及課題的提出在當(dāng)今的網(wǎng)絡(luò)信息時代，信息的安全保密至關(guān)重要，密碼按加密方式的不同可分為分組密碼和流密碼。分組密碼的典型代表是DES，DES體制的安全強(qiáng)度取決于S盒的安全性能。而S盒可由一組布爾函數(shù)來實現(xiàn)，流密碼的安全性則主要依賴于密鑰流序列的安全性，常用的密鑰流生成器是非線性濾波生成器和非線性組合生成器，對它們的研究可歸結(jié)為對布爾函數(shù)的研究。不僅如此，布爾函數(shù)在認(rèn)證系統(tǒng)中也有十分重要的應(yīng)用，比如利用布爾函數(shù)可以構(gòu)造單向函數(shù)，單向陷門函數(shù)和雜湊函數(shù)等，為了保證密碼系統(tǒng)有較強(qiáng)的保密功能，所使用的布爾函數(shù)必須滿足一定的性質(zhì)，如平衡性、相關(guān)免疫性、高的代數(shù)次數(shù)、高的非線性度、擴(kuò)散性和嚴(yán)格雷崩性。近年來，對布爾函數(shù)的各種性質(zhì)進(jìn)行了大量的研究，特別是對抵抗相關(guān)攻擊的相關(guān)免疫函數(shù)類、抗線性分析的Bent函數(shù)類以及滿足不同性質(zhì)的多輸出布爾函數(shù)的研究，但是仍由很多問題有待解決。1985年Siegenthaler為了防止相關(guān)攻擊，提出了相關(guān)免疫函數(shù)的概念，對n個獨立的均勻分布的二元隨機(jī)變量，對于任意下標(biāo)的子集，若統(tǒng)計獨立則m階相關(guān)免疫；馮登國、裴定一對相關(guān)免疫從重量分析的角度進(jìn)行了闡述，溫巧燕、林須瑞從譜分析的角度對相關(guān)免疫也進(jìn)行了研究，楊義先等從矩陣分析的角度進(jìn)行了描述，可以證明這些描述之間是等價的。這些不同角度的描述對相關(guān)免疫的研究提供了很多不同的工具，隨后大量學(xué)者對相關(guān)免疫函數(shù)的構(gòu)造和計數(shù)做了大量工作，提出了m階相關(guān)免疫函數(shù)及非退化一階相關(guān)免疫函數(shù)的構(gòu)造，二階相關(guān)免疫函數(shù)非退化的一個充分條件，而相關(guān)免疫函數(shù)的計數(shù)問題是一備受關(guān)注的重要課題，Mitchel首先于1990年首次討論了一階相關(guān)免疫函數(shù)的計數(shù)問題。給出一階相關(guān)免疫函數(shù)個數(shù)的下界為2%1，此后相關(guān)免疫函數(shù)的計數(shù)下界不斷被改進(jìn)。為了抵抗最佳線性逼近，Rothaus等引入了Bent函數(shù)的概念，Bent函數(shù)具有最高非線性度，在密碼、編碼理論、序列以及設(shè)計理論中有著重要應(yīng)用，因而引起了密碼學(xué)界的極大關(guān)注。此后，相關(guān)學(xué)者對Bent函數(shù)引入了一些等價的定義，使得Bent函數(shù)的研究大大得到深入研究，對于Bent函數(shù)的性質(zhì)，學(xué)者從平衡性、擴(kuò)散性、嚴(yán)格雷崩準(zhǔn)則、函數(shù)結(jié)構(gòu)、最高代數(shù)次數(shù)、相關(guān)免疫性、自相關(guān)度、符合率、多元相關(guān)度等方面做了大量的研究。在Bent函數(shù)的構(gòu)造方面一般分為間接構(gòu)造和直接構(gòu)造，直接構(gòu)造主要有MM(Maiorana-Macfarland)類和PS(partialspread)類。PS類的構(gòu)造只是理論性的，怎么實現(xiàn)還需要進(jìn)一步的研究。Dobbertin等人用Niho幕函數(shù)給出了新的Bent函數(shù)的構(gòu)造。他們把問題歸結(jié)為求域上一些方程的解的個數(shù)，具有較強(qiáng)的技巧性。雖然Bent函數(shù)具有一些優(yōu)良的密碼性質(zhì)，但它也有一些缺陷，如不具備平衡性和相關(guān)免疫性。為此，Carlet引入了部分Bent函數(shù)的概念，它具備Bent函數(shù)的優(yōu)點，同時具備平衡性和相關(guān)免疫性。隨后引入的平穩(wěn)函數(shù)的概念，這類函數(shù)保持了部分Bent函數(shù)的所有密碼特性且沒有非零線性結(jié)構(gòu)。近年來，對布爾函數(shù)的密碼學(xué)性質(zhì)的研究多局限于單輸出布爾函數(shù)，對于流密碼，如果在非線性濾波生成器和非線性組合生成器中選用多輸出布爾函數(shù)作為濾波函數(shù)和組合函數(shù)就可以加快密鑰流的生成速度；對于分組密碼，S盒是其核心部分，要想設(shè)計一個具有較高安全性能的分組密碼體制，必須首先選取一些具有良好密碼性質(zhì)的多輸出布爾函數(shù)，多輸出布爾函數(shù)描述的是n個輸入、m個輸出的變換盒。Gopalakrishnan在1995年引入了多輸出相關(guān)免疫函數(shù)的概念，陳魯生隨后引入了另外一個等價的定義，并且給出了一種由較少自變量的多輸出相關(guān)免疫函數(shù)構(gòu)造較多變量的多輸出相關(guān)免疫函數(shù)的方法。實際中多選用無偏的且分量函數(shù)相互獨立的多輸出相關(guān)免疫函數(shù)，即彈性函數(shù)。彈性函數(shù)首先由Chor等和Bennett等提出并研究，這類函數(shù)可用于容錯分布計算和量子密碼學(xué)中的密鑰分配，以及流密碼中隨機(jī)序列的產(chǎn)生，非線性度和代數(shù)次數(shù)是衡量多輸出函數(shù)是否具有好的密碼性質(zhì)的重要指標(biāo)，故對彈性函數(shù)的研究可歸納為2個方面：一是構(gòu)造高非線性度的(n,m,t)彈性函數(shù)，而是構(gòu)造次數(shù)d>m的高非線性度的(n,m,t)彈性函數(shù)。Stinson和Massey在1995年第一次討論了彈性函數(shù)的非線性度，并應(yīng)用Kerdock和Preparata碼構(gòu)造了一類彈性函數(shù)，Sarkar和Maitra證明了對m<=n-1，彈性函數(shù)非線性度的上界nlmax(n,m)<2〃-"2m一1，取得了較好的效果;Tarannikov等隨后構(gòu)造出了一種m階的彈性函數(shù)，使其非線性度達(dá)到了2n—72n-1-2m-1(—-一<m<n-2)，另外他通過新的構(gòu)造方法證明了對0.6n-1<=m<=n-2，有nlmax(n,m)<2〃-i-2m-i；Pasalic和Maitra利用糾錯碼構(gòu)造彈性函數(shù)，通過尋找盡量多的不相交線性碼來提高函數(shù)的非線性度，但未給出不相交線性碼的構(gòu)造方法，Johansson對此法進(jìn)行改進(jìn)，利用級聯(lián)線性糾錯碼和高非線性度函數(shù)而得到高非線性度的彈性函數(shù)。但是同時具有代數(shù)次數(shù)d>m又具有高非線性度的(n,m,t)彈性函數(shù)的構(gòu)造比較少，Cheon在2001年給出了這方面的研究：如果存在線性糾錯碼[n,m,t]則對于任意的非負(fù)整數(shù)D，存在(n+D+1,m,t-1)彈性函數(shù)，且其代數(shù)次數(shù)為D，非線性度不小于2n+d一2n[<2n+Q+i]+2n-i。EnesPasalic在2003年構(gòu)造了一個(2m-i-1)階彈性函數(shù)G，非線性度為Ng>22m-2+e-22m-2-mX22m-1-1，次數(shù)為d=2m-1-1，其中e=[log2[b(2m-1)]],這個結(jié)果明顯要比Cheon的結(jié)果好。而近年來walsh譜理論亦成為研究布爾函數(shù)性質(zhì)的有力工具，Massey和肖國鎮(zhèn)教授在這一領(lǐng)域開陣了卓有成效的工作。依據(jù)布爾函數(shù)的walsh譜的概率意義可以對布爾函數(shù)與自變量線性和的相關(guān)度以及布爾函數(shù)的最佳線性(仿射)逼近進(jìn)行合理的概率解釋。1.2論文選題意義目前，構(gòu)造同時滿足其他密碼學(xué)性質(zhì)的相關(guān)免疫函數(shù)是一個值得研究的問題，對偶的Bent函數(shù)的還需要進(jìn)一步的研究，構(gòu)造出更多的有限域上的Bent函數(shù)也是一個有待解決的問題，布爾函數(shù)的某些性質(zhì)之間往往存在著一定的制約關(guān)系，一種性能指標(biāo)的實現(xiàn)或提高，可能導(dǎo)致另外一些性能指標(biāo)的降低，因此，如何得到具有更多良好密碼性質(zhì)的布爾函數(shù)成為密碼學(xué)上的一個重要研究課題。2、論文主要內(nèi)容2.1、 研究內(nèi)容同時具有若干優(yōu)良密碼性質(zhì)的布爾函數(shù)的一些理論研究，主要是高非線性度與高代數(shù)次數(shù)、較高代數(shù)次數(shù)與較好擴(kuò)散性的研究；二次非線性度達(dá)到最大值的布爾函數(shù)的構(gòu)造方法和具有最優(yōu)代數(shù)免疫階的布爾函數(shù)的構(gòu)造研究；walsh譜理論與非線性度的相關(guān)分析，揭示兩者之間的區(qū)別與聯(lián)系；具有特殊walsh譜值的幾類布爾函數(shù)，并利用walsh譜的概率意義對布爾函數(shù)進(jìn)行譜分析；構(gòu)造較高非線性度布爾函數(shù)的方法研究，主要利用HillClimbing方法的本質(zhì)來改變布爾函數(shù)的局部輸出；第二非線性度的研究，主要指出其在抵抗最佳仿射逼近攻擊方面的意義，以及折中量化各項指標(biāo)的理論研究；2.2、 擬解決的關(guān)鍵技術(shù)問題及主要思路利用bent函數(shù)構(gòu)造高非線性度布爾函數(shù)的時候，如何避免造成代數(shù)次數(shù)下降？對于兩個m元Bent函數(shù)f(x),f(x)，若f(x)=xf(X&x折(f)x，則1 2 m+11 ml- 2非線性度滿足N>N+N=2m-1-2m/2-1+2m-1-2m/2-1=2m—2m/2；通過遞歸，構(gòu)造兩個bent函數(shù)的線性函數(shù)，最終得到m+k元布爾函數(shù)，可以證明其代數(shù)次數(shù)沒有降低；其中用到武傳坤研究員的引理，如下：設(shè)f(x),f(x)是兩個n元布爾函數(shù)，如果f(x)=xf(x)+(1+x)f(x)，1 2 n+11 n+12貝UNf>Nf+Nf。而m元bent函數(shù)和最大非線性度2婦—2m/2一1亦是等價的。在HillClimbing算法中如果交換任意兩個輸出都不能提高非線性度，如何處理？可以考慮順時針或者逆時針同時交換三個或者四個輸出向量的方法，但是此時可能會對其他的密碼指標(biāo)存在影響。所以要做出相應(yīng)的判斷準(zhǔn)則和處理。3、已完成的工作和下一步需要完成的工作3.1已完成的工作1:給出構(gòu)造高非線性度布爾函數(shù)的一個方法，設(shè)fi(X),f2(X)是兩個m元布爾函數(shù)，若f(x)=Xm+if](x)+(Xm+1+1)f2(x)，則我們可以證明其非線性度Nf>2m—2m/2。反復(fù)遞歸構(gòu)造這樣的函數(shù)，我們就可以得到一個m+k元布爾函數(shù)，使其非線性度大于2〃-2。只要布爾函數(shù)在某個子空間上的常值，就可以根據(jù)它來構(gòu)造出高非線性度的平衡函數(shù)。2：對任意V到V的函數(shù)F=(f,f，…f)，N(F)=minN,其中NLCf是F的nm 12m1 feNLCFf F分量函數(shù)的所有非零線性組合的集合，N(F)=mind(F,中),其中AF表示所有從V2 ^eAF n'm nn,m到Vm的仿射函數(shù)的集合，d(F,①)=\{xeV:F(x)。①(x)},則有N2(F)>N、F)。由以上可知，兩類非線性度比較高的布爾函數(shù)對其分量函數(shù)的任意非零線性組合進(jìn)行的最佳仿射逼近攻擊，也可抵抗最佳多輸出仿射逼近的攻擊。3：對n元布爾函數(shù)f(x)，N(f)=2n-1(1—maxjw(f)(w)|)，Walsh循環(huán)譜與非線性度的密切關(guān)系可以從概率意義上使得對布爾函數(shù)的非線性度的解釋更加合理，更加有效。3.2下一步要完成的工作在利用HillClimbing算法的思想進(jìn)行構(gòu)造布爾函數(shù)的時候，如果已經(jīng)達(dá)到最大非線性度，但是不滿足需求，需要同時順時針或逆時針交換三個以上的輸出向量，以求得更高的非線性度，但此時代數(shù)次數(shù)是否下降？其他密碼指標(biāo)是否下降？如果下降則能不能控制到一個可以接受的程度？三類具有特殊walsh譜值的布爾函數(shù)之間的結(jié)構(gòu)關(guān)系刻畫方面，bent函數(shù)在什么條件下可以用plateaued函數(shù)來進(jìn)行刻畫？同時，plateaued函數(shù)在什么條件下可以用bent函數(shù)進(jìn)行刻畫？

4、支撐條件1） 圖書館豐富的資源文獻(xiàn)，文獻(xiàn)數(shù)據(jù)庫的方便使用；2） 導(dǎo)師的悉心指導(dǎo)；3） 硬件計算機(jī)資源的支持；3）密碼學(xué)基礎(chǔ)學(xué)科具有較好的基礎(chǔ)知識，扎實的理論基礎(chǔ)，充足的學(xué)習(xí)時間。5、論文進(jìn)度安排論文進(jìn)度安排起止時間畢業(yè)論文工作階段要求2010.01-2010.06查閱相關(guān)課題的發(fā)展，確定論文題目；2010.07-2010-12收集相關(guān)的資料、文獻(xiàn)，并做深入研究，完成開題報告；2011.01-2011.06文獻(xiàn)、資料的整理研究，并補(bǔ)充論文需要的文獻(xiàn)、資料；2011.06-2011.12撰寫論文，完成初稿；2012.01-2012.04修改論文，定稿打印，送專家評申；2012.05論文答辯6、論文章節(jié)安排第一章密碼算法構(gòu)造準(zhǔn)則一、 密碼算法指標(biāo)二、 如何構(gòu)造較好的密碼算法第二章布爾函數(shù)非線性度一、 布爾函數(shù)二、 布爾函數(shù)的非線性度三、 非線性度拓展第三章walsh譜理論與非線性度一、 walsh譜二、 walsh譜與非線性度三、 用walsh譜分析函數(shù)非線性度第四章構(gòu)造高非線性度布爾函數(shù)一、 構(gòu)造高非線性度布爾函數(shù)二、 HillClimbing算法三、 HillClimbing算法的優(yōu)化四、 其他構(gòu)造方法及優(yōu)缺點結(jié)致參結(jié)致參參考文獻(xiàn)溫巧燕,肖國鎮(zhèn).二階相關(guān)免疫函數(shù)的構(gòu)造與計數(shù)[J].通信學(xué)報,1998,19(8)：39-44.⑵MatsuiM.LinearCryptanalysisMethodforDESCipher[C].AdvancesinCryptology-EUROCRYPT’93,Berlin:Spring-Verlag:386-397.馮登國.頻譜理論及其在通信保密技術(shù)中的應(yīng)用，博士學(xué)位論文.西安電子科技大學(xué)1995.CracraftMA.CrosstalkanalysisforNonparallelTransmissionLinesUsingPEECwithaDynamicGreen'sFunctionFormulation[C]InternationalSymposiumonEMC,2006:29-33.M.H.DawsonandS.E.Tavares.AnExpandedSetofDesignCriteriaforSubstitutionBoxandTheirUseinStrengtheningDES-likeCryptosystemsIEEEPacificRimConferenceonCommunications,ComputerandSigualProcessing,1991:191-195.M.H.DawsonandS.E.Tavares.AnExpandedSetofDesignCriteriaBasedonInformationTheoryanditsRelationtoDifferen-tial-LikeAttacks,AdvancesinCryptologyEUROCRYPT’91Processing,Berlin:Springer-Verlag,1991:352-367.KCGupta,PSarkar.ImprovedconstructionofnonlinearresilientS-boxes[J],IEEETransactionsonInformationTheory,2005,51(1):339-348.Dobbertin.ConstructionofbentfunctionandbalancedBooleanfunctionswithhighnonlinearity[A],Proceedingsofthe1994LeuvenWorkshoponCryptographicAlgorithms[C],Berlin,Spring-Verlag,1995:61-74.ACanteaut,MDaum,HDobbertin,andGLeander.Normalandnonnormalbentfunctions[A].inProc.WorkshoponCodingandCryptography(WCC2003)[C].2003:91-100.CCarlet,HDobbertin,andGLeander.Normalextensionofbentfunctions[J].IEEETransacionsonInformationTheory,2004,50(11):2880-2885.溫巧燕,肖國鎮(zhèn).一階相關(guān)免疫布爾函數(shù)計數(shù)下界的改進(jìn)[J].通信學(xué)報,2003,24(3):16-22.CarletC.Oartially-Bentfunctions[J].AdvancesinCrypto792,1993,27(3):280-291.PattersonNJ,WiedemannDH.Correctingtothecoveringradiusofthe(215,16)Reed-Mullercodeisatleast16272[J].IEEETransactionsonInformationTheory,1998,36(2):443-448.ChabaudF,VaudenayS.Linksbetweendifferentialandlinearcryptanalysis[J].Europ-crypto’94,1994,28(3):356-365.GopalakrishmanK,StinsonDR.Threecharacterizationsofnon-binarycorrelation-immuneandfunctions[J].Designs,CodesandCryptography,1995,5(4):241-251.SarkarP,MaitraS.NonlinearityBoundsan