（應(yīng)用數(shù)學(xué)專業(yè)論文）低差分一致性函數(shù)的研究.pdf

博士學(xué)位論文 摘要 低差分一致性函數(shù)可分為幾乎完全非線性( a b n o s tp e r f e c tn o n l i n e a r ，a p n ) 函 數(shù)、完全非線性l p e r f e c tn o n l i n e a r ，p n ) 函數(shù)和其它低差分一致性函數(shù)它們在密 碼學(xué)和代數(shù)學(xué)中都有廣泛的應(yīng)用本文構(gòu)造和分析了一批低差分一致性函數(shù)，具體 成果如下： 在第二章中，由已知的a p n 冪函數(shù)特例歸納出奇特征域中的兩類a p n 冪函數(shù)， 并以二次特征和d i c k s o n 多項(xiàng)式為工具給出證明新的a p n 函數(shù)可用來解釋h e l l e - s e t h 提出的兩種公開情況，并且可用來證明d o b b e r t i n 猜想最后，將前面提出的兩 類a p n 函數(shù)加以推廣，得出特定形式下冪函數(shù)的差分一致屬性在證明過程中創(chuàng) 造性地引入d i c k s o n 多項(xiàng)式來求解方程，使得方程的求解變得簡單可行 在第三章中，首先討論了特征為2 的域中已知的幾類a p n 多項(xiàng)式函數(shù)的等價(jià)性 質(zhì)，接著給出了一類新的a p n 多項(xiàng)式函數(shù)，并進(jìn)一步分析了它的b e n t 屬性該a p n 函數(shù)不c a r l e t c h a r p i n - z i n o v i e v ( c c z ) 等價(jià)于d o b b e r t i n 函數(shù)，且在特定條件下不 等價(jià)于已知的函數(shù)其次，將特征為3 的域中一類已知的a p n 函數(shù)推廣到奇特征域 中，新的a p n 函數(shù)包含已知的a p n 函數(shù)為特例最后，利用線性多項(xiàng)式和跡函數(shù)， 通過引入中間變量的方法計(jì)算了一大類a p n 函數(shù)的w a l s h 譜計(jì)算結(jié)果表明該類函 數(shù)的w a l s h 譜和g o l d 函數(shù)的w a l s h 譜相同，從而確定了它們的非線性度，而函數(shù)的 非線性度可以衡量其抗線性分析能力 在第四章中，將已知的a p n 多項(xiàng)式函數(shù)推廣到奇特征域中，加上特定的條件而 得出幾類p n 多項(xiàng)式函數(shù)，且證明了其中兩類p n 函數(shù)不c c z 等價(jià)于已知的p n 函數(shù)， 由此給出了兩類半域在特定的條件下，所構(gòu)造的半域也與已知的半域不合痕我 們在證明過程中給出了判斷c c z 等價(jià)和擴(kuò)張仿射( e x t e n d e da f f i n e ，e a ) 等價(jià)的一種 方法最后，討論了特定條件下d i u o n 多項(xiàng)式的差分一致性 在第五章中，結(jié)合前面的工具和方法，構(gòu)造了幾類低差分一致性函數(shù)我們注 意到除- j e d e l 和p o t t 最近發(fā)現(xiàn)的a p n 函數(shù)外，其它已知的a p n 多項(xiàng)式函數(shù)都是二 次的，而且在易。中還沒有發(fā)現(xiàn)a p n 置換函數(shù)我們構(gòu)造的低差分一致性函數(shù)不限 于二次，而且具有置換特性，從而給設(shè)計(jì)和構(gòu)造s 盒提供了更多的方法在第3 節(jié)中， 引入了幾乎低差分一致性概念，并構(gòu)造了幾類幾乎低差分致性函數(shù) 關(guān)鍵詞：布爾函數(shù)；線性多項(xiàng)式；低差分一致性；完全非線性；幾乎完全非線性； c c z 等價(jià) 低差分一致性函數(shù)的研究 m a b s tr a c t l o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n sc a r lb ed i v i d e di n t ot h r e ec l a s s e s ：a l m o s t p e r f e c tn o n l i n e a r ( a p n ) f u n c t i o n s ，p e r f e c tn o n l i n e a r ( p n ) f u n c t i o n sa n d o t h e rl o w d i f f e r e n t i a lu n i f o r m i t yf u n c t i o n s t h e yp l a ya ni m p o r t a n tr o l ei nc r y p t o g r a p h ya n d a l g e b r a i nt h i sd i s s e r t a t i o n ，w ec o n s t r u c ta n da n a l y z ea s e r i e so fl o wd i f f e r e n t i a l u n i f o r m i t yf u n c t i o n s t h em a i nc o n t r i b u t i o n sa r e 嬲f o l l o w s i nc h a p t e r2 ，t w of a m i h e so fa p np o w e rf u n c t i o n so no d dp r i m ef i e l da r e d e d u c e df r o mt h ek n o w nr e s u l t so fa p np o w e rf u n c t i o n s t h e i ra p np r o p e r t yc a n b ep r o v e db ya p p l y i n gq u a d r a t i cc h a r a c t e ra n dd i c k s o np o l y n o m i a l b a s e do nt h e n e wa p nf u n c t i o n s ，w ec a l le x p l a i nt h et w oo p e nc a s e si n t r o d u c e db yh e l l e s e t ha n d t h e np r o v ed o b b e r t i n sc o n j e c t u r e f i n a l l y , w eg e n e r a l i z et h en e wa p nf u n c t i o n s a n dg e tt h ed i f f e r e n t i a lu n i f o r m i t yo fp o w e rf u n c t i o n sw i t hac e r t a i nf o r m w e i n n o v a t i v l yi n t r o d u c ed i c k s o np o l y n o m i a lt os o l v et h ee q u a t i o n ，w h i c hm a k e st h e p r o c e s se a s ya n df e a s i b l e i nc h a p t e r3 ，w ef i r s t l yd i s c u s st h ee q u i v a l e n c eo ft h ek n o w na p np o l y n o m i a l f u n c t i o n so i l b i n a r yf i e l d m o r e o v e r ，w ep r e s e n tan e wf a m i l yo fa p np o l y n o m i a l f u n c t i o n sa n da n a l y z et h e i rb e n tp r o p e r t y t h e s en e wa p np o l y n o m i a lf u n c t i o n s a r en o tc a r l e t c h a r p i n - z i n o v i e v ( c c z ) e q u i v a l e n tt od o b b e r t i nf u n c t i o n s ，a n da r e n o te q u i v a l e n tt ot h ek n o w nf u n c t i o n su n d e rc e r t a i nc o n d i t i o n s s e c o n d l y , f r o m t h ek n o w nr e s u l to nt h e 知l do fc h a r a c t e r3 ，w es i m i l a r l yc o n s t r u c taf a m i l yo f a p nf u n c t i o n so no d dp r i m ef i e l d t h ek n o w na p nf u n c t i o n sc a nb es e e n 嬲t h e s p e c i a lc a s e so fo u rn e wr e s u l t s f i n a l l y , w eo b t a i nt h ew 如hs p e c t r u mo fa f a m i l y o fa p nf u n c t i o n sb a s e do nl i n e a rp o l y n o m i a l ，t r a c em a p p i n ga n di n t e r m e d i a t e v a r i a b l e w ef i n dt h a tt h ew a l s hs p e c t r u mo ft h e s ef u n c t i o n si ss a m ea 8t h a to f g o l df u n c t i o n s o u rr e s u l t sd e t e r m i n a t et h en o n l i n e a r i t yo ft h ef u n c t i o n sw h i c h m e a s u r e st h e i rr e s i s t a n c et ol i n e a rc r y p t a n a l y s i s i nc h a p t e r4 ，w ef u r t h e rs t u d yt h ek n o w na p np o l y n o m i a lf u n c t i o n so no d d p r i m ef i e l da n dt h e ng e ts e v e r a lf a m i h e so fp np o l y n o m i a lf u n c t i o n su n d e r c e r t a i n c o n d i t i o n s w ep r o v et h a tt w of a m i l i e so ft h e ma r en o tc c ze q u i v a l e n tt ot h e k n o w np nf u n c t i o n s t h e nw eg e tt w of a m i l i e so fs e m i f i e l d s u n d e rc e r t a i nc o n - d i t i o n s ，t h en e ws e m i f i e l d sa r en o ti s o t o p i ct oa n yo t h e rk n o w no n e w ep r e s e n ta m e t h o dt od e t e r m i n ec c z - e q u i v a l e n c ea n de a ( e x t e n d e da f f i n e ) e q u i v a l e n c ei no u r i i 博士學(xué)位論文 p r o o f f i n a l l y , w ed i s c u 鼴t h ed i f f e r e n t i a lu n i f o r m i t yo fd i l l o n sp o l y n o m i a lu n d e r c e r t a i nc o n d i t i o n s i nc h a p t e r5 ，w eg i v es o m el o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n sb yt h ew a y s i n t r o d u c e db e f o r e w bn o t et h a tt h ek n o w na p np o l y n o m i a lf u n c t i o n sa r ea l l q u a d r a t i ce x c e p tt h ea p n f u n c t i o n sr e c e n t l yf o u n db ye d e la n dp o t t i n 昱2 ，i ，t h e a p n p e r m u t a t i o nh a sn o ty e tb e e nf o u n d w ec o n s t r u c tl o wd i f f e r e n t i a lu n i f o r m i w f u n c t i o n sw h i c ha r en o tq u a d r a t i c e s p e c i a l l y , s o m eo ft h e ma r ep e r m u t a t i o n s w e p r o v i d em o r em e t h o d st od e s i g nt h es - b o xb yu s i n gt h e m i ns e c t i o n3 ，w ei n t r o - d u c et h ec o n c e p to fa l m o s tl o wd i f f e r e n t i a lu n i f o f r u i t ya n dc o n s t r u c ts e v e r a lf a m i l i e s o fa l m o s tl o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n s k e yw o r d s ：b o o l e a nf u n c t i o n s ；l i n e a rp o l y n o m i a l ；l o w d i f f e r e n t i a lu n i - f o r m i t y ；p e r f e c tn o n l i n e a r ；a l m o s tp e r f e c tn o n l i n 黜, c c z - e q u i v a l e n c e i i i 湖南大學(xué) 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究 所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包 含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出 重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到 本聲明的法律后果由本人承擔(dān)。 作者簽名： 如長 l ，) 日期：壚苔年壇月7 e l 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同 意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許 論文被查閱和借閱。本人授權(quán)湖南大學(xué)可以將本學(xué)位論文的全部或部分 內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段 保存和匯編本學(xué)位論文。 本學(xué)位論文屬于 1 、保密口，在年解密后適用本授權(quán)書。 2 、不保密邑 ( 請?jiān)谝陨舷鄳?yīng)方框內(nèi)打“”) 作者簽名： 導(dǎo)師簽名： 查壓卵 a 溶沈 日期：少夠年肜月7 日 日期：。孵1 2 月77 日 博士學(xué)位論文 第1 章緒論 1 1 低差分一致性函數(shù)的研究背景與意義 隨著計(jì)算機(jī)技術(shù)與網(wǎng)絡(luò)通信技術(shù)的迅速發(fā)展，社會(huì)生活中數(shù)字化、信息化、網(wǎng) 絡(luò)化發(fā)展趨勢正在影響并改變?nèi)藗兊纳罘绞骄W(wǎng)絡(luò)和信息技術(shù)的研發(fā)與普及，極 大地促進(jìn)了科學(xué)、技術(shù)、文化、經(jīng)濟(jì)、政治以及軍事等領(lǐng)域的發(fā)展，給人們的社會(huì) 生活提供了便利然而，在享受網(wǎng)絡(luò)與通信技術(shù)帶來的便利的同時(shí)，人們也不得不 面對日益嚴(yán)峻的信息安全問題在信息采集、存儲(chǔ)、傳輸?shù)纫幌盗羞^程中信息的保 密性、完整性、可用性等信息安全問題應(yīng)運(yùn)而生如在網(wǎng)絡(luò)中存儲(chǔ)和傳輸?shù)拇罅繑?shù) 據(jù)都需要對目標(biāo)數(shù)據(jù)加以保護(hù)，以免被盜用、泄露、篡改、偽造等電子商務(wù)、電 子銀行等基于網(wǎng)絡(luò)的經(jīng)濟(jì)行為都有身份認(rèn)證、簽名和防否認(rèn)等安全需求如何維 護(hù)信息安全是任何信息技術(shù)都必須解決的核心問題 密碼學(xué)作為保障和實(shí)現(xiàn)信息安全的核心技術(shù)，在各個(gè)國家都受到了普遍重視 密碼的研究與應(yīng)用已有幾千年的歷史，但作為一門科學(xué)是2 0 世紀(jì)5 0 年代才開始的 密碼學(xué)是研究密碼系統(tǒng)和通信安全的一門學(xué)科，它的應(yīng)用非常廣泛，如網(wǎng)絡(luò)上應(yīng)用 的數(shù)據(jù)加密技術(shù)、數(shù)字簽名技術(shù)、消息認(rèn)證與身份識(shí)別技術(shù)、防火墻技術(shù)以及反病 毒技術(shù)等都是基于密碼學(xué)技術(shù)來設(shè)計(jì)的互聯(lián)網(wǎng)的廣泛應(yīng)用，無線通信，秘密共享 等都大大推動(dòng)了密碼學(xué)的研究和發(fā)展大多數(shù)國家和地區(qū)都已成立了密碼學(xué)學(xué)會(huì)， 這些學(xué)會(huì)定期主辦學(xué)術(shù)會(huì)議進(jìn)行學(xué)術(shù)交流，也促進(jìn)了密碼學(xué)的研究與應(yīng)用國內(nèi)外 已出版了大量有關(guān)密碼學(xué)的書籍和理論研究論文，人們對密碼學(xué)的研究和發(fā)展越 來越關(guān)注無論是政府，企業(yè)，還是個(gè)人，都開始有意識(shí)的使用密碼技術(shù)來保密信 息資料密碼學(xué)的研究與應(yīng)用可謂日新月異 密碼分為私鑰密碼( 又稱為對稱密碼) 和公鑰密碼，其中私鑰密碼又分為序列密 碼和分組密碼，具體的概念定義請參見文【1 ，2 】它們各有特點(diǎn)，從設(shè)計(jì)原理到安 全性機(jī)制都有很大差異公鑰密碼是一個(gè)單向陷門函數(shù)，其主要原理是計(jì)算的單 向可行性自從1 9 7 6 年d i f f e 和h e l l m a n 提出公鑰密碼的觀點(diǎn)之后，大量的公鑰密碼 被陸續(xù)提出來，如r s a 公鑰密碼、m e r k e - h e l l m a n 背包公鑰密碼、m c e l i e c e 公鑰密 碼、e 1 g a m a l 公鑰密碼和橢圓曲線( e c ) 公鑰密碼等，所有這些公鑰密碼的安全性都 依賴于數(shù)學(xué)問題的難解性序列密碼是一個(gè)偽隨機(jī)序列發(fā)生器，它具有生成簡潔、 偽隨機(jī)性好等優(yōu)點(diǎn)分組密碼是一個(gè)偽隨機(jī)置換，它具有快速、易標(biāo)準(zhǔn)化、偽隨機(jī)性 好等優(yōu)點(diǎn)分組密碼有四個(gè)著名的算法標(biāo)準(zhǔn)：美國i b m 公司研究的“d e s ”；來學(xué)嘉 教授設(shè)計(jì)的“i d e a ；j a m e s l m a s s e y 設(shè)計(jì)的“s a f e r ；j o a nd a e m e n 和v i n c e n t r i j m e n 共同設(shè)計(jì)的“r i j n d a e l 私鑰密碼體制的安全性基礎(chǔ)是偽隨機(jī)性另外， 低差分一致件函數(shù)的研究 私鑰密碼與公鑰密碼的應(yīng)用領(lǐng)域也有很大的不同序列密碼體制以簡捷，快速的生 成算法，使其成為新一代移動(dòng)通信的主流加密算法；分組密碼體制也具有簡捷，快 速的特點(diǎn)，并且容易標(biāo)準(zhǔn)化，使其成為軟硬件加密標(biāo)準(zhǔn)的主流而公鑰密碼體制的 運(yùn)行速度則慢得多，占用空間也大得多，一般用于數(shù)字簽名、電子商務(wù)等計(jì)算資源 相對寬松的領(lǐng)域 伴隨著現(xiàn)代密碼技術(shù)的發(fā)展，密碼函數(shù)的設(shè)計(jì)與分析從來都是研究的熱點(diǎn)眾 所周知，現(xiàn)行的分組密碼分析方法除了窮盡搜索之外最常用的就是線性分析和差 分分析相應(yīng)地，一個(gè)安全的分組密碼體制必須具有抗線性攻擊和抗差分攻擊的性 能我們知道s 盒是分組密碼中最重要的加密部件，如何設(shè)計(jì)s 盒的構(gòu)造函數(shù)來有效 的抵抗線性攻擊和差分攻擊就成為人們研究的熱點(diǎn)1 9 9 4 年n y b e r g 在文 3 】中首次 提出了差分一致性函數(shù)的定義： 定義1 1 令，( z ) 表示函數(shù)f ：_ 島，n ( a ，6 ) 表示在z 昂n 中所有滿足方 程f ( x + 口) 一f ( x ) = 6 的解的數(shù)目，其中a ，b 昂n ( a ，6 ) 的最大值，定義為，= m a x n ( a ，b ) l a ，b 昂n ，a o ) 若，= k ，則稱函數(shù)，( z ) 為差分七一致函數(shù) 在分組密碼( 如d e s ) 中，差分密碼分析和線性密碼分析就是利用構(gòu)造s 盒的函 數(shù)的一致性缺點(diǎn)進(jìn)行攻擊所以，在密碼學(xué)應(yīng)用中，使用的函數(shù)f ( x ) l 箏j a ，值越小越 好構(gòu)造和設(shè)計(jì)低差分一致性函數(shù)不可避免地成為研究的熱點(diǎn)和重點(diǎn)。 低差分一致性函數(shù)通常是指定義1 1 中滿足a ，4 的函數(shù)，其中根據(jù)，值又 可具體地分為幾類函數(shù)，值等于1 時(shí)函數(shù)稱為平面函數(shù)或者完全非線性( p e r f e c t n o n l i n e a r 即p n ) 函數(shù)在這種情況下，( z + o ) 一，( z ) 對任意的n 瞄= 昂n o ) 而 言是一個(gè)置換多項(xiàng)式完全非線性函數(shù)在有限幾何以及差集的構(gòu)造上有著廣泛的應(yīng) 用它可用來構(gòu)造一個(gè)擁有可遞性群的投影平面，相關(guān)的幾何構(gòu)造是基于用來構(gòu)造 所謂的超橢圓的毋型冪函數(shù)完全非線性d e m b o w s k i - o s t r o m 多項(xiàng)式函數(shù)還可用來 定義預(yù)半域和半域有關(guān)完全非線性函數(shù)的更多研究與應(yīng)用請參見文 4 1 0 1 a f 值 等于2 時(shí)函數(shù)稱為幾乎完全非線性( a h n o s tp e r f e c tn o n l i n e a r 即a p n ) 函數(shù)a p n 函 數(shù)的定義和幾乎本原( a l m o s tb e n t 即a b ) 函數(shù)的定義是密切相關(guān)的【1 1 】a b 函數(shù)只 存在于f 2 。m 為奇數(shù)) 中，且擁有最佳的抵抗線性密碼分析性能1 1 2 ，1 s 1 任意的a b 函 數(shù)都是a p n 函數(shù)，而且當(dāng)n 為奇數(shù)時(shí)，任意的二次函數(shù)為a p n 函數(shù)當(dāng)且僅當(dāng)它是a b 函數(shù)【1 4 1 在特征為2 的域中，因?yàn)?，p + a ) 一f ( x ) = b = ，( 扛+ 口) + a ) 一f ( x + 口) ，。 所以，= 2 是最小的可能值因此，幾乎完全非線性函數(shù)是構(gòu)造s 盒函數(shù)的最佳 選擇幾乎完全非線性函數(shù)也可用于其它無線通信領(lǐng)域如幾乎完全非線性函數(shù) 對應(yīng)長度為2 n 一1 的2 n 維線性碼的最小距離剛好為5 ，所以可以用它來構(gòu)造和研 究線性碼在奇特征域中，越來越多的幾乎完全非線性函數(shù)也被發(fā)現(xiàn)和應(yīng)用現(xiàn) 在，完全非線性函數(shù)和幾乎完全非線性函數(shù)因其優(yōu)良的差分性質(zhì)被廣泛應(yīng)用到相 關(guān)的其它領(lǐng)域如它們可用來構(gòu)造差集，幾乎差集和扭曲映射等( 見文 1 5 , - , , 2 5 1 ) 另 博士學(xué)位論文 一方面，它們的w a l s h 譜和布爾函數(shù)都有很好的性質(zhì)相關(guān)的研究見文 2 6 , - , - , 3 0 與a b 函數(shù)相對應(yīng)地有b e n t 函數(shù)，它是r o t h a u s 在1 9 7 6 年在文【3 1 】中提出的w a l s h 譜 為0 ，z t ：2 詈的易。上的布爾函數(shù)稱為b e n t 函數(shù)，b e n t 函數(shù)是與所有的仿射函數(shù)中具有 最大距離的函數(shù)，它只在n 為偶數(shù)時(shí)存在，相關(guān)地研究見文 3 2 4 2 由于考慮到其 它的密碼學(xué)性質(zhì)，如最大非線性，相關(guān)免疫性等，低差分一致性為3 或4 的函數(shù)也被 應(yīng)用到密碼體制中雖然它們差分一致性不及完全非線性函數(shù)和幾乎完全非線性 函數(shù)，但是它們的置換屬性等其它的優(yōu)秀特性也使其有很大的應(yīng)用價(jià)值如當(dāng)禮為 偶數(shù)時(shí)，易。中的逆函數(shù)2 ：2 - - 2 是一個(gè)差分4 一致置換函數(shù)，其非線性度為2 儼1 2 號(hào) 當(dāng)n = 8 時(shí)，該函數(shù)被選作高級(jí)加密標(biāo)準(zhǔn)( a e s ) 的s 盒函數(shù)【4 3 】 綜上所述，低差分一致性函數(shù)具有較高的應(yīng)用價(jià)值，而構(gòu)造和分析低差分一致 性函數(shù)是密碼工作者的重要任務(wù)之一本文致力于解決一些低差分一致性函數(shù)中 存在的問題，分析和構(gòu)造了幾類低差分一致性函數(shù)本文的研究結(jié)果豐富了低差分 一致性函數(shù)的內(nèi)容，給密碼設(shè)計(jì)者提供了更多的選擇，同時(shí)我們的構(gòu)造方法也可用 于對低差分一致性函數(shù)的進(jìn)一步研究 1 2 低差分一致性函數(shù)研究進(jìn)展 大多數(shù)針對對稱密碼算法的攻擊是利用系統(tǒng)中的布爾函數(shù)的某些屬性來進(jìn)行 的在迭代塊密碼中，最主要的密碼分析方法是線性密碼分析和差分密碼分析 而s 盒作為代換置換的主要執(zhí)行部分不可避免地成為密碼設(shè)計(jì)和密碼分析的重 點(diǎn)b i h 鋤和s h 8 m i r 在文【4 4 1 中討論了s 盒的差分分析方法以及怎樣保證s 盒的抗差 分分析能力自從n y b e r g a ，4 5 1 給出了差分一致性函數(shù)的定義后，大量的低差分一致 性函數(shù)特別是幾乎完全非線性函數(shù)被構(gòu)造和研究 人們最先考慮的是冪函數(shù)f ( x ) = 一的差分一致性在密碼應(yīng)用中，幾乎完全 非線性函數(shù)在塊密碼和流密碼中都有廣泛應(yīng)用為了有效的在硬件和軟件上執(zhí)行， 人們更多的考慮特征為2 的域( 即偶特征域) 上的幾乎完全非線性函數(shù)已發(fā)現(xiàn)的偶 特征域上的幾乎完全非線性冪函數(shù)如下： n y b e r g a l ，b e t h 和d i n g 4 6 1 i l t i t 韭 了d = 妒一2 ，禮為奇數(shù)時(shí)一為易。中的a p n 函 數(shù)( k l o o s t e r m a n 情況) ； n y b e r g 3 1 ，b 矗h 和d i n g 考慮了g o l d 指數(shù)而得出d = 2 k + 1 ，( n ，k ：；= l 時(shí)一為 易n 中的a p n i 函數(shù)( g o l d 情況) ； j a n w 灌】w i 婦由k a s a 蚵指數(shù)【4 9 】而得出d = 2 2 k - 2 毛+ 1 ，( 佗，k ) = 1 時(shí)為足n 中的a p n i 函數(shù)( k a s m i 情況) ； d o b b e r t i n 在文【5 0 】中證明了w _ e l c h 猜想【5 1 】而得出d = 2 七+ 3 ，n = 2 k + l l i 寸z d 為易 孓 低差分一致性函數(shù)的研究 中的a p n 函數(shù)( w e l c h 情況) ； d o b b e r t i n 在文【5 2 】中證明了n i h o 猜劃5 1 】而得出d = 2 2 七+ 2 七一1 ，4 k + 1 三0 r o o dn 時(shí)為島n 中的a p n 函數(shù)( n i h o 情況) ； d o b b e r t i n 在文 5 3 】中給出- j d = 2 4 七+ 2 3 七+ 2 2 七+ 2 七一1 ，釓= 5 七時(shí)為易n 中 的a p n 函數(shù)( d o b b e r t i n 情況) 到目前為止，在偶特征域中只發(fā)現(xiàn)上述六類a p n 冪函數(shù)( 在等價(jià)條件下) h e l l e - s e t h 等用計(jì)算機(jī)搜索證明了當(dāng)釓1 1 時(shí)，足。中只存在上述六類a p n 冪函數(shù)酬。人 們猜想尼。中沒有其它的a p n 冪函數(shù)( 在等價(jià)條件下) ，但到目前為止還無法證明它 在奇特征域中，新的a p n 函數(shù)陸續(xù)被構(gòu)造h e u e s e t h 和s a n d b e r g 5 5 】用計(jì)算機(jī)進(jìn)行了 大量搜索并找到了兩類單項(xiàng)式a p n 冪函數(shù)：( 1 ) b 。中的函數(shù)f ( x ) = z 3 ，其中p 3 ； ( 2 ) d = 衛(wèi)蘭21 時(shí)，b n 中的函數(shù)f ( x ) = 一，其中p 三3 ，7m o d2 0 ，i f , 7 ，礦 2 7 且死為奇數(shù)除了己知的a p n 函數(shù)外，他們還發(fā)現(xiàn)了一些新的低差分一致性函數(shù) h e l l e s e t h ，r o n g 和s a n d b e r g 酬用計(jì)算機(jī)搜索到部分特征為奇素?cái)?shù)域上的a p n 函數(shù)， 并成功的構(gòu)造幾類a p n 冪函數(shù)來解釋它們在易中，已被解釋的情況為：( 1 ) d = 學(xué)+ 掣時(shí)一為a p n 函數(shù)，其中礦三3r o o d8 ；( 2 ) d = 型坐4 時(shí) 一- - 為a p n 函數(shù)， 其中p n 蘭7m o d8 ；( 3 ) d = 壟時(shí)一為a p n 函數(shù)，其中礦三2r o o d3 ；( 4 ) d = 礦一3 1 j 寸x d 為a p n 函數(shù)，其中p = 3 ，n 1 為奇數(shù)但仍有幾種情況不能解釋( 見 表2 1 ) ，解釋這幾種公開情況就成了人們研究的方向之一d o b b e r t i n l 等解釋了 其中的兩種情況而得出兩類新的a p n 冪函數(shù)( 見引理2 1 2 2 ) ，并且對另一種情況給 出了著名的d o b b e r t i n 猜想f e l k e 5 7 】利用多變量方法構(gòu)造了一系列低差分一致性函 數(shù)，并且部分解決了d o b b e r t i n 猜想本文構(gòu)造了兩類a p n 函數(shù)，解釋了表2 1 中其 它的兩種情況并完全證明了d o b b e r t i n 猜想我們注意到：在構(gòu)造a p n 冪函數(shù)的同 時(shí)，一些低差分一致性函數(shù)也被構(gòu)造和討論構(gòu)造新的a p n 函數(shù)，一般先采用計(jì)算 機(jī)搜索一些單個(gè)的a p n 函數(shù)，然后將其推廣為一類a p n 函數(shù)并用數(shù)學(xué)方法來證明 它 盡管大量的a p n 函數(shù)被構(gòu)造和發(fā)現(xiàn)，但是一些特殊的a p n 函數(shù)仍沒有找到， 如足。中的a p n 置換函數(shù)我們知道在對稱密碼體制中，執(zhí)行的變量為偶數(shù)而 且s 盒其實(shí)就是一個(gè)代換置換網(wǎng)絡(luò)，所以b ：。中的a p n 置換函數(shù)是構(gòu)造s 盒的最佳 選擇但是，到目前為止人們還沒有找到這種函數(shù)，它是否存在是一個(gè)公開問題 h o u 在文f 5 8 ，5 9 1 中證明了在局。中，當(dāng)n = 4 或f 只哥m 時(shí)，f 不可能是a p n 置換 已經(jīng)發(fā)現(xiàn)的二元域中的a p n 多項(xiàng)式函數(shù)都是二次的，是否存在非二次的a p n 多項(xiàng) 式函數(shù)? 以及當(dāng)n 3 k 且( 3 ，k ) = i n ，是否存在毋。中的二次a p n 函數(shù)不等價(jià)于 任意的冪函數(shù)? e d e l 和p o t t 在文【6 0 】中首次提出了兩類非二次a p n 多項(xiàng)式函數(shù)并 證明其中一類a p n 函數(shù)與已知的a p n 函數(shù)不等價(jià)，利用該文的方法構(gòu)造新的非二 垂 博士學(xué)位論文 次a p n 或p n 多項(xiàng)式函數(shù)將是我們未來研究的目標(biāo)b e r g e r ，c a n t e a u t ，c h a r p i n 和 c h a p u y 在文 6 1 】中綜合討論了a p n 函數(shù)的公開問題并利用布爾函數(shù)得出a p n 函數(shù) 新的性質(zhì)總之，a p n i 垂i 數(shù)還有更多的問題等待我們?nèi)グl(fā)現(xiàn)和解決 由于完全非線性( p n ) 函數(shù)只能在奇特征域中存在，它的應(yīng)用一般限于有限幾 何最早被發(fā)現(xiàn)的三類p n 函數(shù)( 又稱為平面函數(shù)) 如下( 參考文獻(xiàn)見文【6 2 6 5 】) ： f ( x ) = x 2 在中為p n 函數(shù)，其中p 為奇素?cái)?shù)； f ( x ) = 礦。+ 1 在中為p n 函數(shù)，其中p 為奇素?cái)?shù)，佗( 死，s ) 為奇數(shù)； f ( x ) = z l o + z 6 一x 2 在瑪。中為p n 函數(shù)，其中n 等于2 或奇數(shù) p n 函數(shù)有一個(gè)有趣的性質(zhì)：若q 為一個(gè)奇素?cái)?shù)且f r 為一個(gè)p n i 函數(shù)，貝, l j f 等 價(jià)于z 2 d e m b o w s k i 和o s t r o m 6 5 1 提出一個(gè)問題：是否所有的p n 函數(shù)，( z ) 具有形 式，( z ) = 啦f 憎( d e m b o w s k i o s t r o m 多項(xiàng)式) ? c o u l t e r 和m a t t h e w s i e 治l 給出 i j 。- - 。o 一 了一類新的p n 函數(shù)：f s 。中，( z ) = z 孕，其中k 為奇數(shù)且( n ，后) ：1 這類p n 函數(shù) 否定地回答了上面的問題另外，y u a n i g l d i n g s 推廣了上面的多項(xiàng)式p n 函數(shù)而得 出一類新的多項(xiàng)式p n 函數(shù)：b 。中的函數(shù)f ( x ) = z l o 一蚴6 一牡2 2 2 ，其中讓b n ， 鉈為奇數(shù)本文由已知的a p n 多項(xiàng)式函數(shù)構(gòu)造出兩類新的p n 多項(xiàng)式函數(shù)，該p n 多 項(xiàng)式函數(shù)不等價(jià)于已知的p n 函數(shù)由于p n 函數(shù)在有限幾何以及差集的構(gòu)造上的 應(yīng)用【6 7 “倒，構(gòu)造新的p n 函數(shù)特別是p n 多項(xiàng)式函數(shù)成為人們研究的熱點(diǎn) k r i s t e n s e n 在文 7 3 】中給出了用計(jì)算機(jī)搜索形為f ( x ) = z d z + z d ：的p n 函數(shù)和 a p n 函數(shù)的結(jié)果于是一系列研究p n 多項(xiàng)式函數(shù)和a p n 多項(xiàng)式函數(shù)的工作隨之展 開由于a p n 函數(shù)的密碼學(xué)用途更廣泛，人們將研究的重點(diǎn)放在a p n 多項(xiàng)式函數(shù) 的構(gòu)造和分析上一批新的a p n 多項(xiàng)式函數(shù)被構(gòu)造和發(fā)現(xiàn)，但是我們發(fā)現(xiàn)：部分新 的a p n 函數(shù)和已提出的函數(shù)雖然形式不同，但實(shí)際上是相互等價(jià)的可是如何判定 兩個(gè)a p n 函數(shù)是等價(jià)的呢? 當(dāng)前我們評(píng)定的標(biāo)準(zhǔn)有兩種：擴(kuò)張仿射( e x t e n d e da 伍n e 即e a ) 等價(jià)和c a r l e t - c h a r p i n - z i n o v i e v ( c c z ) 等價(jià)【1 4 1 c c z 等價(jià)和碼等價(jià)是相互對 應(yīng)的，我們可以利用編碼理論中的方法和工具來確定函數(shù)是否c c z 等價(jià)【7 如洲構(gòu) 造出一類新的a p n 函數(shù)后，討論它與已知的函數(shù)的不等價(jià)性也是一項(xiàng)重要的工作 目前a p n 多項(xiàng)式函數(shù)研究的主要成果如下： e d e l ，k y u r e g 螄l 和p o t t 在文【8 1 】中首先在r ，。中構(gòu)造出一類a p n 雙項(xiàng)式函數(shù) ，p ) = 礦+ t ，其中玨為巧。中特定的元素同時(shí)，另一個(gè)a p n 雙項(xiàng)式函數(shù) b ，。中，( z ) = z 3 + u t 5 2 8 ( u 為磁：中特定的元素) 也被提出； j e d u d c a 在文 8 2 】中給出了毋n 中的無限類a p n 單項(xiàng)式函數(shù)； 一5 低差分一致性函數(shù)的研究 b u d a g h y a n ，c a r l e t $ f l p o t t 在文 2 6 1 中給出了易n 中新的a p n 函數(shù)和a b 函數(shù)，并 且證明了它們e a 不等價(jià)于任意的冪函數(shù)和仿射函數(shù)之和： b u d a g h y a n 等在文陽，8 4 】中給出了易。中的一類二次a p n 雙項(xiàng)式函數(shù)，其中他為 3 的倍數(shù)，并證明了函數(shù)不等價(jià)于冪函數(shù)； b u d a g h y a n 等在文i s 4 ，8 5 】中給出了f 2 。中的一類二次a p n 雙項(xiàng)式函數(shù)，其中n 為 4 的倍數(shù)，并討論了函數(shù)的不等價(jià)特性； b u d a g h y a n 在文 8 6 】中給出了利用e a 等價(jià)和逆置換構(gòu)造了一類多項(xiàng)式a p n 函 數(shù)，該函數(shù)e a 不等價(jià)于冪函數(shù)； b u d a g h y a n 等在文 8 7 】中給出了一種由已知a p n 函數(shù)構(gòu)造a p n 函數(shù)的方法，并 構(gòu)造出一類a p n 函數(shù)他們討論了該a p n 函數(shù)的c c z 等價(jià)特性和構(gòu)造的可行 性，給以后的研究工作提供了方法和工具； b u d a g h y a n 弄f l c a r l e t 在文 8 8 】中給出了易n 中的幾類二次a p n 三項(xiàng)式和六項(xiàng)式函 數(shù)，。其中凡為偶數(shù)，并簡要討論了函數(shù)的相關(guān)結(jié)構(gòu)和不等價(jià)特性； b r a c k e n ，b y n e ，m a r k i n 和m c g u i r e i t 4 在扎為偶數(shù)和鉈為3 的倍數(shù)時(shí)分別構(gòu)造出易 中一類多項(xiàng)式a p n 函數(shù)，并討論了其中該函數(shù)的c c z 等價(jià)特性和編碼理論在 文 8 9 】中他們將文 7 4 】中的函數(shù)加以推廣，得到一類二次四項(xiàng)a p n 函數(shù)并簡要 討論了其和d i l l o n 多項(xiàng)式間的等價(jià)關(guān)系： n e s s 承i h e l l e s e t h 在文 9 1 1 中給i 出t f 3 n 中的一類a p n 雙項(xiàng)式函數(shù)f ( x ) = 一“一2 + 札z 華，其中u 為瑪。中特定的元素，他們的結(jié)果給a p n 函數(shù)的研究開辟了新 的領(lǐng)域z e n g ，h u ，y a n g 和j i a n g 在文【9 2 】中證明了該類a p n i 函數(shù)c c z 不等價(jià)于 已知的a p n 函數(shù)； e d e l _ j g l p o t t 在文 刪中給出了而中的一類非二次a p n 多項(xiàng)式函數(shù)f ( x ) = 護(hù)+ t 正1 7 ( z 1 7 + z 1 8 + z 加+ 護(hù)4 ) + t 1 8 2 9 + t 上3 6 2 1 8 + 讓9 z 笳+ z 2 1 + z 4 2 + t r ( u 2 7 x + u 5 2 護(hù)+ 鏟z 5 + t 1 9 2 7 + 1 2 2 8 x 1 1 + t 正2 2 1 3 ) ，其中毋是由。6 + x 4 + 護(hù)- i - z + 1 f 2 z t 糙 的分裂域，u 為上式在中的根該函數(shù)c c z 不等價(jià)于任意扭曲函數(shù) 在上述研究成果獲得的同時(shí)，大量的a p n 函數(shù)研究的相關(guān)工作也得到了深入的研 究f 蜘卅如c h e o n 和i 艘在文【9 8 】中分析了a p n 冪函數(shù)的抗代數(shù)攻擊性能，b y r n e 和 m c g 山r e 在文【9 9 】中證明了一類a p n 函數(shù)不可能是無限類等等 低差分一致性函數(shù)，特別是a p n 函數(shù)及p n i 愛數(shù)在相關(guān)領(lǐng)域中的應(yīng)用也得到了 廣泛的研究b r a c k e n ，b y r n e ，m a u r l 【i n 和m c g l l i r e 在文【1 0 0 ，1 0 1 】中研究了a p n 函數(shù) 博士學(xué)位論文 f 拘w a l s h 譜以及非線性特性y u a n 和d i n g 在文【8 】中利用新的p n 函數(shù)來構(gòu)造h a d 扣 m a r d 差集，從而否定了長期存在的h a d a m a r d 猜想k y u r e g h y a n 和b i e r b r a u e r 在文 獻(xiàn) 1 0 2 1 0 5 】中討論a p n 函數(shù)與扭曲映射之間的關(guān)系，更多的研究見文【1 0 7 一1 1 6 - 1 3 主要成果和組織結(jié)構(gòu) 由于低差分一致性函數(shù)在密碼體制設(shè)計(jì)中有著舉足輕重的地位，構(gòu)造和設(shè)計(jì) 具有良好密碼學(xué)性質(zhì)的低差分一致性函數(shù)是當(dāng)前應(yīng)用密碼學(xué)中的研究熱點(diǎn)之一本 文在已知的a p n 函數(shù)及構(gòu)造方法的基礎(chǔ)上，利用二次特征，d i c k s o n 多項(xiàng)式，冪函數(shù) 以及仿射多項(xiàng)式等工具，構(gòu)造并分析了幾類具有低差分一致性的函數(shù)本文的主要 成果及章節(jié)安排如下： 在第二章中，我們首先以二次特征，d i c k s o n 多項(xiàng)式為工具構(gòu)造并證明了一類 a p n 函數(shù)，新的a p n 函數(shù)解釋了h e l l e s e t h 提出的一種公開情況然后我們利用同 樣的方法證明了d o b b e r t i n 猜想并提出另一類新的a p n 函數(shù)，該類a p n 函數(shù)解釋 了h e l l e s e t h 提出的另一種公開情況另外我們討論了剩下的一種公開情況，給出一 類函數(shù)的差分一致性界最后我們將前面提出的兩類a p n 函數(shù)加以推廣，得出特 定形式下冪函數(shù)的差分一致屬性我們的證明方法是將已往的傳統(tǒng)方法中創(chuàng)新性 的引入d i c k s o n 多項(xiàng)式來討論求解，這種新的方法使得方程的求解變得簡單可行 在第三章中，我們分別考慮了偶特征域和奇特征域中的多項(xiàng)式a p n 函數(shù)首 先，我們討論了偶特征域中已知的幾種a p n 多項(xiàng)式函數(shù)的等價(jià)性質(zhì)，接著給出了一 類新的a p n 函數(shù)并證明了它的b e n t 屬性該a p n 函數(shù)c c z 不等價(jià)于d o b b e r t i n 函 數(shù)且在特定條件下不等價(jià)于已知的函數(shù)其次，我們將特征為3 的域中一類己知 的a p n 函數(shù)推廣到奇特征域中，得到定義范圍更廣的a p n 函數(shù)，新的a p n 函數(shù)包 含已知的a p n 函數(shù)為特例最后，我們計(jì)算了一大類a p n 函數(shù)的w a l s h 譜，我們的 結(jié)果回答了文【l o o 】中提出的一個(gè)公開問題 在第四章中，我們將已知的a p n 函數(shù)推廣到奇特征域中，加上特定的條件而 得出幾類p n 函數(shù)我們證明了其中兩類p n 函數(shù)c c z 不等價(jià)于所有已知的p n 函數(shù)， 由此給出了兩類半域在特定的條件下，我們構(gòu)造的半域也與已知的半域不合痕 其中二項(xiàng)式p n 函數(shù)主要用特殊的線性多項(xiàng)式為工具來證明，我們的方法可以對已 知的a p n 函數(shù)給出一個(gè)不同的證明，而多項(xiàng)式p n 函數(shù)則用第三章中所用的方法來 證明我們的結(jié)果給出了構(gòu)造p n 函數(shù)的新方法，對現(xiàn)有的p n 函數(shù)是一個(gè)很好的補(bǔ) 充最后，我們討論了特定條件下d i l l o n 多項(xiàng)式的差分一致性，得出了一些特殊的 低差分一致性函數(shù) 在第五章中，我們結(jié)合前面的工具和方法，給出了一些低差分一致性函數(shù)和 構(gòu)造方法我們注意到除了e d e l 和p o t t 最近發(fā)現(xiàn)的非二次a p n 函數(shù)外，其它已知 的a p n 多項(xiàng)式函數(shù)都是二次的，而且在b h 中還沒有發(fā)現(xiàn)a p n 置換函數(shù)我們構(gòu)造 低差分一致性函數(shù)的研究 的低差分一致性函數(shù)已不限于二次，而且具有置換特性，從而給構(gòu)造和設(shè)計(jì)s 盒提 供了更多的方法在第3 節(jié)中，我們引入了幾乎低差分一致性概念并證明了幾類幾 乎低差分一致性函數(shù) 最后，我們對論文進(jìn)行了總結(jié)，并討論了今后所要做的工作 1 4 本文所用的記號(hào) 易 墨 c f ( p n ) l m a x ( ，) g c