（基础数学专业论文）布尔函数的代数免疫度与非线性度.pdf

摘要 布尔函数在序列密码，分组密码和h a s h 函数设计与分析中具有广泛应用。代数免疫度和 非线性度是衡量布尔函数安全性的重要指标。在本文中，首先介绍了具有最大代数免疫度的布 尔函数的结构，并对具有次最大代数免疫度的布尔函数的构造和性质做了细致研究。然后研究 了b e n t 函数的结构，性质和构造。本文主要结果： ( 1 ) ：研究了通过有限域的方法，即通过毋n 的一个本原元的一些连续次幂作为布尔函数的 支集构造了一类新的具有次最大代数免疫度，且非线性度较高的布尔函数。 ( 2 ) ：给出了b e n t 函数的一般构造方法，并且从理论上证明了当布尔函数的支集是2 一 g r o u p f 多的一个( 2 “：k t ) 一一( 这里k , t 为正整数佗为一个正偶数) 差集时，且当k 兰2 ”1 时， 布尔函数是一个b e n t 函数，且具有最大代数免疫度。 关键词：最大代数免疫度；次最大代数免疫度；差集；非线性度；b e n t 函数 a b s t r a c t b o o l e a nf u n c t i o n sp l a yv e r yi m p o r t a n tr o l e si nt h ed e s i g na n da n a l y s i so fb l o c kc i p h e r s ，s t r e a m c i p h e r sa n dh a s hf u n c t i o n s a l g e b r a i ci m m u n i t y ，n o n l i n e a r i t ya n dc o r r e l a t i o n a li m m u n i t y , a r ei m p o r t a n t c r y p t o g r a p h i cp r o p e r t i e so fb o o l e a nf u n c t i o n s t h i st h e s i sf i r s t l yi n v e s t i g a t e st h ep r o p e r t i e sa n dt h e c o n s t r u c t i o n so ft h eb o o l e a nf u n c t i o n sw i t hm a x i m u ma l g e b r a i ci m m u n i t y , t h e ns t u d i e st h ep r o p e r t i e s a n dt h ec o n s t r u c t i o n so fb e n tf u n c t i o n s t h em a i nc o n t e n t sa n df r u i t so ft h i st h e s i sa r eo u t l i n e da s f o l l o w s ： 1 an e wm e t h o dt oc o n s t r u c tt h eb o o l e a nf u n c t i o n sw i t hs u b - o p t i m a la l g e b r a i ci m m u n i t ya n dw h o s e s u p p o r ti sm a d eo fc o n s e c u t i v ep o w e r so fap r i m i t i v ee l e m e n to ft h ef i e l df 2 n t h en o n l i n e a r i t yo f t h en e wb o o l e a nf u n c t i o n si sa l s oh i g h ； 2 t h ec o m m o nm e t h o dt oc o n s t r u c tb e n tf u n c t i o n si sg i v e n i t sp r o v e dt h a tw h e nt h es u p p o r to f b o o l e a nf u n c t i o n si sa ( 2 n ，k ，) 一( 七，ta r ep o s i t i v ei n t e g e r s ，佗i sap o s i t i v ee v e ni n t e g e r ) i n2 - g r o u p 毋a n dk 2 n - 1 t h eb o o l e a nf u n c t i o n sa r eb e n tf u n c t i o n sa n da r em a if u n c t i o n s t e x t b f k e ) w c o r d s ：m a x i m u ma l g e b r a i ci m m u n i t y ，s u b - o p t i m a la l g e b r a i ci m m u n i t y ，d i f f e r e n c es e t ：n o n l i n e a x i w , b e n tf u n c t i o n 1 n 1j11j1 11 摘要 a b s t r a c t 日u吾 目录 第一章基本概念和预备知识 1 1 布尔函数的基本概念和性质 1 2 r s 码的介绍 第二章具有最大代数免疫度和次最大代数免疫度的布尔函数及构造 2 1 符号 2 2 具有最大代数免疫度的布尔函数 2 3 具有最大代数免疫度的对称布尔函数 2 4 具有最大代数免疫度的2 m 元对称布尔函数 2 5 具有次最大代数免疫度及较高非线度的布尔函数的构造 2 6 关于构造的布尔函数的一些数据 第三章b e n t 函数及其构造 3 1 b e n t 函数的结构分析。 3 2 一类b e n t 函数的一种新的构造法 参考文献 致谢 ； m 1 7 7 加 墙 坞 墙 竭 幻 卯 四 卵 目录 - - 一 刖吾 首先介绍一下选题背景和意义： 密码学是一门既古老又年轻的学科，其历史可以追溯到几千年以前，但2 0 世纪四五十年 代才开始作为一门学科来进行研究。当今，密码学不仅应用于军事、政治和外交，还广泛 应用于电子政务、商务活动以及人们的日常生活中。1 9 9 7 年4 月，美国国家标准技术研究院 ( n i s t ) 为了履行其法定职责，发起了一场推选用于保护敏感的联邦信息的对称密码算法活 动。1 9 9 8 年8 月，n i s t 宣布接受十五个候选分组密码算法并提请全世界密码研究界协助分析这 些候选算法，包括对每个算法的安全性和效率特性进行初步检验。n i s t 考察了这些初步的研究 结果，选定m a r s ，r c 6 ，r i j n d a e l ，s e r p e n t 和t w o f i s h 等五个分组密码算法作为参加决赛的算法。经 公众对决赛算法进行进一步的分析和评论，2 0 0 0 年1 0 月，n i s t 决定推荐r i j n d a e l 作为高级加密标 准a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 。继美国推出a e s 计划以后，欧洲于2 0 0 0 年1 月启动了新 欧洲签名，完整性和加密计划一n e s s i e ( n e we u r o p e a ns c h e m e sf o rs i g n a t u r e s ，a n de n c r y p t i o n ) 计 划，以适应2 1 世纪信息安全发展的全面需求。该计划为期三年，投资2 6 4 万元，主要目的就是通过 公开征集和进行公开的透明的测试，评估，提出一套高效的密码标准，以保持欧洲工业界在密码 学研究领域的领先地位。和a e s 相比，n e s s i e 涉及的范同更广，这套标准不但有分组密码，还包 括序列密码，公钥密码，认证码，杂凑函数和数字签名等标准。2 0 0 1 年底，n e s s i e 工作组在十七 种候选的分组密码算法中，选定了i d e a ，k h a z a ，( i ，m i s t y l ，c a m e l l i a ，s h a c a l ，r c 6 和s a f e r + + 等 七种分组密码算法为分组密码的决赛算法，在六种候选的序列密码算法中，选定了b m g l ，s n o w ，s o b e r - t 1 6 ，和s o b e r - t 3 2 等四种序列密码算法作为序列密码的决赛算法。2 0 0 3 年2 月，n e s s i e 工作公 布了包括分组密码，公钥密码，认证码，杂凑函数和数字签名等在内的十七个标准算法，其 中m i s t y l ，c a m e l l i a 和s h a c a l - - - - 个分组密码算法联同a e s 一起作为欧洲新世纪的分组密码标 准算法。遗憾的是，候选的四个密码算法由于没有达到人们的预期的安全要求，没有一个成为 欧洲新世纪的序列密码标准算法。 2 0 0 4 年2 月1 日，欧洲i s t 基金出台j e c r y p t ( e u r o p e a nn e t w o r ko fe x c e l l e n c ef o rc r y p t o l o g y ) 计划，这个为期四年的项目是n e s s i ( n e we u r o p e a ns c h e m e sf o rs i g n a t u r e s ，i n t e g r i t y , a n de n - c r y p t i o n ) 计划结束后欧洲启动的一个更大的信息安全研究项目项目，基金预算为5 6 0 万欧元，远 多于n e s s i e 的2 6 4 万欧元的投入，其目标是促进欧洲信息安全研究人员在密码学和数字水印研 究上的交流，促进学术界和工业界的持久合作。为了达到这个目标，欧洲3 2 个在信息安全研究领 域领先的高校实验室和公司一起合作建立了5 个虚拟实验室作为不同方向的研究核心。其中虚 拟实验室s t v l 是为了便于欧洲在对称密码的研究而建立。e c r y p t 计划的一个重要任务是征集 欧洲新世纪的流密码标准算法。2 0 0 5 年4 月，e c r y p t 宣布接受3 4 个候选流密码算法，并提请全 世界密码研究界协助分析这些候选算法，包括对每个算法的安全性和效率特性进行初步检验。 经过三轮筛选，2 0 0 8 年9 月8 日公布了最后结果，选定了h c 一1 2 8 、r a b b i t 、s a l s a 2 0 1 2 、s o s e m a n u k 四 个面向软件的流密码算法，g r a i nv l 、m i c k e yv 2 、t r i v i u m 三个面向硬件的流密码算法。由此 可见，流密码的设计与分析是目前密码学领域的前沿热点问题。 布尔函数作为流密码，序列密码，分组密码和h a s h 函数中的重要组件，其密码学性质的好 坏直接关系到密码体制的安全制。序列密码，分组密码和h a s h 函数的设计都是建立在s h a n n o n 引 2前言 入的两个基本准则一混淆和扩散一之上的。混淆旨在消除密码算法任何可能的内在代数结构，它 和算法所使用布尔函数的复杂度密切相关。扩散旨在把输入数据或是密钥的最微小变化影响 到所有输出比特上。这两条准则提出至今已有半个世纪之久。从那时开始，对于各种密码系统 提出的许多攻击一一再验证这两条准则的正确性。对于各种密码系统的已知攻击导致了其所 使用的布尔函数必须满足的密码学指标。更准确地说，密码系统对于已知攻击的抵抗性是可以 由它们所使用的布尔函数的这些密码学指标所衡量的，密码中使用函数的设计必须同时考虑 这些不同的指标。把布尔函数理论研究和密码算法设计联系起来，是一件很重要很有意义的工 作。 目前布尔函数的密码学指标主要有：平衡性，非线性度，差分均匀度，相关免疫度和代数 免疫度。这些密码学指标跟密码体制攻击方法密切相关，非线性度是针对线性攻击提出的，差 分均匀度是针对差分密码攻击提出的，相关免疫度是针对相关攻击提出的，代数免疫度是针对 代数攻击提出的。研究布尔函数的密码学指标对于密码体制的安全性具有十分重要的意义。 再者，来介绍国内外相关研究和现状： 布尔函数的非线性度方面： 线性密码攻击是一种经典的分组密码攻击方法。线性密码攻击的基本思想是找一个给定密 码算法的有效的线性近似表达式来破译密码系统。线性密码攻击为布尔函数的非线性度赋予了 新的密码学意义，推进了对它们的研究。抵抗线性攻击的布尔函数必须有高的非线性度，它由函 数的最大w a l s h 谱值决定，最大的w a l s h 谱值越小，则非线性度【3 7 】越高。由p a r s e v a l 公式，我们知 道这个值至少为2 一号，当n 为偶数时，这个下界可以达到的这类函数称为b e n t 函数。1 9 8 7 年丁存 生等提出了布尔函数的稳定性的概念【5 2 】，后来发现这利- 稳定性函数就是r o t h a u s 于1 9 7 6 年提出 的b e n t 函数【4 4 】。以b e n t 函数为非线性度滤波函数和非线性组合函数的流密码能抵抗最佳仿射逼 近攻击。一直以来对b e n t 函数的构造是研究者所关心的问题，其中分为直接构造方法和间接构 造方法。直接构造方法有m ( m a i o r a n a - m a c f a r l a n d ) 类【3 9 】，p s ( p a r t i a ls p r e a d ) 类和把它转化 为域上函数的求解方法。关于域上函数的求解方法：二元域上的n 维向量空间和有限域g f ( 2 n ) 是 等价的，因此布尔函数的研究相当于有限域上函数的研究。k k h o o ，g u a n gg o n g ，d r s t i s o n 2 2 】为 有限域上的二次b e n t 函数和s e m i b e n t 函数给出了新的刻画，另外h d o b b e r t i o n 等人 2 0 】用n i h o 幂 函数给出新的b e n t 函数的构造。在文献【2 1 】j 【4 4 给出了两个b e n t 函数的和仍是一个b e n t 函数的间 接构造方法，a d a m s 和t a v a r e s 【1 2 】以b e n t 特征序列的形式给出了一类新的b e n t 函数的构造。 布尔函数的相关免疫度方面： s i e g e n t h a l e r 在文【4 5 】中对于基于线性移位寄存器的组合流密码系统提出了一种被称为“分 别征服“的攻击方法，即后来的相关攻击。该攻击后来被人们不断提升并推广到基于线性移位 寄存器的滤波流密码系统。相关攻击的基本思想是考察线性移位寄存器和密钥流序列的相关 性，相关性越高，越容易攻击。相关攻击的发展导致了布尔函数相关免疫度1 4 6 的定义和人们对 其的深入研究。特别是，构造具有高非线性度和高代数次数的相关免疫函数 3 4 , 3 7 , 3 8 , 4 3 , 4 8 , 4 9 , 5 0 引 起了国内外密码学者的关注。最近，其中的一种构造方法【3 4 , 3 7 ，3 8 通过修改一个b e n t 函数的部分 输出点来构造高非线度的l 阶弹性函数即相关免疫函数。m a i t y 等在文【37 】中给出了一个b e n t 函 数至少修改多少个输出点才能得到一个弹性函数的下界，并在文【3 8 】巾进一步给出了求解一个 更好的下界的算法，并证明了新的下界对小于等于1 4 个变元的情形都是紧的，并且在文【3 8 】中主 前言3 要考虑通过修改m a i o r a n a - m c f a r l a n d 型的b e n t 函数来构造具有1 阶弹性函数，它表明与b e n t 函数 的距离最小的那些弹性函数具有非常好的非线性度。 布尔函数的代数免疫度方面： 最近几年，出现了一种新的分析手段代数攻击( a l g e b r a i ca t t a c k ) 。代数攻击最初是在 分析“h i d d e nf i e l de q u a t i o n ”( h f e ) 公钥密码系统的基础展而来的。c o u r t o i s 等通过分析找出 了h f e 公钥密码系统中存在多余的多元等式，从而引入了代数攻击。这是h f e 设计者所没有考 虑到的。 代数攻击首先应用在公开密钥密码系统( h f e ) 和分组密码( a e s ) ，随后应用于流密码t o y o c i y p t 3 6 ，1 0 的 分析中，后来又扩展到对l i l i - 1 2 8 2 ，1 0 的分析。这种攻击非常有效。c o u r t o i s 等 1 0 ，1 1 ，3 3 对不带记 忆的线性反馈流密码的代数攻击做了研究，并且总结了攻击有效的方法。早些时候，带记忆部 分的流密码被认为可以更好的抵抗此类攻击，但是不久一些研究表明即使是这样的情况，流密 码仍有可能受到攻击 1 。 代数攻击主要对基于线性反馈移位寄存器( l f s r ) 的流密码构成威胁。基于l f s r 的流密码 包括若干l f s r 和一个非线性滤波器。其中，设k = ( k 1 ，k 2 ，k n ) 为初始密钥，l 为线性反馈移 位寄存器，为非线性滤波函数即布尔函数，b t + l 为t + 1 时刻输出的密钥流比特。由这种流密码 的结构可知，下面的方程组成立： b o = f ( k l ，k 2 ，k n ) b l = f ( l ( k l ，k 2 ，k n ) ) b 2 = f ( l 2 ( 昆1 ，惫2 ，k n ) ) b t = f ( l 。( k l ，k 2 ，k ) ) 因上面的方程组中只有k = ( k 1 ，k 2 ，k ) 未知，如果有m 个( t ，b t ) 已知，故只需求解一个含m 个 高次方程的关于佗个未知元的方程组来恢复初始密钥k 。这就是代数攻击的主要思想。也就是 建立起初始密钥和输出密钥流比特之间的代数方程组，然后运用线性化手段来解方程获得秘 密的初始密钥。如何抵抗代数攻击至今仍是一个公开问题。 方程组的次数是d e g ( f ) ，方程的个数比未知元多，即该方程组是超定的。方程组存在唯一 解。d e g ( f ) 越大，求解方程组越难。c o u r t o i s 和m e i e r 给出了代数攻击的猜想 1 0 】。如果存在非零的 布尔函数9 ( z ) 与低次数的布尔函数h ( z ) 使得 g ( x ) f ( x ) = ( z ) ， 则 g ( l 。( k l ，k 2 ，k n ) ) ，( l 。( k l ，k 2 ，k n ) = b i g ( l 。( k l ，k 2 ，一，k ) ) ， h ( l 。( k l ，k 2 ，七n ) ) = b i g ( l 2 ( 七1 ，k 2 ，忌。) ) ， ( 2 ) 如果h ( z ) 有较低的次数，则可以利用方程组( 2 ) 得到一个次数较低的子方程组。从而，代数攻击 成功。随后，m e i e r 在文【3 3 里证明了把这个猜想归纳为寻找布尔函数的零化子。也就是，代数攻 4前言 击成功的关键是找至u f ( x ) 或者f ( x ) + l 的最低次数的零化子。这个最低的次数称为，( z ) 的代数 免疫度。 基于l f s r 的流密码具有简洁性的特点，而且适当选择l f s r 和布尔函数可使密钥流序列具 有良好的统计特性和高的线性复杂度，因而它在现实生活中被广泛使用，其安全性能也一直 被予以很大的关注。为了抵抗许多己知对流密码的有效攻击，要求布尔函数具有平衡性、高代 数次数、高非线性度等密码学性质。然而代数攻击的提出又要求布尔函数具有新的密码学性 质高代数免疫度。代数攻击通过求解超定的多元方程组来获得密钥。 代数免疫用来衡量布尔函数抵抗代数攻击能力，为了在一定程度上抵抗代数攻击，需要设 计代数免疫度高的布尔函数。c o u r t o i s 在 1 0 】里证明了n 元布尔函数的代数免疫度上界疋1 百n 。代 数免疫度达到此上界的布尔函数称为具有最优代数免疫度( m a x i m u ma l g e b r a i ci m m u n i t y ) 的布尔 函数，简称为m a i 函数。m a i 函数是密码学中一类非常重要的布尔函数，研究这类函数具有非 常重要的意义。 m a i 函数的性质与构造是密码学者们非常关注的研究课题。l o b a n o v 在【3 1 】里给出了函数的 非线性度下确界。m a i 函数最早的两个构造出现在 1 4 1 5 中。d m a i 用迭代方法构造了m a i 函数【1 4 】， 并从零化子的基本思想出发，首次提出了m a i 函数的一个一般构造思想，然后研究了所构造 函数的代数次数、非线性度等密码学性质【1 5 】。b r a e k e n 在【3 】里、刘峰等【2 9 】、李娜等【2 4 】、屈龙江 等 4 0 4 1 】研究了对称m a i 函数的构造。张文英等【5 1 】构造了若干类特殊的m a i 函数并对其分别进行 了计数。c a r l e t 在【7 】里利用仿射平面理论提出了两个构造平衡m a i 函数的算法。屈龙江等 2 6 4 2 】利 用矩阵理论进一步刻画了m a i 函数的结构，给出了一类构造方法。李娜和戚文峰 2 5 ，2 7 ，2 8 进一步 研究了奇数变元m a i 函数的构造，证明了一个奇数变元m a i 函数唯一对应矩阵m ( n ) 的一个可 逆子矩阵，将奇数变元m a i 函数的构造转化为寻找矩阵m ( n ) 的一个可逆子矩阵的问题，简化 了m a i 函数的构造问题。研究矩阵m ( n ) 的性质，可以更清楚m a i 函数的结构，以方便构造m a i 函 数。目前，研究矩阵m ( n ) 的性质的文献较少。文献 2 8 】研究了该矩阵的性质，给出了三类奇数 变元m a i 函数。 在2 0 0 8 年亚洲密码学年会上，c a r l e t 和冯克勤【9 】利用有限域理论提出了一类具有最优代数 次数和高非线性度的平衡m a i 函数，并通过实验说明了该类函数对快速代数攻击( f a s ta l g e b r a i c a t t a c k s ) 也具有良好的抵抗性质。这是目前己知的密码学性质最好最全面的一类m a i 函数。但由 于该类函数是n 1 次平衡布尔函数，该类函数不是弹性函数f 4 】，不能抵抗相关攻击。 c a r l e t 和冯克勤同时在 9 】中指出了通过有限域的方法可以构造一类具有次最大代数免疫度 的布尔函数，并指出具有次最大代数免疫度的布尔函数的结构会比具有最大代数免疫度的布 尔函数的结构简单一些，会比具有最大代数免疫度的布尔函数要好。 本文共分为三章，编排如下： 第一章：主要介绍了布尔函数的代数正规型和单变量多项式及布尔函数的密码学性质，并 对r s 码的构造及r s 码的零点作了一些介绍，是本文的理论基础。 第二章：介绍了一些具有最大代数免疫度的布尔函数的结构及通过迭代法和有限域理论 构造具有最大代数免疫度的布尔函数，并研究了一种新的具有次最大代数免疫度的布尔函数 的构造方法及以及所构造函数的代数次数、非线性度等其它密码学性质。 共分为以下六节： 前言 5 第1 节：约定了的一些相关数学符号。 第2 节：给出了具有最大代数免疫度的布尔函数f n ( z ) 的表达式和由矩阵理论推出的当一个 函数是具有最大代数免疫度的布尔函数时需满足的充要条件，并详细介绍了通过迭代法构造 具有最大代数免疫度的2 惫元布尔函数咖2 七，并提出了当毋2 k 满足咖2 k p 2 k 时，可以构造一类具 有最大代数免疫度的2 七+ 1 元布尔函数。还介绍了通过有限域理论构造具有最大代数免疫度的 平衡布尔函数和该类布尔函数的代数次数。 第3 节：介绍了具有最大代数免疫度的对称布尔函数的结构，并证明了具有最大代数免疫 度的奇数变元对称布尔函数有且仅有两个。 第4 节：介绍了2 m 元对称布尔函数具有最大代数免疫度的必要条件。 第5 节：通过域f 2 。的一个本原元的一些连续次幂作为布尔函数的支集构造了一类新的具有 次最大代数免疫度，且非线性度较高的布尔函数。 第6 节：给出了与第5 节中构造的布尔函数相关的一些数据。 第三章：主要对b e n t 函数的结构做了分析，并介绍了b e n t 函数的一般构造方法。通过b e n t 函 数的定义，域f 2 。的一个本原元的一些连续次幂作为布尔函数的支集构造了一类新的具有最大 代数免疫度的b e n t 函数。 本章共分为以下两节： 第1 节：给出了布尔函数的w a l s h 循环谱的概率表达式，布尔函数的小项表示，及单项式 布尔函数的相应的w a l s h 循环谱表示，进而给出了当知道一个布尔函数的小项表示时，相应 的w a l s h 循环谱表达式，及该布尔函数是b e n t 函数时的允要条件。 第2 节：通过b e n t 函数的定义，由域f 2 。的一个本原元的一些连续次幂作为布尔函数的支集 构造了一类新的具有最大代数免疫度的b e n t 函数。 6前言 第一章基本概念和预备知识 1 1布尔函数的基本概念和性质 本节内容可以在关于布尔函数的参考书【8 ，5 4 】中找到。 在本文中，我们固定下面的记号：佗：任意的正整数； d ：任意的正整数； k ：任意的小于等于犁的正整数。 定义1 1 1 设昭为f 2 上的一个n 维向量空间，一个n 元布尔函数可以看作是从域巧到局 的一个映射，也可以看作是从域f 2 。到f 2 的一个映射。 记全体n 元布尔函数为b 。任意一个n 元布尔函数厂都可以用长为2 n 的真值表 f = f ( o ，0 ，o ) ，f ( 1 ，0 ，o ) ，f ( 1 ，1 ，1 ) 唯一表示。j f 也可以用f 2 上的n 元多项式 f ( x l ，x 2 ，z n ) = o o + n i x i + a i j x i x j + + a 1 2 n x l 2 n 1 i n1 d ，则耋o ( ? ) w t ( f ) 留_ 1 ( ：) 。 c o u r t o i s ：在 10 】里证明了亿元布尔函数的代数免疫上界是墨 。 定理i i 1 0 【1 0 】设，b 。，则a j ( 厂) 号 。 证明：反证法。假设a i ( f ) 量1 。令d = 罟1 ，由引理有 这与竹一d 一1 d 矛盾。口 定义1 1 1 1 设，b n ，若- a i ( f ) = 鸶 ，称厂为具有最优代数免疫度的布尔函数，简称为m ，函 数。 为了抵抗最佳仿射逼近攻击、快速相关攻击5 等，密码学巾的布尔函数必须具有高非线 性度。 定义1 1 1 2 布尔函数厂的非线性度川( 厂) 定义为，和所有仿射函数的最小汉明距离，即 n f ( ，) = 2 n - 1 _ 互1 躅i ( 叫) i 定义1 1 1 3 任意布尔函数厂的非线性度佗f ( ，) 2 ”一2 号。非线性度达到这个上界的布尔函数 称为b e n t 函数。这时，n 必须是偶数。 暖 小铷 一 d“ u 一 暖 d 铷 旺1 布尔函数的基本概念和性质 9 定义1 1 1 4 设g 为一个口阶群，其幺元记为e ，当g 为磊的加群时，设d = 口1 ，0 2 ，n 七】 ( a g ) ，且d 为g 一个子集，如果对于任一d g ，d e , d 恰有入种方式表为 d 三a i a j ( m o d v l 这里i 和j 都为大于等于1 小于等于k 且不相等的整数，这时称d 为群的一个( ，k ，a ) 一群差 集。 这里给b e n t 函数的另外一个定义： 定义1 1 1 5 任意一个布尔函数，如果布尔函数f 的支集是一个2 一舻。叩珂的一个( 2 n ，k ，t ) 偿里后，为正整数，n 为一个正偶数差集时，是一个b e n t 函数。 为了抵抗相关攻击【4 】，密码学中的布尔函数必须具有相关免疫性。 定义1 1 1 6 设，( z ) 为一个n 元布尔函数，整数1 m n ，如果对任意1 砌( 叫) m ：吩( 叫) = 0 ，则称，( z ) 是一个m 阶相关免疫函数。 定义1 1 1 7 设，( z ) 为一个礼元布尔函数，整数l m 礼，如果对任意o 叫( 叫) m ：晰( 叫) = 0 ，则称厂( z ) 是一个仇弹性函数。 布尔函数的代数次数与相关免疫性存在相互制约的关系【4 】：如果厂是一个m 阶相关免疫函数， 贝j j d e g ( f ) + m 扎。如果厂是一个m 一弹性函数，1 m 礼一2 ，贝j j d e g ( f ) + m 扎一1 。布尔函数 的代数免疫度和非线性度之间也有一定的关系：l o b a n o v 在 2 7 】给出了布尔函数的代数免疫度与 非线性度的紧界。并给出了一个平衡布尔函数厶加这一类平衡布尔函数的a i ( f ) = 七时，非线 性度为2 旨( n 了1 ) 。 定理1 1 1 8 【2 7 设，是n 元布尔函数，a i ( f ) = 七，则 州舵2 一n - k i = k - 1 ( 礼了1 ) = 2 登i = 0 ( 几a 、 ， 特别地，如果，是n 元舰4 j 函数，则 当n 是奇数时，n l ( f ) 2 ”一( n 犁- - 1 ，o ， 2 当n 是偶数时，n l ( f ) 2 ”1 一( ；) 。 定理1 1 1 9 【27 】设厶是n 元布尔函数：且 1 0 ， 如果w t ( x 1 ，x 2 ，z ) n 一七； i 钆否则 如果a ，( ，n ，南) = k ，那么n t ( a ，七) = 2 一n - 。k - 。2 ( n 了1 ) 。 1 0第一章基本概念和预备知识 下面介绍一类特殊的布尔函数：对称布尔函数。设s 玩表示所有含n 个变元z 1 ，z 2 ，z 。 的对称布尔函数所构成的集合：一个对称布尔函数，s b 。可以通过一个n + 1 维向量表示： 巧= ( v a o ) ，u a i ) ，巧( n ) ) 刀+ 1 其中巧( i ) = ，( 。) ，z 巧，且其汉明重量为w t ( x ) = i ，另一方面，可表示为 其中 a ，( ) f 2 ，卵 是关于n 个变元z 1 ，z 2 ，z 。的第i 个初等对称布尔函数，于是一个对称布尔函数，s 玩又 可以通过另一个佗+ 1 维向量表示： 入，= ( a ，( o ) ，i i ( i ) ，入，( 礼) ) ，? + 1 关于对称布尔函数的代数次数在文献【5 3 有如下结论： 引理1 1 2 0 对任意正整数k ，至少存在一个2 k + 1 元的非零对称布尔函数g 满足 j ( 1 ) d e g ( g ) 艮； 【( 2 ) 嵋( o ) = 嵋( 南+ 1 ) = k ( 七+ 2 ) = = k ( 2 k ) = 0 总之，为了抵抗许多己知对密码体制的有效攻击，要求布尔函数具有平衡性、高代数次数、 高非线性度、相关免疫性等密码学性质。 1 2r s 码的介绍 本节主要介绍y n s 码的定义和r s 码的零点概念：( 本节内容在参考书【5 4 中可以找到) 设r 是一个大于1 的整数。再设q 是域f 2 ，的一个本原元，那么，j = 0 ，1 ，2 ，2 一2 ，就是 f 2 ，中全部不等于0 的元素。将他们表示成a o ，q 1 ，q r 一1 的线性组合 这2 7 1 个列向量两两相异。将这2 r 一1 个列向量按j = 0 ，1 ，2 ，2 r 一2 为序排列成f 2 上的一 个rx ( 2 7 1 ) 矩阵 竹0 口 ， 入 n 瑚 = n z 2 zz ， 2 一 r 2210 = 一叼 0 “枷 = 旺2r s 码的介绍 日隹蔓。 那么r n n 后( 日) = r ，而以日为校验矩阵的二元( 2 7 1 ，2 一1 一r ) 线性码就叫二元( 2 r 一1 ，2 r 一 1 一r ) h a m m i n g 码。 我们总是把日简记为 h = ( 1 ，口，q 2 ，0 e 2 r - 2 ) ， 其中代表f 2 ，中的r 维列向量 当把二元h a m m i n g 码作如下推广： 定义1 2 1 设d 为整数，而1 d n ，我们构造f 2 上的一个7 ( d 一1 ) ( 2 r 一1 ) 矩阵 其中代表f 2 r 中的r 维列向量( o 町，a l j ，n 巧) ，0 j 2 7 2 。我们把这个矩阵记作日。一般 说来，日的秩小于r ( d 一1 ) 。r l ( f 2 ) 中所有适合条件 h c = 0 的向量c = ( c o ，c 1 ，c 2 ，c 2 - 2 ) 组成一个予空间。我们把这个子空间叫做设计距离为d 的二元本 原b c h ；玛。 且有如下定理： 定理1 2 2 设f 为一个有限域，f q 是它一个含口个元素的子域，而q 是f 4 中任一元素。假定q 在f ，中 的阶是f ，那么a c d ( q ，f ) = 1 ，而且( q ) 2 z 。再假定( g ) z 在z ；中的阶是m ，那么q 在f q 上的极小多 项式，( z ) 就是m 次的。 我们再把二元本原b c h 码推广成q 元本原b c h 码： 、l-、 以 c i | l 弘 = o o n 即 眈 您 毖 一 。 口 n 叮u； 以 o o 即 q 扯弘 一严器吁竹矿胡一一 酗” j如 口舻扩 矿 1 2第一章基本概念和预备知识 设q 为一个素数的幂，几是与q 互素的一个大于l 的整数。假定q 在群绨中的阶为r 。设q 是域 f 的一个n 阶元。因g 在群露中的阶是r ，所以根据上定理知q 在域上的多项式就是r 次的。这 样1 ，o l ，q 2 ，o t r 一1 就是域f 口r 在f 口上的组基。于是a j ( o j n 一1 ) 都可以唯一地表示成他们 的线性组合，而系数属于n ： r 一1 o = fa i j c e ， i = 0 这样每个凸：j 都唯一确定r 上的一个r 维列向量： o ，ha 叮，0 1 j ，a r - l , j ) 7 设d 是一个整数，而1 0 ，i o 时，酩= i m o d 2 。为了理解上述中的迭代，举一些例子： 圣k = 圣2 七一2 i i 西5 七一2 i 1 圣1 七一2 i | 圣；芒2 ； 西1 一2 = 西! 一4 i i 圣氛一4 i i 圣；一4 | | 西2 k - 4 ； 西；一4 = 西；一6 i i 圣i 一6 圣氛一6 i i 西! 一6 引理2 2 4 【1 3 】假设西2 i b 2 i 由上述构造得到，当 0 i 七，a i ( f ) = i 如果对于0 i 忌，j 0 ，存在 g a n ( ： ) ，h a n ( 西j 2 + 1 ) 且d e g ( g + h ) i 一2 + j ，那么g = h 。 引理2 2 5 【1 3 】设圣2 i b 2 i ，由上述构造生成，对于 0 i 后，a ，( 厂) = i ， 如果0 i 七，j 0 ，存在g a ( 鸱t ) na ( 呜于1 ) ，且d e g ( g ) i + 歹，那么9 = 0 。 定理2 2 6 【1 3 】由上述构造的布尔函数2 ，有a j ( 2 七) = k ，( k o ) 。 定义2 2 7 【1 9 设，b 2 k ，且a i ( f ) = 南，设g ，h s 泐 j 为，和1 + ，的代数次数为k 的零化子， 且对任意的g 和h 有d e g ( g + ) 艮成立。记这样的，的集合p 2 。 弓i 理2 2 8 【19 】设厂p 2 ，贝4a i ( x 2 七+ 1 + ，) = 后+ 1 。 这时，我们可以得到一个具有最大代数免疫度的奇数元布尔函数： 定理2 2 9 对于上述构造的圣2 七t 2 七时，a i ( 垂2 k + x 2 k + 1 ) = k + 1 。 下面再介绍一种由有限域理论所构造的具有最大代数免疫度的布尔函数 2 2 具有最大代数免疫度的布尔函数 定理2 2 1 0 9 】 设整数n22 ，q 为f 2 。的本原元。支撑集为 o ，1 ，q ，q 2 ，0 e 2 n - l - 2 】l 的布尔函数是m j 函数。 将其推广到一般情形。下面，我们给出平衡的m 灿函数的一般结果和证明。 定理2 2 1 1 【5 8 】设整数n 2 ，q 为f 2 。的本原元。设，是几元布尔函数，如果 i f = q ，q 件1 ，g