（基础数学专业论文）几类密码函数的二阶非线性度下界.pdf

、 t h el o w e rb o u n do ft h es e c o n do r d e rn o n l i n e a r i t yo f s e v e r a lc l a s s e so fb o o l e a nf u n c t i o n s at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：c h e nx i n j i a o s u p e r v i s o r ：p r o f z e n gx i a n g y o n g h u b e iu n i v e r s i t y 胁h a n c h i n a 湖北大学学位论文原创性2 声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 论文作者签名：硝、行设 签名日期：i o 年，月) 侣 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有 关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目 的的前提下，学校可以公开学位论文的部分或全部内容( 保密论文在解密后遵守 此规定) 鞴磊黧破和岛 指导教师签名： 嗜h ；锣 日期：7 一o o 少西 日期：加，。上玎 中文摘要 摘要 在流密码体制中，密码系统的安全性与用作非线性组合函数或滤波函数的 布尔函数有着密切的关系。在分组密码体制中，决定整个系统安全性的非线性 部件s 盒的设计也与布尔函数紧密相关。因此，布尔函数在对称密码系统的安 全性方面扮演着重要角色，它的密码性质优劣会直接影响整个密码系统的安全 性。由于改变布尔函数真值表中的某一位或几位输出，其代数次数可能大幅增 加而整体密码性质变化较小，故密码系统中的布尔函数不仅要具有较高的代数 次数，而且不存在代数次数很低的函数可以较好地逼近它。也就是说，应用于 密码系统中的布尔函数与低次布尔函数的汉明距离应当足够大。因此，对于每 个正整数r l ，目前对7 阶非线性度的研究主要根 据布尔函数微商的r 一1 阶非线性度与其7 阶非线性度之间的关系来讨论。 利用迹函数的性质求解向量空间的维数，并分析布尔函数微商的w a l s h 谱 的取值范围，从而确定布尔函数微商的非线性度下界。基于此方法，本文考察 了两类布尔函数的二阶非线性度下界。对于偶数n ，本文首先确定了布尔函数 类t r ( x 2 叫2 + 3 ) 的二阶非线性度下界；另外，对于正整数n = 2 ( m o d4 ) ，本文确定 了一类布尔函数t r ( x 2 2 + 2 州”1 + 1 1 的二阶非线性度下界。与相同变元数的两类已 知布尔函数相比，本文研究的布尔函数具有更紧的二阶非线性度下界。这样能 够更好的抵抗二次函数和仿射函数的逼近。 关键词：布尔函数；二阶非线性度；w a l s h 谱：微商；迹函数 湖北大学硕上学位论文 a bs t r a c t i nt h es t r e a mc i p h e rs y s t e m t h e r ei sa t i g h tr e l a t i o n s h i pb e t w e e nt h es e c u r i t yo ft h e s y s t e ma n dt h eb o o l e a nf u n c t i o n su s e di nn o n l i n e a rc o m b i n i n go rf i l t e r i n gf u n c t i o n s i t i sa l s oi m p o r t a n tt ot h ed e s i g no ft h en o n l i n e a rs b o x e s b e c a u s eo ft h e s e b o o l e a n f u n c t i o n sp l a yc r i t i c a lr o l ew i t hr e s p e c tt ot h es e c u r i t yo ft h es y m m e t r i cc r y p t o s y s t e m ， t l l e i rp r o p e r t i e sc a ni n f l u e n c et h es e c u r i t yo ft h ew h o l es y s t e m w h e naf e wb i t so ft h e o u t p u tt ot h ef u n c t i o na r ec h a n g e d ，t h ep r o p e r t i e sd on o tc h a n g em u c h c o n s i d e r i n g t h i s ，t ot h eb o o l e a nf u n c t i o n su s e di nt h es y s t e m ，i t sa l g e b r a i cd e g r e e ss h o u l dh i g h ，a n d t h e r ea r en of u n c t i o n so fl o w e ra l g e b r a i cd e g r e e st oa p p r o x i m a t et h e m t h a ti st os a y , t h eh a m m i n gd i s t a n c eb e t w e e nt h e ms h o u l dl a r g ee n o u g h t h e r e f o r e ，f o re v e r yi n t e g e r r n i ti sv e r yi m p o r t a n tt oc o n s i d e rt h em i n i m u mh a m m i n gd i s t a n c eo ft h sb o o l e a n f u n c t i o nt oa l lf u n c t i o n so fd e g r e e sa tm o s tr t h i sd i s t a n c ei su s u a l l yc a l l e dt h er t h o r d e r n o n l i n e a r i t yo f t h eb o o l e a nf u n c t i o n t h er t ho r d e rn o n l i n e a r i t yo ft h eb o o l e a n f u n c t i o nu s e di ns y m m e t r i cc i p h e r ss h o u l db eh i g h r e c e n t l y , t h el o w e rb o u n do ft - t h o r d e rn o n l i n e a r i t yc a nb ed e t e r m i n e dm a i n l yd e p e n d i n go nt h e r e l a t i o n s h i pb e t w e e nt h e ( r 一1 ) 一t hn o n l i n e a r i t yo fd e r i v a t i v ea n dr - t ho r d e rn o n l i n e a r i t yo fab o o l e a nf u n c t i o n m a k i n gu s eo ft h ep r o p e r t i e so ft r a c ef u n c t i o nt os e e kt h ed i m e n s i o no ft h ev e c t o r s p a c e ，a n da n a l y z i n gt h ew a l s hs p e c t r u mo ft h ed e r i v a t i v e ，t h el o w e rb o u n do ft h en o n 1 i n e a r i t yo f t h ed e r i v a t i v e sc a nb ed e t e r m i n e d b a s e do nt h i sm e t h o d t h el o w e rb o u n do f t h es e c o n do r d e rn o n l i n e a r i t yo ft w oc l a s s e so fb o o l e a nf u n c t i o n sa r ep r e s e n t e di nt h i s p a p e r f i r s t l y , f o re v e ni n t e g e r 礼，t h eh el o w e rb o u n do ft h es e c o n do r d e rn o n l i n e a r i t y o ft r ( x 2 叫2 + 3 ) i sg i v e n ；b e s i d e s ，o ra p o s i t i v ei n t e g e rn = 2 ( m o d4 ) ，t h el o w e rb o u n do f t h es e c o n do r d e rn o n l i n e a r i t yo ft h eb o o l e a nf u n c t i o nt r ( z 2 2 + 2 ”7 2 1 + 1 1i sd e t e r m i n e d c o m p a r e dw i t ht w oc l a s s e so fb o o l e a nf u n c t i o n sw i t ht h es a m en u m b e ro fv a r i a b l e s ，t h e f u n c t i o n sd i s c u s s e di nt h i sp a p e rh a v eat i g h t e rl o w e rb o u n do n2 t ho r d e rn o n l i n e a r i t y i tc a nr e s i s tt h ea p p r o x i m a t i o n so f q u a d r a t i cf u n c t i o n sa n d a f f i n ef 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 ；2 - t ho r d e rn o n l i n e a r i t y ；w a l s hs p e c t r u m ；d e r i v a t i v e ； t r a c ef u n c t i o n 目录 目录 摘要 i a b s t r a c t ( 英文摘要) 1 引言1 1 1 布尔函数的研究背景1 1 1 1 密码体系简介 1 1 1 2 布尔函数在流密码中的应用 2 1 2 布尔函数的低次逼近 3 1 2 1 低次逼近的原理 3 1 2 2 布尔函数的非线性度轮廓 3 1 2 3 非线性度轮廓与其他密码学指标之间的关系 4 1 3 论文的研究内容和组织结构5 2 预备知识 6 2 1 布尔函数的基础理论 6 2 2 函数的二阶非线性度与其微商的非线性度的关系 8 3 两类布尔函数的二阶非线性度下界 9 3 1g o l d 型指数函数的二阶非线性度下界9 3 1 1g o l d 型函数微商的非线性度9 3 1 2g o l d 型函数的二阶非线性度下界1 4 3 2t r ( x d ) ，d = 2 n 2 + 2 ”2 1 + 1 的二阶非线性度下界1 4 3 。2 1 t r ( x d ) 型函数微商的非线性度】4 3 2 2 t r ( x d ) 型函数的二阶非线性度下界1 8 4 其他函数类的非线性度轮廓2 0 4 1t r ( x d l 型函数类的二阶非线性度下界2 0 4 2 这些函数类的二阶非线性度下界的比较2 l 5 结果及展望2 2 参考文献2 3 致谢2 9 i i i 1引言 随着信息时代的来临，伴随计算机网络技术的飞速发展，现代密码学不再 局限于军事、政治、外交等，它的商用价值和社会价值也越来越广泛。 从1 9 7 7 年美国国家标准局正式颁布的数据加密标准d e s 【l 】，到2 0 0 1 年的高 级数据加密标准a e s 2 1 ，还有我国在2 0 0 6 年公布的商用数据加密标准s m s 4 ，以 及各种数字签名方案和各式的攻击方法等，所有这些在密码学发展史上具有标 志性的作用，也为现在密码学的发展指明了新方向。近二十年来，密码学无论 在理论上还是在应用上都取得了很好的发展，d e s 的破译，m d 5 的破译，分组 密码加密标准也在不断推陈出新，流密码也有了加密标准，在如今，一些新的 密码学研究领域也在涌现，如量子密码，混沌密码，d n a 密码。所有这些都给 密码学的发展带来巨大的推动力，同时也为其进一步的发展提供更加广阔的前 景。 1 1 布尔函数的研究背景 1 1 1 密码体系简介 密码学的基本思想是伪装信息，这样使得未授权者不能够识别信息【3 1 。它 是研究密码系统或者通信安全的一门科学。主要有两个分支：密码编码学和密 码分析学。根据密钥的特点，密码体制分为对称和非对称密码体制。对称密 码体制又称为单钥或者私钥或者传统密码体制，非对称密码体制又称双钥或 者公钥密码体制1 4 。一般现实中使用的密码方案是同时使用这两种密码体制， 其中，使用公钥密码体制来生成和交换密钥，使用私钥密码体制则用来传输 数据。本文的研究内容限于私钥密码体制，对于公钥感兴趣的读者可以参阅 文献【5 ，6 ，7 ，8 】。在实现私钥密码体制中，流密码和分组密码是两种基本方式。 一个常规的密码系统包括下面五个基本要素1 3 ：明文空间，密文空间，密钥空 间，加密算法，解密算法。对密码的破译或者攻击的类型也很多，根据密码分 析者破译时已经具备的前提条件，人们通常将攻击类型分为四种1 8 ： ( 1 ) 唯密文攻击：密码分析是在仅知一段密文的情况下进行的； ( 2 ) 已知明文攻击：密码分析者事先知道一些明文对。这可能对给定密文的 分析有决定性帮助： ( 3 ) 选择明文攻击：密码分析者可得到所需的任何明文所对应的密文，这些 密文与待解的密文是用同一个密钥加密得来： 湖北大学硕上学位论文 ( 4 ) 解密变换攻击( 也称选择密文攻击) ：在收到任何密文之前，由于密码分 析者知道加密方法，从而可以设法找到对应的解密方法。 其中选择明文攻击比已知明文攻击强很多。因为当密码分析者对密钥有一 些明确猜测时，可将自己伪装成该系统的合法使用者。对于密码体制的安全评 估问题始终是密码学中的一大难点，要证明一个现有密码体制的安全性，需要 证明该系统能否抵抗所有攻击方法。但是现在我们所面临的问题是：对于一个 密码体制，在一般情况下是无法证明存在几种攻击方法。到目前为止，只有 “一次一密”被证明是绝对安全的。可是“一次一密”同时又存在着一些缺 陷。因此，密码设计和密码分析是相互依存的，但又是互逆的。受到这种密码 体制的启发，在流密码的加解密过程中使用了伪随机序列。在伪随机序列方 面，许多学者做了很多的研究和探索，同时也提出来一些评价序列以及序列集 的随机性和相关性【9 ，1 0 , 1 1 , 1 2 , 13 】等的方法，还有关于构造具有较好性质的随机序列 以及序列集的方法【1 4 1 5 , 1 6 , 1 7 , 1 8 。 1 1 2 布尔函数在流密码中的应用 流密码【l9 1 ，又称序列密码。其加密和解密的思想非常简单，通常密文是用 密钥流序列与明文序列进行叠加得到，再用同一个密钥流序列与密文叠加以此 恢复出明文【删。其中密钥流序列是由密钥流生成器产生的，最常用的密钥流生 成器是非线性滤波生成器和非线性组合生成器【2 1 1 。这二者的安全性能与所选择 的滤波函数和组合函数【2 2 】有着非常密切的关联，也就是说密码函数在密钥流生 成器的设计中扮演着非常重要的角色。通常情况下，密码函数就是布尔函数， 有时候也有有限域上的函数或者其他代数结构上的函数。本文的研究内容主要 是在布尔函数这一部分。 为了提高密钥流生成器和非线性组合生成器的安全性能，必须采用具有较 好的密码学性质【2 3 2 4 ，2 5 】的滤波函数和组合函数，于是，构造具有较好的密码学 性质 2 6 , 2 7 , 2 8 的密码函数显得尤为重要。对于密码函数的使用上有一些理论结 果。使用于流密码中的滤波函数要求满足的性质有：平衡性、高的代数次数、 高的非线性度、至少一阶相关免疫；而使用于流密码的组合函数要求满足的性 质有：平衡性、高的代数次数、高的非线性度、高阶相关免疫；使用于分组密 码中的向量布尔函数被要求至少满足的性质有：高的非线性度、平衡性、高的 代数次数、低差分特征。这些是在2 0 0 3 年代数免疫阶【2 9 1 这个概念提出之前，随 着代数攻击和快速代数攻击方法 2 9 , 3 0 , 3 1 , 3 2 的提出，对密码体系中使用的密码函 数要求具有较高的代数免疫阶1 1 7 , 3 3 ，3 4 3 5 。近年来，布尔函数的非线性轮廓也引 起了国内外密码学者的浓厚兴趣。对于使用的布尔函数应具有较高的高阶非线 性度。 2 1 2 布尔函数的低次逼近 1 - 2 1 低次逼近的原理 为了抵消移位寄存器的线性特点，增大输出序列的周期复杂度，防止已知 攻击，对于在移位寄存器驱动的组合密钥生成器中的组合函数必须是非线性 的。可是具体用什么来衡量和刻画非线性呢? 人们在这方面做了很多的探索。最开始的时候密码学者考虑的是函数的代 数次数，事实上，一个代数次数很高的函数也可以用线性函数来逼近。显然， 仅仅用代数次数是不够的。后来以编码理论为工具，考虑函数和线性函数之间 的距离定义了非线性度【3 6 1 。作为衡量密码函数非线性性的重要指标之一，非 线性度标志着密码函数抵抗线性攻击和相关攻击的能力。于是具有较高非线性 度的密码函数更更好抗线性攻击。同时，考虑了函数与线性函数，或者说是所 有仿射函数之间的距离后，又有新的问题出现，由于改变布尔函数真值表中的 某一位或几位输出其代数次数会大幅增加而整体密码性质并未提高，故密码系 统中的布尔函数不仪要具有较高的代数次数，而且不存在代数次数很低的函数 可以较好地逼近它，即应用于密码系统中的布尔函数与低次布尔函数的汉明距 离应当足够大。因此对于每个正整数r n ，考察布尔函数和所有次数不超过 r 的布尔函数的最小汉明距离非常重要，这个最小距离就是布尔函数的r 阶非 线性度，换句话说，n f r ( ，) 同时也是布尔函数，到r 阶r e e d m u l l e r 码r m ( r ，佗) 的距离【3 7 1 。关于此，许多学者研究了一些关于二阶r e e d m u l l e r 码的加密算法 等 3 8 ，3 9 4 0 , 4 1 1 。 1 - 2 2 布尔函数的非线性度轮廓 上节中提到了函数的r 阶非线性度及其由来。为了考察函数抵抗低次函数 逼近【4 2 ，4 3 】的能力，不能够只考虑单独的某一参数的7 阶非线性度，而是要总体 概况起来综合考虑，于是也就有了非线性度轮廓【4 4 】这个概念。作为抵抗低次逼 近能中的一个重要的衡量指标，非线性度轮廓和其他的密码指标之间又存在着 怎样的关系以及如何计算和确定一个给定的布尔函数的非线性轮廓，还有如何 获取具有较好的非线性度轮廓的布尔函数等问题都是值得进一步研究的课题。 现在已知的关于函数非线性度轮廓【4 5 】的结果很少，现阶段已知的关于7 阶非线 性度的最好的上界也只是个近似值【删： n = 2 n - 1 _ 尘2 ( 1 + v 互) r - 2 - 2 暑+ o ( n r - 2 ) 3 湖北大学硕上学位论文 利用函数的微商，通过迭代的方法得出布尔函数的非线性度轮廓的关 系【4 7 1 。例如： 佗w ) 互1 翼弩m 一( d n ，) ) ， 进一步地， 1 几。( ，) 2 n 一1 一主 由此可以继续对微商的高阶非线性度进行演算。得到 1 n o ( ，) 2 ”1 一言 z j 还有引入其他参数对函数的非线性度轮廓进行更进一步的讨论研究。例 如，对于具体的函数类，现在已知的考察了其高阶非线性度的函数类有w e l c h 指数函数，还有m m 类函数，i n v e r s e 函数等。其中因为代数次数的原因，对于 i n v e r s e 函数考虑的高阶非线性度要更进一步。 1 2 3 非线性度轮廓与其他密码学指标之间的关系 根据r 阶非线性度的定义可知，布尔函数的非线性度轮廓表示的序列在r 大于原布尔函数的代数次数后就全部为o ，所以通常情况下是只讨论小于布尔 函数的代数次数的高阶非线性度。对于高阶非线性度和其他密码学指标之间的 关系，也引起很多密码学者的研究兴趣。首先对于代数次数r + l 扎，则有 n f r ( ，) 2 铲r - 1 。一阶非线性度，也就是我们常说的非线性度，它与函数的代数 免疫阶之间存在如下关系【4 8 】： 2 ai(y)-nl(f)2 ( 2 r 了上) 1 = u 、7 对于礼变元的布尔函数，当n 为偶数时，一阶非线性度可以达到最高2 铲1 2 暑一1 ，即这类函数为b e n t 函数。对于奇数情形，通过函数级联，可以得到的最 大一阶非线性度为：2 俨1 2 孚。 至于一般情形，函数的高阶非线性度与代数免疫阶之间还存在着一定的关 联，对于代数免疫为七的礼变元布尔函数，文献【4 4 ，4 9 1 给出了n 0 ( ，) 的下界： k - r - 1k - r - 1 n l ，( ，) m a x ( ( ：) ，2 ( n 了) ) ， i = 0 i = 0 m e s n a g e r 肛步提高了这个下界【5 0 】： k - r - 1k - r - 1 n l ，( ，) e ( ：) + ( n i ”) i = 0 i = k - 2 r 由于在考察函数的7 阶非线性度时，要想确定其微商的r 一1 阶非线性度同 样很难，就目前为止，对于函数的高阶非线性度的考察也大多数仅限于对于二 阶非线性度的研究。 1 3 论文的研究内容和组织结构 基于文献【4 4 给出的关于高阶非线性度的讨论方法，本文给出了两类具有 较好非线性度的函数的二阶非线性度下界。并将它们与已知的函数类的二阶非 线性度下界进行比较。 论文结构如下： 第一章介绍布尔函数的研究背景以及其在流密码中的应用。包括设计密码 函数应满足的各种性质以及使用的密码函数的低次逼近原理。布尔函数的高阶 非线性度的研究背景和实际应用。 第二章给出了本文关于布尔函数的一些基础理论知识。主要包括迹函数的 性质介绍，布尔函数的r 阶非线性度与其微商的r 一1 阶非线性度之间的关系。 第三章主要讨论了两类已知非线性度很高的布尔函数的二阶非线性度下 界，主要应用了布尔函数的二阶非线性度与函数微商的非线性度之间的关系来 确定，并将这两类函数的二阶非线性度下界与已知的函数类进行比较。证实本 文中函数类具有更紧的二阶非线性度下界。这样能够更好的抵抗线性攻击和二 次逼近。 第四章是给出了其他的函数类的高阶非线性度，当参数选择一样的时候， 对这些函数类的二阶非线性度进行了比较。 第五章是对本文工作的总结和展望。 5 一 湖北大学硕上学位论文 2 预备知识 布尔函数是定义域为二元域 0 ，1 上的n 维向量空间霹，值域为二元域 o ，1 ) 的函数。在现代密码学最初的设计中，密码函数就有很广泛的应用。在 本章中，对布尔函数做出一些简单的基础介绍，同时也作为下面章节研究的预 备知识。 2 1 布尔函数的基础理论 根据同构关系我们知道，在一组基下，向量空间曰和有限域f 2 。是等同 的。布尔函数( b o o l e a nf u n c t i o n ) 就是从毋到f 2 = 0 ，1 的所有映射，记所有这 些n 变元的布尔函数所组成的集合为魄。一个布尔函数的汉明权重w t ( f ) 定义 为使得函数值等于1 的。的个数，即函数的支集s t , p p ( f ) = z 毋i f ( x ) = 1 ) 的 势。若这个势等于n 2 ，则此布尔函数为平衡的。两个布尔函数f ，g 之间的 汉明距离( h a m m i n gd i s t a n c e ) 贝j 定义为d ( ，9 ) = w t ( fo 夕) 。关于布尔函数的表 示方法，具体有很多形式，例如：代数正规型、真值表、多项式表示、小项表 示、矩阵表示、迹函数表示、w a l s h 谱表示等等，而且对于上述的这些表示方法 是可以互相转化的。为了我们这篇文章中对应的研究方便，我们在此只列举其 中的几种表示方法。 ( 1 ) 亿元布尔函数f ( x ) 的代数正规型( a n f ) m ) = f ( x l ，x 2 ，a t , n ) = n ，n j 1 ，2 ，0 7 3 “，n i e l 其中a i 足，这也可以算是多项式表示。由此我们也可以得到此函数的代 数次数的定义即为：函数的a n f 表示中系数非零的乘积项中的最大次数，记 之为d e g ( f ) 。对于那些代数次数小于等于l 的函数，称之为仿射函数( a f f i n e f u n c t i o n ) 。所有n 变元的仿射函数构成的集合记作a 。 ( 2 ) 迹函数表示 从有限域f 2 。到b 的迹函数 5 ht r 表示的布尔函数为 为了下文叙述方便，先简略介绍一下推广的迹函数及性质。对于q f = 一6 z 御 = zr 2 预备知识 b m ，k = 扇，迹函数t r e i g ( o e ) = q + q 9 + + q 叮仉，其性质有： ( i ) t r f k ( a + p ) = t r f k ( ( x ) + t r f k ( p ) 对于所有的a ，p f ； ( i i ) t r f k ( a q ) = a t r f k ( q ) 对于所有a k ，q f ； ( i i i ) r f 似( q ) 是一个从f 到k 的线性变换； ( i v ) t r f g ( a ) = m a 对于所有a k ； ( v ) t r f k ( a q ) = t r f k ( a ) 对于所有o l f 。 ( 3 ) w a l s h 谱表示 任何一个布尔函数，都能由w a l s h h a d a m a r d 系数表示为一个算术多项式： ，( z ，z z ，z n ) = 刍 五+ 五- ( 一1 ) z n + 五( 一1 ) z n 一- 十五( 一1 ) 。n 一。z n + + 五。一1 ( 一1 ) 。- 。z ：。n 】， 其中。表示模2 相加，五，五，五。一1 r 是f o u r i e r 谱系数。这种表示方法是 根据f o u r i e r 谱反演公式得出的。通过这种布尔函数的表示方法可知分析谱系数 与直接分析布尔函数的多项式是等价的，从而推广了布尔函数的密码学性质的 研究工具。在此，介绍一下关于函数的w a l s h 变换的定义： 定义2 1 对于任意入曰，函数，的w | a l s h 变换定义为一个从曰到整数集z 的映射 晰( a ) = ( 一1 ) m ) 船a z 露 根据w a l s h 变换的定义，给出了函数的非线性度( n o n l i n e a r i t y ) 表示方式 m ( ，) = 2 “一互1 蹴i ( 姚 其中z 入表示露上z 与入的内积，由于向量空间毋等同于有限域f 2 。，函数 的w a l s h 变换还可以表示成w f ( a ) = ( 一1 ) ，( z ) + 打( n ) 。布尔函数的非线性度 。 z 两 的原始定义为函数与所有仿射函数的极小距离，即n l ( f ) = r a i n ( d ( f ，夕) ) 。 9 e q n 上面给出的是函数的非线性度的描述性表示，为了抵抗仿射函数的逼近， 那么函数必须有较高的非线性度。以此类推，为了防止二次函数的逼近，在原 来基础上又添加了函数的2 阶非线性度以及相应的非线性度轮廓的概念。 定义2 2 对于任意正整数7 n ，n 变元布尔函数，到所有次数不大于r 的布尔 函数的极小距离被称为厂的r 阶非线性度，记作n f r ( 厂) ，特别地，当r = 1 时 简记为n t ( f ) ，函数，的非线性度轮廓定义为其r 阶非线性度r = 1 ，2 ，礼一1 湖北大学硕上学位论文 所组成的序列( h i ( f ) ，n 1 2 ( f ) ，n l n 一，( ，) ) 。 定义2 3 对于任意a 曰，布尔函数f ( x ) 在a 点的微商定义为 d n ( ，( z ) ) = ，( z ) of ( xoo ) 在若干向量a i 处多次求微商进而得函数的高阶微商 2 2 函数的二阶非线性度与其微商的非线性度的关系 在上面的描述中，布尔函数的非线性度与布尔函数的w a l s h 变换，也就是 w a l s h 谱之间存在联系。因此研究函数的二阶非线性度时，我们同样也可以借助 w a l s h 谱，只不过是借助其微商的w a l s h 谱。对于函数的r 阶非线性度，c a r l e t 在文献【4 7 】中通过迭代的方法给出了其下界： 引理2 4 设正整数r n ，对于他变元的布尔函数，有 1 礼f r ( ，) 2 , , - 1 一一2 那么由此对应的二阶非线性下界就可以有微商的非线性度来确认了，它们 之间满足关系式 此扭毛f 虿面 一8 吼 u 仇汹 + z ，j 叼 = z ， m d 虮 d 3 两类佰尔函数的二阶非线件度下界 3两类布尔函数的二阶非线性度下界 根据前面的预备知识以及我们对于函数的高阶非线性度的了解，确定一个 函数的高阶非线性度是一个比较网难的工作。对于所要研究的布尔函数，需要 考虑的前提条件是其一阶非线性度较好，对于变元个数是偶数情况下的函数 类，我们希望其非线性度达到最优，也就是函数为b e n t 函数。至于变元个数为 奇数的情形，在本文中没有给予进一步的讨论研究。在这一章节中，我们主要 给出了两类确定为b e n t 函数的二阶非线性度下界。采用的方法是先确定函数的 微商的非线性度，其中用到的主要数学工具是迹函数的性质以及向量空问的维 数与线性方程的解数之间的关系。 3 1g o l d 型指数函数的二阶非线- | 生度下界 这一小节中，主要给出了布尔函数t r ( x 2 们+ 3 ) ，n = 2 m ( m 为任意正整 数) 的二阶非线性度下界。 3 1 1g o l d 型函数微商的非线性度 先给出引理3 1 ，是关于这类函数微商的非线性度。 引理3 1 函数t r ( x 2 2 + 3 ) ，n = 2 m ( m 为任意正整数) 在非零点。的微商d 口，的 非线性度满足 剐( d n ，) 2 2 m _ 1 _ _ 2 m , 2 ，。a ef f 2 2 m + 1 m + 1 , 证明因为，( z ) = t r ( x d ) = t r ( x 2 2 + 3 ) ，则 d 。f ( z ) = f ( x ) + f ( x + a ) = t 7 ( z 2 “2 + 3 ) + t r ( ( z + 。) 2 “7 2 + 3 ) = t r ( x 2 ”+ 3 + ( z + g ) 2 ( z + o ) 2 ( z + o ) ) = t r ( x 2 ”+ 2 a + x 2 “+ l a 2 + x 2 , n a 3 + x 3 a 2 “+ x 2 a 2 ”+ 1 + x a 2 ”+ 2 + a 2 m + 3 1 9 一 令g ( 5 ) = d 口，( z ) ，则 夕( o ) + 9 ( z + y ) t r ( x 2 r n + 2 n + z 2 ”+ 1 口2 + z 2 ”口3 + 5 3 a 2 ”+ z 2 口2 ”+ 1 + z n 2 m + 2 + 0 2 m + 3 ) + 打( ( z + 秒) 2 ”+ 2 n + ( z + 可) 2 ”+ 1 0 2 + ( z + 箩) 2 ”口3 + ( z + ) 3 0 2 m + ( z + 秒) 2 a 2 ”+ 1 + ( z + 暑，) n 2 ”+ 2 + n 2 ”+ 3 1 t r 5 2 ”( y 2 2 “- 1 0 2 ”一1 + 材2 m + l 。+ 3 ，2 “一1 a 2 2 m 一1 + 暑，2 口+ y a 2 + a 2 t ，+ 1 + 暑，2 ”+ 2 0 + y 2 “+ 1 口2 + 可2 ”q 3 + y a a 2 + 可2 n 2 ”+ 1 + 可n 2 m + 2 ) 为了计算函数仇，的非线性度，根据非线性度的定义，首先需要知道其 w a l s h 变换的系数。实际上，先计算出其平方： 这里 ( w d 。，( a ) ) 2 =( 一1 ) 9 ( 卅| g ( m ) 桁( ( m ) a ) o ，：f 2 = ( 一1 ) 9 ( 。) + 夕( z + 掣) + 打( 分a ) = ( 一1 ) 打( 善2 ”l - ( 缈+ 二：( 可) ) = ( 一1 ) 打( l 。( 可) ) ( 1 ) 打xm l l ( 管) j y e f 2 , t z 三瓦n l i ( y 、= 可2 2 ”一1 口2 ”一1 + 可2 m + 1 a + 2 一1 n 2 2 m 一1 + y 2 a + y a 2 + 可n 2 m + 1 ， l 2 ( y ) 2 y 2 m + 2 a + y 2 m + l a 2 + y 2 m a 3 + 可3 n 2 ”+ 2 a 2 m + l + 可a 2 m + 2 ) + 入妙 由迹函数的定义和性质可得 ( 一1 ) 打( ) ：j 2 n , l i ( y ) = o ， x e f 2 , t 10 ，其他 于是代入到上式可得 ( w d 。，( a ) ) 2 = 2 n ( 一1 ) 打l 。( 3 ，) ) ：2 七， y e m 其中m = 可曰i l l ( 可) = o ) ，d i m m = 七。接下来就是求空间m 的维 一l o 3两类布尔函数的二阶非线1 峰度下界 数，也就是求线性方程组l l ( 可) = 0 在珂上解的个数。令 l ( z ) = x 2 2 r n - 1 0 2 ”一1 + x 2 m + l q + x 2 m - 10 2 2 ”一1 + z 2 0 + x a 2 十x a 2 “+ 1 = 0 ( 3 一1 ) ( 3 - 1 ) 式平方得 z 0 2 ”+ z 2 ”+ 2 d 2 + z 2 “o + x 4 a 2 + x 2 a 4 + x 2 a 2 ”舭= 0 ( 3 2 ) 不妨设z 2 ”= y ，a 2 ”= b ，代入( 3 2 ) 有 ( 3 3 ) 式2 m 次方得 z 6 + y 4 a 2 + y a + x 4 a 2 + x 2 a 4 + x 2 b 4 = 0 n + z 4 6 2 + z 6 + 可4 6 2 + 可2 6 4 + 可2 a 4 = 0 ( 3 3 ) 式与( 3 - 4 ) 式对应相加整理得 ( z + 秒) 4 ( n + 6 ) 2 + ( z + 可) 2 ( o + 6 ) 4 = 0 ( 3 3 ) 式乘( 口+ 6 ) 2 力ni - _ ( 3 5 ) 式乘a 2 就可以消去z 4 与y 4 项得到 ( 3 - 3 ) ( 3 - 4 ) ( 3 - 5 ) z 2 b 2 ( a - i - 6 ) 4 - 4 - y 2 a 2 ( n + 6 ) 4 + x b ( a + 6 ) 2 + y a ( a + 6 ) 2 = 0 ( 3 6 ) ( 3 6 ) 式平次方得 x 4 b 4 ( a + 6 ) 8 + y 4 a 4a + 6 ) 8 + x ：b 2 ( o + 6 ) 4 + y 2 a 2 ( 口+ 6 ) 4 = 0 ( 3 - 7 ) ( 3 3 ) a 4 ( a - 4 - 6 ) 8 + ( 3 7 ) x a 2 消去y 4 项 x 4 a 2 ( o + 6 ) 1 2 + x 2 a 2 ( n + 6 ) 4 ( n l o + a 2 b s + b 2 ) + x a 4 b ( a + 6 ) 8 ( 3 8 ) 式- 甲次方得 + 可2 a 4 ( o + 6 ) 4 + y a 5a + 6 ) 8 = 0 x 8 a 4a + 6 ) 2 4 + x 4 a 4 ( n + 6 ) 8 ( 0 2 0 + a 4 b 1 6 + b 4 ) + x 2 a 8 b 2 ( o + 6 ) 1 6 + 可4 a 8 ( n + 6 ) 8 + y 2 a l o ( o + 6 ) 1 6 = 0 ( 3 8 ) ( 3 - 9 ) 湖北大学硕上学位论文 ( 3 3 ) x a 8 ( o + 6 ) 8 + ( 3 - 9 ) x a 2 消去耖4 项 z 8 n 6 ( n + 6 ) 2 4 + z 4 0 6 ( o + 6 ) 1 2 ( ( n + 6 ) 1 6 + 1 ) + x 2 0 8 ( o + 6 ) 1 2 ( n 2 b 2 ( a + 6 ) 4 + 1 ) + z 口8 b ( a + 6 ) 8 + y 2 a 1 2 ( o + 6 ) 1 6 + y a 9 ( 口+ 6 ) 8 = 0 ( 3 1 0 ) ( 3 8 ) x a l 2 ( o + 6 ) 1 6 + ( 3 1 0 ) x a 4 ( o + 6 ) 4 消去可2 项 z 8 0 1 0 ( 口+ 6 ) 2 8 + x 4 0 1 0 ( 口+ 6 ) 1 6 ( 6 4 ( o + 6 ) 1 2 + 1 ) + x 2 n 1 2 ( n + 6 ) 1 6 ( 0 4 ( o + 6 ) 1 2 + 1 ) + z a l 2 b ( a + 6 ) 1 2 ( c t 4 ( n + 6 ) 1 2 + 1 ) + y a l 3 ( o + 6 ) 1 2 ( 口4 ( o + 6 ) 1 2 + 1 ) = 0 ( 3 - 1 1 ) ( 3 11 ) 式平次方得 z 1 6 0 2 0 ( 口+ 6 ) 5 6 + z 8 0 2 0 ( n 十6 ) 3 2 ( 6 8 ( o + 6 ) 2 4 + 1 ) + z 4 0 2 4 ( o + 6 ) 3 2 ( 0 8 ( o + 6 ) 2 4 + 1 ) + z 2 0 2 4 b 2 ( o + 6 ) 2 4 ( n 8 ( o + 6 ) 2 4 + 1 ) + y 2 n 2 6 ( o + 6 ) 2 4 ( c t 8 ( n + 6 ) 2 4 + 1 ) = 0 ( 3 1 2 ) ( 3 - 8 ) x a 2 6 ( n + 6 ) 2 4 ( 0 8 ( n + 6 ) 2 4 + 1 ) + ( 3 - 1 2 ) x a 4 ( o + 6 ) 4 消去可2 项 z 1 6 n 2 4 ( n + 6 ) 6 0 + x 8 0 2 4 ( o + 6 ) 2 4 ( b s ( a + 6 ) 2 4 + 1 ) + z 4 n 2 8 ( n + 6 ) 6 8 + x 2 0 3 0 ( o + 6 ) 3 6 ( n 8 ( o + 6 ) 2 4 + 1 ) ( 3 1 3 ) + z 0 3 0 b ( a + 6 ) 3 2 ( n 8 ( o + 6 ) 2 4 + 1 ) + y a 3 1 + 6 ) 3 2 ( n 8 ( o + 6 ) 2 4 + 1 ) =