（数学专业论文）有限域上高度非线性函数的性质与构造.pdf

国防科学技术大学研究牛院硕十学位论文 摘要 高度非线性函数在密码学、序列设计以及编码理论有着非常广泛的应用本文首 先对有限域上完全非线性函数、几乎完全非线性函数和几乎b e n t 函数的已有工作进行 了分析和整理，在此基础上计算出了类三项式形式的几乎完全非线性函数的非线性 度，构造了两类d e m b o w s b o s t r o m 型完全非线性函数，并分别分析了它们与已有函数的 等价关系主要成果有： ( 1 ) 求出了一类三项式形式的几乎完全非线性函数的扩展w a l s h 谱，从而确定了它 的非线性度进一步利用该类函数，构造了一类佗维二元线性码，并确定了该线性码的 最小距离和特征集，进一步还确定了该线性码的扩展码的相关性质； ( 2 ) 在f 口。t 上构造了一类完全非线性函数，并且证明它与已知的完全非线性函数是 不等价的； ( 3 ) 在f 口z * 上构造了一类完全非线性函数，实验数据表明，在七2 ，p 1 1 时， 该函数类是e a 等价于z 2 的进一步证明它的一个子类是与z 2 等价的，并且该子类含 有逆生幽个元素 关键词：差分均匀度；非线性度：完全非线性函数；几乎完全非线性函数；扩展w a l s h 谱；c a r l e t - c h a r p i n z i n o v i e v 等价；扩展仿射等价 第1 页 国防科学技术大学研究牛院硕士学位论文 a b s t r a c t f u n c t i o n sw i t hh i g hn o n l i n e a r i t yh a v ei m p o r t a n ta p p l i c a t i o n si nc r y p t o g r a p h y ，s e q u e n c e sa n d c o d i n gt h e o r y i nt h i st h e s i s ，i ti sf i r s t l yp r e s e n t e dt h a tt h es u m m a r yo fa l li m p o r t a n tk n o w nr e s u l t s a b o u tp e r f e c tn o n l i n e a rf u n c t i o n s ，a l m o s tp e r f e c tn o n l i n e a rf u n c t i o n sa n da l m o s tb e n tf u n c t i o n so v e r f i n i t ef i e l d s t h e n ，t h en o n l i n e a r i t yo faf a m i l yo ft r i n o m i a la p nf u n c t i o n si sg i v e n f i n a l l y , t h e c o n s t r u c t i o n so ft w of a m i l yo fd e m b o w s k i o s t r o mt y p ep e r f e c tn o n l i n e a rf u n c t i o n sa l ep r e s e n t e d m e a n w h i l e ，t h ee q u i v a l e n c e sb e t w e e nt h e ma n dt h ek n o w no n e sa r ea n a l y z e d ，r e s p e c t i v e l y t h em a i n c o n t r i b u t e sa n df r u i t so ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) t h ee x t e n dw a l s hs p e c t r u mo faf a m i l yo ft r i n o m i a la p n f u n c t i o n sfi sc a l c u l a t e d ，a n dt h e n o n l i n e a r i t yo ffi sd e t e r m i n e d m e a n w h i l e 。ab i n a r yl i n e a rc o d ec sa n di t se x t e n d e dc o d ecla r e c o n s t r u c t e df r o mf ，a n dt h em i n i m u md i s t a n c e ，d i m e n s i o na n dc h a r a c t e r i s t i cs e to fc l a n dc l a r e p r e s e n t e d ，r e s p e c t i v e l y ； ( 2 ) an e wf a m i l yo fd e m b o w s k i o s t r o mt y p ep e r f e c tn o n l i n e a rf u n c t i o n si sp r e s e n t e do v e rf 口2 k ， a n di ti sp r o v e dt ob ei n e q u i v a l e n tt oa n yk n o w no n e s ； ( 3 ) af a m i l yo fd e m b o w s k i o s t r o mt y p ep e r f e c tn o n l i n e a rf u n c t i o n si sp r e s e n t e do v e r 2 k c o m p u t e rp r o g r a ms h o w st h a tt h i sf u n c t i o ni se q u i v a l e n tt oz 2 ，f o rk 2 ，a n dp r i m ep 1 1 f u r t h e r m o r e t h ep r o o fo ft h ee q u i v a l e n c eb e t w e e no n eo fi t ss u b f a m i l ya n d 护i sg i v e n a n di ti s p r o v e dt h a tt h i ss u b f a m i l yc o n t a i n s ( p k + 1 ) 2 ( p k - - 3 ) e l e m e n t s k e yw o r d s ：d i f f e r e n t i a lu n i f o r m i t y ；n o n l i n e a r i t y ；p e r f e c tn o n l i n e a rf u n c t i o n ；a l m o s tp e r f e c t n o n l i n e a rf u n c t i o n ；e x t e n dw a l s hs p e c t r u m ；c a d e t - c h a r p i n z i n o v i e ve q u i v a l e n c e ；e x t e n d a f f i n ee q u i v a l e n c e 第贞 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技 术大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：有限域上高度非线性函数的性质与构造 学位论文作者签名： j 氢! 丕日期：7 c 7 0 9 年f f 月2 se t 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人 授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印 件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：有限域上高度非线性函数的性质与构造 学位论文作者签名：图! ! 叁 日期：工口。扩年f1 月苟日 作者指导老师签名：奎垃 日期：p r 年1 1 月2 ，日 国防科学技术大学研究乍院硕士学位论文 第一章绪论 编码和密码技术应用于军事和外交通信的历史非常久远，但是，除了少数爱好者 的业余研究之外，绝大多数研究都是由官方组织秘密进行的现代编码理论的开山之 作是c s h a n n o n 于1 9 4 8 年发表的通信的数学原理【1 1 一文而s h a n n o n 于1 9 4 9 年发表的 另一篇文章一一保密系统的通信理论f 2 1 ，标志着现代密码学的开端 与编码理论的蓬勃发展不同，在s h a n n o n 文章发表大约3 0 年之后，密码学的公开研 究才逐步开始，这主要与以美国为代表的政府管制有关1 9 7 6 年，wd i f f i e 和m h e l l m a n 发表了密码学的新方向一文【3 】，提出了适应网络上保密通信的公钥密码思想， 开辟了公开秘钥密码学的新领域受他们思想的启迪，各种公钥密码体制被相继提出， 特别是1 9 7 8 年r s a 公钥密码体制的出现，成为公钥密码的杰出代表，在密码学史上是 一个里程碑1 9 7 7 年，美国国家标准局公布实施了美国的数据加密标准( d a t ae n c r y p t i o n s t a n d a r d ，简写为d e s ) ，公开了它的加密算法，并批准用于政府的机密单位以及商业上 的保密通信同时，各国政府纷纷解除了密码学公开研究的限制，现代密码学的研究 进入了蓬勃发展的时代 编码理论与密码理论，作为两个独立的学科，虽然有着不同的发展轨迹和应用背 景，但是隐藏在它们身后的数学理论和数学工具却有着惊人的一致性和互通性而它 们所依赖的这些数学理论中，不仅包含了组合、初等数论、线性代数这些基本的数学 工具，还包含了有限几何、代数数论、代数几何、椭圆曲线、表示理论等近代和现代数 学理论因此，有很多学者在编码理论、密码学和纯数学三个方面都做出了非常杰出 的贡献由于编码理论发展较早，成果丰富，因此有很多编码中的思想、方法被应用在 了密码学中同时，密码学中一些问题的解决，也促进了编码学中相对应的重要问题 的解决下面介绍的高度非线性函数，就是一个非常典型的例子 1 1 高度非线性函数的研究现状及发展趋势 高度非线性函数在密码学1 4 1 1 5 1 1 6 1 1 7 1 、编码理论1 5 1 8 1 9 1 1 0 以及序列1 1 1 2 1 有着非常重 要的应用在密码设计中，为了达到混淆的目的，必须使用高度非线性函数例如：它 们被用来构造序列密码中的滤波函数、分组密码中的s 盒、h a s h 函数中非线性组件在 编码理论中，可以用高度非线性函数构造好的纠错码在序列设计方面，可以通过高 度非线性函数构造具有良好相关性质的序列，用于c d m a 通信系统和扩频通信系统 在过去的2 0 多年中，关于非线性函数的研究主要集中在布尔函数以及向量值布尔 函数上特别是对于布尔函数，有很丰富的结果i1 3 1 1 1 4 1 第l 贞 囝防科学技术大学研究牛院硕士学位论文 对于从有限域f 口。到其自身的映射，根据差分密码攻击【1 5 1 和线性密码攻击f 7 1 ，分 别有两种不同的非线性度量，即：差分均匀度与非线性度而在这两个非线性度量下 的主要研究对象，就是所谓的完全非线性函数( p n 函数) 、几乎完全非线性函数( a p n 函 数) 和几乎b e n t 函数( a b 函数) 但是，这些函数的构造问题是十分困难，早在上世纪7 0 年 代，w e l c h 、k a s a m i 和n i h o 等人就猜想了3 类a b 函数( 同时也是a p n 函数) ，而直到1 9 9 9 年， 才被h d o b b e r t i n ，a c a n t e a u t 和h h o l l m a n n 等人证明1 1 6 1 1 7 1 1 8 1 1 9 2 0 1 在此之后，幂函数 形式的a p n 、a b 函数研究的进展一直非常缓慢与此同时，多项式形式的a p n 函数被 人们逐步发现而这其中的第一个是由y e d e l ，g k y u r e g h y a n 和a p o t t 三人，存2 0 0 6 年， 通过计算机搜索而提出的t o 上的一个二项式【2 1 1 而到目前为止，人们所构造的a p n 多 项式函数族都是二次型的，a p o t t 等学者将视线转移到了构造非二次型的多项式函数 上，并且在不久之前给出了一些计算机搜索的例子【2 2 1 ，但没有给出新的a p n 函数族 对于一般的交换群到交换群之间的高度非线性映射的研究，则更加困难，因此结果 也非常有限c c a r l e t 并1 c d i n g 讨论了在一般a b e l 群上完全非线性函数的原像分布的问 题【2 3 1 他们给出了关于原像分布的三个一般的公式，并在此基础上讨论了当m = 3 和4 时 的原像分布情况，得到了一些关于原像分布的不定方程组c l i ，q l i 和s l i n g 等进一 步确定了这些不定方程的解a p o t t 则利用相对差集( r e l a t i v ed i f f e r e n c es e t ) 等组合设计的 语言【2 4 】，对几乎所有类型的高度非线性映射，做出了统一的表示，并进行了深刻的总 结值得一提的是，k h o r a d a m 还讨论了非交换群之间的高度非线性映射1 2 5 1 ，而这类 问题当然更加深刻和复杂 1 2 论文的主要结果和安排 本文主要以有限域上多项式理论与特征和理论为工具，研究了有限域上完全非线 性函数( p n 函数) 与几乎完全非线性函数( a p n 函数) 的性质和构造 本文的主要j i ：作如下： ( 1 ) 文献【2 6 】中提出了一个f 秘上的三项式a p n 函j 数，本文证明了该函数的w a i s h 谱 是5 谱值的，这与吒：t 一 - g o l d 型函数z 2 + 1 的谱值，。致，其中( t ，2 k ) = 1 从而确定了该类 函数的非线性度进一步，利用该函数，构造了二元线性码，并分别确定了它和它的扩 展码的最小距离和特征集； ( 2 ) 在特征为奇数的有限域上，构造了一类新的d e m b o w s k i o s t r o m 型的完全非线性 函数并且证明，在一定的条件下，它是与已知的p n 函数都是不等价的； ( 3 ) 在特征为奇数的有限域上，构造了一类d e m b o w s k i o s t r o m 型的完全非线性函数 通过计算机程序，得到在k 2 ，p 1 1 时，第二类函数f ( x ) k 。* m 是e a 等价于z 2 的 第2 页 国防科学技术大学研究牛院硕士学位论文 进一步，讨论了第二类函数的一个子类，证明了其与x 2 的e a 等价性，并给出了该子类 共含有芷兰掣个函数的证明 本文的安排如下： 第二章介绍与一些本文有关的基本概念和预备知识，主要包括有限域上的线性化 多项式，仿射多项式，迹函数和置换多项式的定义及其性质；c c z 等价与e a 等价的定 义，以及它们之间的关系；非线性度的定义，以及几乎b e n t 函数；差分均匀度，完全非 线性函数与几乎完全非线性函数的定义；现在已知的特征为奇数的有限域上的完全非 线性函数和几乎完全非线性函数，特征为偶数的有限域上的几乎完全非线性函数和几 乎b e n t 函数 第三章针对文献 2 6 1 中提出的一个f f ，2 。上的三项式a p n 函数，证明了该函数的扩 , l 琵w a l s h 谱值与f 口。- 上g o l d 型函数z 2 。+ 1 的谱值一致，都为5 谱值的，其中( t2 k ) = 1 进而 确定了该类函数的非线性度同时，得到该类函数不可能通过计算其扩展w a l s h 谱值， 来证明其与其它函数c c z 不等价进一步，利用该函数，构造了二元线性码，证明其最 小距离d = 5 ，同时求出了它的特征集 第四章在特征为奇数的有限域上，构造了两类d e m b o w s k i o s t r o m 型的完全非线性 函数进而证明，在一定的条件下，第一类函数与已知的p n 函数都是不等价的，同 时m a g m a1 程序测试结果显示在k 2 ，素数p 1 1 时，f 。z t 上第二类函数，( z ) 是e a 等价 于z 2 的进一步，讨论了第二类函数的一个子类，证明了其与z 2 的e a 等价性，并给出 了该子类的计数公式 第五章对全文的工作进行了总结，并对下一步的研究工作和方法进行了探讨 m a g m a s - - 款由悉尼人学开发的，用于代数计算的专业编f l l j 软件 第3 页 国防科学技术大学研究乍院硕士学位论文 第二章基本概念和预备知识 2 1 有限域上的若干类多项式函数 有限域上的任何一个映射，都可以通过其上的多项式将其表达出来【2 7 】，因此通过 多项式来研究、分析和构造有限域上的映射是非常重要的方法本节将介绍有限域上 几类重要多项式函数，及其相关性质，它们将在后面的章节中出现 定义2 1 1 2 7 1 形如 其中n i f 口m ( i = 0 ，1 ，礼) 的多项式称为f g m 上的线性化多项式，也称为q 一多项式 可以证明，f g m 上的线性化多项式相当于f 口上向量空间的一个线性算子f 2 7 1 因此 由线性化多项式所诱导的f 口m 的函数，就是一个线性函数 设线性化多项式l ( x ) f q m ，f 是f 口m 【z 】的一个有限扩域，扩张次数为8 进而f 可 以视为上的一个s 维向量空间设 1 ，风) 是f 在f g 上的一组基，由于三是砸g 上向量 空间的线性算子，所以任意的p f 都可以表示为 进而有 对于所有的j ( 1 j s ) ，设 其中勺f q ，1 j s s l ( p ) = c j l ( j 3 j ) j = l 其* b j k f q ( 1 j ，k s ) 设b 是一个f 叮上s s 的矩阵，其第( 歹，忌) 个元素；0 b j k 那么， 如果 ( c l ，c s ) b = ( d l ，d 。) ， 就有 第4 贞 岛勺 。触 = p 凤七b 。脯 = 岛 “ 侠七 d 。随 | l p l 国防科学技术大学研究牛院硕士学佗论文 所以，方程l ( 卢) = 0 等价于 ( c 1 ，c s ) b = ( 0 ，0 ) ( 2 1 ) 进而f 口m 上线性化多项式的求根问题就等价于f q 上线性方程组的求解问题 由线性化多项式，可以定义仿射多项式 定义2 2 【2 7 1 设l ( z ) 是f g m 上的一个线性化多项式，o t 砸 g m ，那么形如 a ( x ) = l ( x ) 一o t 的多项式就称为f g m 上的一个仿射多项式 类似于线性化多项式，仿射多项式所诱导的口m 的函数，就是一个仿射函数显然 地，p 是仿射多项式a ( z ) 的根，当且仅当l ( p ) = q 若使用方程( 2 1 ) 的表示，方程l ( p ) = n 就等价于 ( c 1 ，c s ) b = ( d l ，以) 进一步，可以定义一类非常特别的线性函数 定义2 3 f 2 7 】r e = f g m ，k = f g ，那么对于任意的z f ，f 上的迹函数定义为 丁，州k ( z ) = z + z 口+ + z 口“一1 若k 是f 的素子域，那么t r f k ( z ) 就被称为z 的绝对( a b s o l u t e ) 迹函数，记为t r f ( x ) 迹函数有如下重要性质【2 7 1 ( 1 ) t r f k ( x + y ) = t r f k ( x ) + t r f k ( y ) ，v x ，y f ； ( 2 ) t r f k ( c x ) = c t r f k ( x ) ，v x f ； ( 3 ) 将f $ d k 都视为k 上的向鼍空间，贝1 t r f k 是由f 到k 的线性变换： ( 4 ) t r f k ( a ) = m a ，v a k ； ( 5 ) t r f k ( x q ) = t r f k ( z ) ，v z f 接下来，分别给出置换多项式、线性置换、仿射置换和代数次数的定义 定义2 4 f 2 7 1 若h 中的多项式所对应的多项式函数厂：c _ y ( c ) ，是一个f q 到其自 身的置换，那么厂( z ) 就被称为置换多项式进一步，如果，( z ) 同时又是线性化多项式 ( 仿射多项式) ，那么就称，( z ) 所诱导的映射，为线性置换( 仿射置换) 第5 页 国防科学技术大学研究牛院硕士学位论文 定义2 5 1 2 5 1 设- 厂( z ) = 妻a s z s 陆【z 】，其中p 是一个素数那么，的代数次数( a l g e b r a i c d e g r e e ) 定义为 m 。a x s ih o ，s = ( s l ，8 2 s 竹) p 一 其中，s = ( s 1 ，8 2 ，8 n ) p 表示s 的p a d i c 展开 显然，代数次数为l 的多项式就是仿射多项式下面定义的二次型多项式是本文研 究的重要对象，同时也在密码学和编码学的很多重要领域有广泛的应用 定义2 6 【2 8 1 设f ( x ) 跏，并且，的代数次数 b 2 ，那么这类多项式就称为二次型 多项式 需要说明的是，当素数p 2 时，很多文献也称二次型多项式为d e m b o w s k i o s t r o m 型 多项式 2 2c c z 等价与e a 等价 由于有限域f p n 可以视为上的礼维向量空间，其上的函数之间也自然有一一对应， 所以下列叼上定义的概念自然可以对应到n 上去 定义2 7 设f 是哪到其自身的映射，f 的图( g r a p h ) g f 定义为 g f = ( z ，f ( z ) ) ：z ) 2 g 接下来，给出两种重要的等价关系 定义2 8 1 2 9 1 设f 和f 7 是赡到其自身的映射，若存在f 争上的仿射置换l ，使得l ( g f ) = g 肌那么就称f 和f 7 是c a r l e t c h a r p i n z i n o v i e v ( c c z ) 等价的 定义2 9 1 3 0 l 设f 和f ，是睇到其自身的映射，若存在赡上的仿射置换l 1 和l 2 ，以及 仿射函数l 3 ，使得f 7 = l 1 of o 三2 + 己3 ，那么就称f 和f 7 是扩展仿射( e x t e n da f f i n e ) 等价 的，简记为e a 等价 上述两种等价性对密码学函数的分类是十分重要，一个新的密码学函数的提出， 往往要求与已有的函数c c z 不等价或e a 不等价同时，不难发现，e a 等价是c c z 等价的 一个特例【2 9 】，因此函数之间的c c z 等价的判断比e a 等价的判断更加困难并且c c z 等 价在一般情况下是真包含e a 等价的例如：设d d = 1r o o d 矿一1 ，则i 厂( z ) = x d 是c c z 等 第6 贝 国防科学技术大学研究牛院硕士学位论文 价于，7 ( z ) = x d ，这是因为通过交换g f = ( z ，) ：z 睇】- 的前几行与后几行，便可以得 到 ( ，z ) ：z ) ，再将z = y a 带入，就有g ，= ( 秒，y d ”z f ；】- 然而一一般是e a 不 等价于的，这是因为一般它们具有不同的代数次数，而由定义可以容易推出，e a 等 价是不会改变多项式的代数次数的 另一方面，在这两种等价性定义所诱导的等价变换之下，有很多性质是不变的，称 之为c c z 等价不变量( e a 等价不变量) 例如：由e a 等价的定义，可以直接推出代数次数 就是e a 等价不变量，但一般不是c c z 等价不变量在后面的章节中，将给出几种与本 文有关的不变量 2 3 非线性度与几乎b e n t 函数 2 3 1 定义 设门铂夕是有限域f p m 到f p n 的函数，那么，和夕之间的距离定义为【2 8 1 d ( f ，g ) = l z mf ( x ) 一g ( x ) o 1 进一步，定义，的非线性度为【7 】 n f2 m l i a n d ( f , 1 ) 其中a 表示有限域到f p n 的所有仿射函数所构成的集合，的非线性度代表了，抵抗 线性攻击【7 】的能力，越大，厂抵抗线性攻击的能力越强 接下来，只讨论特征为2 的有限域上函数的非线性度设函数厂：f 2 m f 2 n ， 在( o ，b ) 处的w a l s h 变换( w a l s ht r a n s f o r m ) 定义为 f w ( a ，6 ) = x ( a x + 6 ，( z ) ) ， x e f 2 m 其中) ( ( z ) = ( 一1 ) n ( 引，对讹f 2 。，b f 2 n 那么就- - i p a 定义，的w a l s h 谱( w a l s hs p e c t r u m ) a ，= ，l cf w ( n ，6 ) in f 2 m ，b f 2 n ，b 0 水， 其中， 木术) 表示该多重集台 ( m u l t i s e t ) 而非线性度与w a l s h 变换有如下关系f 3 0 i ，= 2 一三倒。m a x 。咖。l ，( 口6 ) i ( 2 2 ) 值得注意的是，非线性度是已知的为数不多的c c z 变换不变量之一f 2 9 1 第7 页 国防科学技术大学研究牛院硕士学位论文 事实上，文献【2 8 】中证明，非线性度存在一个上界，2 n 一2 暑一，并且在佗为偶 数，仇鸶时，才存在函数，使得等号成立对于达到这个上界的函数，称之为b e n t 函 数【2 8 1 当m ：n 时，非线性度存在另外一个上界，2 n - l 一2 孚【3 1 1 ，当m 达到这个上 界的时候，称之为几乎b e n t 函数( a l m o s tb e n t ) ，简称a b 函数，在有些文献中也称其为极 大非线性( m a x i m i u mn o n l i n e a r ) 函数 2 3 2 已知的几乎b e n t 函数 直到现在为止，f 2 。上已知的a b 函数非常少，其中幂函数仅有4 个，请参见表2 1 表2 12 n 上已知的a b 幂函数，其中n 是奇数 g o l d 3 0 l2 。+ 1 g c d ( i ，n ) = 1 k a s a m i 3 2 1 2 2 i 一2 i + 1 g c d ( i ，n ) = 1 w e l c h t i 9 1 2 + 3 n = 2 t + 1 n i h o d 9 l 2 2 + 2 一1 ，t 偶； n = 2 t + 1 2 。+ 2 学一1 ，t 奇 h d o b b e r t i n ，v a nl i n t 等学者猜想，表2 1 已经包含了所有的单项式形式的a b 函数 而对于多项式形式的a b 函数，已知的仅是一些二次形式的多项式，由于其与几乎完全 非线性函数关系密切，我们将在下一节中给出 2 4 差分均匀度，完全非线性函数与几乎完全非线性函数 2 4 1 定义 对于有限域上的某个函数来讲，差分均匀度( d i f f e r e n t i a lu n i f o r m i t y ) 是衡量该函数抵 抗差分攻击能力强弱的指标，其定义为 定义2 1 0 3 0 1 设厂( z ) 峰矧，其中p 为素数那么，的差分均匀度就定义为 6 ，- 。 6 f p m a 邮x z n ：他+ n ) 一m ) ：6 ) 1 事实上，可以将差分均匀度的概念推广到一般的群之间的映射去，但由于这与本文关 系并不密切，所以省略，可以参考1 2 3 1 1 2 4 1 同非线性度一样，差分均匀度也是已知的为 第8 贞 围防科学技术大学研究牛院硕士学位论文 数不多的c c z 变换不变量之- - 2 9 1 由其定义可以看到，差分均匀度越小，则函数，抵抗 差分攻击的能力便越强进而就有 定义2 1 1 3 3 1 设f ( x ) n 吲，其中p 为素数若, i f = 1 ，那么就称，为完全非线性函 数( p e r f e c tn o n l i n e a rf u n c t i o n ) ，简记为p n 函数 对于p = 2 的情形，完全非线性函数是不存在的，这是由于 f ( x + a ) 一f ( x ) = ，( ( z + a ) 十a ) 一f ( x + 口) ， 这样一来，6 ，一定是偶数所以，有如下定义 定义2 1 2 3 0 】设f ( x ) f p n ，其中p 为素数若6 ，= 2 ，那么就称，为几乎完全非线 性函数( a l m o s tp e r f e c tn o n l i n e a rf u n c t i o n ) ，简记为a p n 函数 同时，a b 和a p n 性质有如下的两个重要关系 定理2 1 3 1 设，是f 2 。到其自身的映射，若，是a b 函数，那么，就是a p n 函数。 定理2 2 1 2 9 1 设礼为奇数，二次型函数，是f 2 。到其自身的映射，, 贝l j f 是a p n 的当且仅 当，是a b 的 定理2 1 意味着a b 函数肯定要l h a p n 函数少，同时也更难构造。而定理2 2 意味着， 如果可以在砸 2 的奇数次扩域上，构造二次型形式的新的a p n 函数，那么同时也就得到 了新的a b 函数 由于c c z 等价包含e a 等价，于是下面的这个定理告诉我们，p n 函数之间的c c z 等 价性和e a 等价性是一致的 定理2 3 3 4 1 设门嘞是叼一叼的完全非线性函数如果，和夕是c c z 等价的，那么它 们也是e a 等价的 2 4 2 已知的完全非线性函数 由于完全非线性函数本身所具有的重要性质，该类函数的构造一直都是编码、密 码和组合设计领域的重要问题，同时也是十分困难的问题 直到目前为止，我们已知的有限域f 矿上的完全非线性函数有如下的几类 ( 1 ) 1 ( z ) = 妒+ 1 ，其中整数0 南为奇数( d e m b o w s l c i a n do s t r o m 【3 5 】) ； ( 2 ) 2 ( 茁) = z 掣，其中p = 3 ，南为奇数并日g c d ( n ，) = 1 ( c o u l t e ra n dm a t t h e w s 【3 6 1 ) ； 第9 贞 国防科学技术大学研究牛院硕士学位论文 ( 3 ) 3 ( z ) = z 1 0 一u x 6 一u 2 x 2 ，其中p = 3 ，几为奇数并胃u f p ( d i n g a n dy u a n 3 7 ) ； ( 4 ) 4 ( z ) = u x p + l u p x p 他+ p 一如，其中n = 3 k ，g c d ( 3 ，七) = 1 ，k g c d ( k ，s ) 为奇数，s = 士惫 z = 二1 ，克k + - s s ：= 。o m m 。o d d3 3 并且u 是n 中的本原元( z h a ，k y u r e g h y a na n dw a n g 3 8 ) ； ( 5 ) 5 ( z ) = t 工护+ 1 + u 扩5 + p t + u p 舻5 + p + + o 1 5 谱值，n 偶； 使得p 3 ，g c d ( p ，n ) = 1 3 谱值，佗奇晰1 3 1 ( k + s ) ，( 8 ，3 k ) = ( 3 ，k ) = 1 ， 6 1 4 7 钍2 k x 2 一。+ 2 + 5 + 牡z 2 。+ 1 n = 3 k ，钍是f 2 3 k 上的本原元， 未知 + u z 2 一+ 1 + t d 札2 + 1 2 2 + 。+ 2 。 v ，w f 2 k ，口w 一1 g c d ( k ，8 ) = l ，2fk ，2f8 ， 7 1 4 8 1 q z 2 。+ 1 + q 2 z 2 + 4 + 2 o t ，p 是f 2 。t 上的本原元， 5 谱值【4 9 1 + z z 2 + 1 + 仁k - 1 17 i x 2 + 1 + 2 m f 2 2 k ，v w 一1 3 1 ( k + s ) ，( s ，3 k ) = 1 ， 8 1 4 8 1札z 2 - k + 2 + 。+ u 2 。x 2 8 + 1 n = 3 k ，3 十k ，未知 + 钞z 2 七+ 。+ 2 。 u ，u 是f 2 n i 的本原元 第l l 页 国防科学技术大学研究牛院硕士学位论文 表2 3f 2 n 上已知的a p n 幂函数 g o l d 3 0 2 。+ 1 g c d ( i ，礼) = 1 k a s a m i l 3 2 1 2 2 i 一2 i + 1 g c d ( i ，佗) = 1 w e l c h 【1 6 1 2 + 3n = 2 t 士1 n i h o h 7 1 2 。+ 2 一1 ，t 偶；2 。+ 2 学一1 ，t 奇 f , = = 2 t4 - 1 i n v e r s e l 3 0 12 2 t 1n = 2 t + 1 d o b b e r t i n 1 8 12 4 。+ 2 3 t4 - 2 2 t + 2 t in = 5 t 表2 4 n 上已知的a p n 幂函数，p 为奇数 指数d条件 k 1 0 0 s t e 姗a n 【3 0 1 f 5 1 1 【5 2 】 p n 一2p 三2m o d3 h e l l e s e t h 5 2 1 佗= 2 m 一1 s a n d b e r g 2 m 一1m 2 h e l l e s e t h 5 2 1 p 三3 ，7m o d2 0 ，p n 7 ， s a n d b e r g贮。一1 矿2 7 ，并且扎为奇数 2 d o b b e r t i ne t a 1 1 5 3 1 墨1 2 ! ! ! ! = 1 n 三3m o d4 2 f e l k e 5 4 13 ( l + i ) 2 _ 1j - 3 n - - 1 2 2 扎三1m o d4 d o b b e n i ne t a 1 1 5 3 1 筻! = 1 礼三3m o d4 8 3 n + 1 1 。3 “一1 n 兰1m o d4 1 厂一十丁 h e l l e s e t h ，r o n g 业 矿三3m o d8 4 和s a n d b e r g 1 5 5 1 业上inml42 p n 兰7m o d8 h e l l e s e t h ，r o n g f f l ls a n d b e r g1 5 5 1 堑! = 1 p n 兰2m o d3 3 h e l l e s e t h ，r o n gp = 3 ，礼 1 ， ； l l s a n d b e r g 1 5 5 1 矿一3n 为奇数 h e l l e s e t h ，r o n g n = 2 m ，p 3 ， 和s a n d b e r g 1 5 5 1 p m + 2p m = = 1m o d3 平凡的 3 p 3 第1 2 页 国防科学技术大学研究牛院硕士学位论文 第三章。七上一类a p n 函数的w a l s h 谱 文献【2 6 】中提出了一个：t 上的三项式a p n 函数，本章将证明该函数的w a l s h 谱是5 谱 值的，这与。t 上g o l d 型函数z 2 + 1 的谱值一致，其中( i ，2 七) = 1 从而可以知道，通过计 算该函数的w a l s h 谱值，是无法判断其与g o l d 型函数的c c z 等价性质的进一步，确定了 该类函数的非线性度，并利用，构造了礼维二元线性码及其扩展码，并确定了它们的最 小距离、信息位数和特征集本章结果已发表在中国密码年会2 0 0 8 年会论文集中1 5 6 1 3 1 预备知识 为了证明本文的主要结论，需要以下的两个引理及一个推论其中，引理3 1 和引 理3 2 证明都是基本的数论和代数知识，在这里不对其进行证明 引理3 1 设d = g c d ( m ，n ) ，那么g c d ( 2 m 一1 ，2 n 一1 ) = 2 d l ，并且 ， l2 d + 1m d 是偶数并r n d 是奇数， g c d ( 2 m 一1 ，2 n + 1 ) = ( 3 1 ) il其它 、 引理3 2 1 5 7 1 设正整数n ，s 满足条件g c d ( n ，8 ) = 1 ，k 是一个域，日1 和巩分别是k 的n 次 和8 次扩域那么玩n 2 = k 推论3 1 设n ，8 ，d 是正整数，并j i g c d ( n ，8 ) = 1 那么线性化多项式 d c ( z ) = a i x 2 ”f 2 n i x ， i - - - - 0 在f 2 。中最多有2 d 个零点 证明令y 表示c ( z ) 在f 2 。中的零空间由于c ( z ) 是线性化多项式，因此y 就是f 2 上 的向量空间，设其维数为m 设v cf 2 。表示y 中元素在f 2 。上所生成的向量空间由 于g c d ( n ，8 ) = 1 ，由引理3 2 ，v 7 就是f 2 。上的一个m 维向量空间进一步，对于所有的c f 2 。以及u f 2 。，有( 刨) = c c ( u ) 因此，所有的y 7 中的元素，都是c ( x ) = o 的根又 由于y 在f 2 上的维数是m ，于是l y ，| = 2 8 m ，进而c ( z ) 在f 2 。中最少有2 8 m 个零点另一方 面，一个2 d s 次多项式至多有2 d s 个零点因此，有m d 口 设k ，i 是整数，几：2 k ，其中后3 文献 2 6 1 中，在f 2 。上证明了一类新的二次型函数 是a p n 的函数 ，( z ) ：x 2 2 4 + 2 2 + p z g + 1 + o x q ( 2 2 1 + 2 q ， ( 3 2 ) 第1 3 页 围防科学技术大学研究牛院硕士学位论文 其中q = 2 七，0g 入( 2 4 + 1 ) ( q 一，入f 2 2 k ，0 q + 1 = 1 ，g c d ( i ，k ) = 1 ，p 卢q + p 0 由引理3 1 ，我们知道当i 是偶数时，由于g c d ( i ，k ) = 1 ，所以g c d ( 2 驰一1 ，2 i + 1 ) = 1 那 z , z - + 1 就是f ，。k 上的一个置换，这意味着不可能存在0 使得0g 入( 2 + 1 ) ( 口一1 1 ，a f 2 2 k 并 且o q + 1 = 1 因此，可以直接令i 为奇数 由定理2 2 我i l i o n 道，在f 2 奇数次扩域上，二次型a p n 函数的w a l s h 谱值是可以马上 确定下来的而在这里，由于f 噼是f 2 的偶数次扩张，虽然，是a p n 函数，它的w a l s h 谱还 是不能马上确定的事实上，确实存在f 2 偶数次扩张上的二次型a p n 函数，并不是5 谱 值的下面的例子来自文献【4 0 】，设u 是f 2 6 中的本原元，那么 g ( x ) = z 3 + u l l x 5 + u 1 3 x 9 + z 1 7 + u l l x 3 3 + z 4 8 ， 是具有7 谱值的二次型a p n 函数 3 2 新的a p n i 函数f l 勺w a l s h 谱值 定理3 1 设k ，i 是整数，n = 2 k ，其中七3 f ( x ) f 2 n i x 定义为 ，( z ) ：x 2 2 i + 2 + 触口+ 1 + o x q ( 2 2 + 2 “， ( 3 3 ) 其中q = 2 k , 0 彰 入( 2 + 1 ) ( 口一，a f 2 2 k ，o q + 1 = 1 ，g c d ( i ，k ) = 1 ，p 伊+ p 0 ，并且i 是奇数 设f wa ，b ) 是，( z ) 在n ，b f 2 ：t 处的w a