（概率论与数理统计专业论文）高阶非线性resilient布尔函数与多值函数的谱性质.pdf

hi g h l y n o n l i n e a r t - r e s i l i e n t f u n c t i o n s a n d s p e c t r a l p r o p e r t y o f t h e mu l t i v a l u e d f u n c t i o n s j i a n g h a i l i n g c o l l e g e o f ma t h e m a t i c a l s c i e n c e s , n a n k a i u n i v e r s i t y ab s t r a c t t h e s e c u r i t y o f s t r e a m c y p h e r c r y p t o s y s t e m s d e p e n d o n t h e c o m - b i n e d f u n c t i o n s i n t h e k e y s t r e a m g e n e r a t o r s . t h e s e f u n c t i o n s m u s t h a v e h i g h n o n l i n e a r i t y a n d r e s i l i e n t t o r e s is t p o s s i b l e a t t r a c k s . h e r e w e s h o w a n e w d e s i g n m e t h o d f o r h i g h n o n l i n e a r a n d r e s i l i e n t b o o l e a n f u n c t i o n s . o u r m e t h o d g i v e s h i g h e r l o w b o u n d s o f n o n l i n e a r i t y t h a n r e f e r e n c e ( 7 . b e s i d e s , w e g i v e t h e n e c e s s a r y a n d s u ff i c i e n t, c o n d i t i o n s o f t h ( c h r e s t e n s o n c i r c le s p e c t r u m o f t h e s u m f u n c t i o n f o r t w o m u l t i - v a l u e d f u n c t i o n s e q u a l s t h e s u m o f t h e s e p a r a t e c h r e s t e n s o n c i r c l e s p e c t r u m o f t h e s e t wo mu l t i - v a l u e d f u n c t i o n s . an d t h e s u ff i c i e n t c o n d i t i o n s o f t h e c h r e s t e n s o n l i n e a r s p e c t r u m o f t h e s u m f u n c t i o n f o r t w o m u l t i - v a l u e d f u n c t i o n s e q u a l s t h e s u m o f t h e s e p a r a t e c h r e s t e n s o n l i n e a r s p e c t r u m o f t h e s e t w o mu l t i - v a l u e d f u n c t i o n s . ke y w o r d s : r e s i l i e n t f u n c t i o n s , p r o p a g a t i o n c r i t e r i o n , n o n l i n e a r i t y , p a r t i a l l y b e n t f u n c t i o n s , c h r e s t e n s o n s p e c t r u m. 一 . 引言 密码从信息保密处理的方式看可分为分组密码和序列密码两大部分.序列 密码是把明文数据序列同密钥序列进行逐位加密生成密文序列发送给接受者. 序列密码不存在数据扩展和错误传播，实时性好，加、解密实现容易， 是一种 应用广泛的密码系统. 序列密码的安全强度取决于密钥序列，因而密钥序列的生成是一个关键问 题。人们寻找那些不但结构简单易于工程上的实现，而且满足必要的伪随机特 性的密钥序列生成器. 密钥序列生成器的传统模型是， 通常先用线性的方法产生有限个具有好的 伪随机特性的序列， 再经非线性组合来实现这个目标.其中，前馈网络是一类 比较理想的密钥序列生成器.n 个线性移位寄存器(l f s r) 产生n 个随机序 列，2 1 ，x 2 , ，: 。 ，f ( ) 是某个无记忆组合逻辑， 在二进制下f ( ) 实际 上就是某种布尔函数，f : 珍 h 凡，k 为生成的密钥序列. 如图1 . 1 所示. 图1 . 1 : 非线性组合前馈网络密钥序列生成器 这种组合函数的选择就成为序列密码体制一个重要的研究课题. 在序列密码中， 密钥序列生成器中的组合函数在二进制下即为布尔函数. 因此布尔函数在密码学中具有特殊的地位，是密码体制设计与分析的一个重要 工具.作为组合函数的布尔函数的一条性质反映一种安全性能指标，我们一方 面希望提出更多的性质来满足安全性能的更高要求，另一方面由于不同性能指 1 一一. 一. 一一一. - 标相互制约，在现有的性质之间找出最优折衷来提高综合性能. 现在公认在序列密码系统中布尔函数必须最少满足的性质为平衡性 (b a l - a n c e d n e s s) ， 高阶非线性( h i g h n o n l i n e a r i t y) 和高阶相关免疫性(h i g h ( h d c l o f c o r r e l a t i o n i m m u n i t y) .下面我们都会给出具体定义并量化出各种性质的衡 量指标，如非线性是密码系统中为抵抗线性攻击而提出的性能，非线性度则是 衡量其线性性能强弱的指标.若从这个意义上讲，非线性度越高越好，但非线 性度达到最高的函数， 其它性能将变弱. 如当非线性度达到最高时，将失去平 衡性和相关免疫性等.因此， 研究不同性质之间的关系，特别是不同性能指标 之间的数量关系是布尔函数研究中的一个重要课题.我们力求寻找它们的折衷 选择方案，以达到最佳的密码学特性. 这里必须指出，尽管这些特性的必要性很明显，但是无法知道具有这些 特性的函数可以充分抵制所有可能的攻击.事实上，我们现在实际应用的序列 密码系统的安全性是由系统可抵抗目前知道的几种攻击的能力来评判的，如 s i e g e n t h a l e r 相关攻击!2 0 ) , b e r le k a m p - m a s s e y 线 性合成攻击 1 1 和不同的线 性 近似攻击 【5 等等. 关于单输出的布尔函数已有许多好的结论，本文第三节中讨论的是二元域 上的多输出函数，它作为密钥生成器中的组合函数比单输出布尔函数有更高的 容许度，但同时也增大了信息泄漏的几率，所以对多输出函数的密码特性，有 着更高的要求. 二 输入，m输出的函 数f ( x l , . . . , x) 二( f l , - - - , f m ) 称为( n , m , t ) 一 : e s i l i e n t 函数， 若任一固定f中任意t 个输人后得到的函数是无偏的【 1 , 4 , r e s i l i e n t. 函数在密码应用中占有重要的地位， 如密钥恢复 1 和序列密码中可以抵制 相关攻击的密钥序列生成器的设计 ! 2 0 . 而 d i n 或 5 等提出的最佳仿射近似 ( b e s t a f f i n e a p p 二二 二 a t i o n) 攻击说明了高阶非线性度在密钥序列生成器 的组合函数的设计中的重要地位. 二元域上， 组合函数的研究已经得到了较好的结果， 但是t . s i e g e n t h a l e : 同 一一一一一一 一r 一， - -一_3 时给出如下结论: 定理1 . 1 11 9 1 若f 是域 摺 上的n变元rn 阶相关免疫布尔函数，则w( .月= 2 n k ( k o ) ， 且f 的代数标准式中不小于n 一 二+1 个变元的单项不出 现. 特别 是当f 是( 。 一1 ) 阶相关免疫函数时，r 必须是线性的. 这个结论反映了一个重要的现象， 即域岭 上的函 数的相关免疫性质与线性 复杂度性质具有矛盾性. 在密码体制设计中， 如果为防止d c攻击， 一味地要求f 具有高的相关免疫性， 则其抗线性攻击能力下降， 人们可以用b e l e r k a m p - m a s s e y 序列综合迭代算法 【2 4 有效地攻击. 定理1 . 2 田 有限域肠 上的。 变 元( n 一 1 ) 阶相关免 疫函 数都是线性的充分必 要条件是4 =2 , 3 . 该定理说明只有在小域上， 相关免疫特性与线性复杂性是矛盾的.我们通 过选择大的有限域 f n，可使其上的函数既有大的线性复杂性，又有高的相关 免疫性. 所以对于有限域上的多值函数的研究具有实际意义. 本文内容安排为， 在第二节中， 给出基本定义， 符号和结论; 在第三节中， 匹 西 在 定 理“ .2 中 给 出 了 一 种 新 的 具 有 高 阶 非 线 性 的 恤 m , t) 一 r e s a二 “ 函 数的构造方法，在相同的n输入，二输出下，这类函数的非线性度大于等于 2 n - 一 2 n - h / 2 - 1 ， 比 文献7 和2 司中 构 造的 函 数具有 更 优的 非线 性度. 在第四节中我们应用谱域特征来研究多值函数， 分别对多值函数的和的循 环谱，线性谱进行讨论.我们得到两个和多个多值函数和式的循环谱等于这些 函数循环谱的和的充要条件， 及两个和多个多值函数和式的线性谱等于这些函 数线性谱的和的充分条件. 二.基本概念与符号 记凡为有限域g f ( 2 ) ,蜡 为n 维空i旬g f ( 2 户，凡 中的加法记为。. 定义2 . 1两个具有相同长度 a 的二元序 i1 s , ，s 2 ， 我们记q ( s , =s 2 ) ( 相 应地，tt ( s , 并凡) 为序列s ; 与凡 对应位五相等( 相应地，不相等) 的个 数. s ， 与s 2 的 h a m m i n g距离定义为d ( s i , s 2 ) 二d ( s l t s 2 ) . w a ls i 距a w d ( s i , s 2 ) = d ( s l = s 2 ) 一 ( s l :a凡) .一个序 11 s 的h a m m i n g 重量或称为简单 重蚤，记做w t ( s ) =d ( s = 1 ) . 注意到w 武 s t , 凡) =a 一2 武 s , , 凡) . 设x =( x i , x n ) e f 2，j二 f 2一 f 2 ，j =( j ( 0 ) , . . ， ， .f ( 2 ” 一1 ) ) 为心 弃 上 2 n 序列 长向量， 称 为j ( x ) 的 函 数 值 向 量 或 真 值 表 . 定 义了 (劝为j ( x ) 的( 1 , - 1 ) ( ( 一 1 ) r c o , ， ( 一 1 ) x ( 2 , 一 ) ) . 布尔函数平衡性定义如下: 令x 二( x i , ， x n ) ，j : f z 一 f z .当 1 1 - 1f ( x ) 二0 l = i f x if ( x ) =1 i =z n - 1 时， 称f ( x ) 是平衡的. 定义n 输入， 。输出的函数f: 玛 一 f z ， 令川二 、 ， 相应地，多输出函数有 定义2 . 2若f ( x ) 对于任意0e 即 ，当 x , ) =( .r l , ， 几) i f x l f ( x ) 二mi =2 n - m 称f ( x ) 为无偏的. 引 理2 . 1 ! l f ( x ) 二( f l , , f m ) 是无 偏的 性纽合是平衡 的。 扩散准则是文献(6 中 引人的“ 5 0 % 广. 4 当且仅当所有非零的f l , . . . , f m的线 依赖性”和 “ 完全非线性”概念的推 -一 一一一 一一一- 一 - 一 一-. . 定 义2 . 3 1 1 5 1 设。 e 楷 ，a 0 0 ， 若f ( x ) . .f ( x (d a ) 是 平衡函 数， 即w t 汀 ( 二 ) f ( x .a ) ) = 2 n - i ， 则称.f ( x ) 关于a 满足扩散准则. 若对任意满足 1 w t ( a .) k 的a , f ( x ) 关于a满足扩散准则，则称f ( x ) 满足k次扩散准则. 如果f ( x ) 在a 满足扩散准则， 则f ( x ) (d f ( x . a ) 之间的互信息为零， 即 i ( f ( x ) ; f ( x (d a ) ) 二0 . 这正是密码学中所期望的性质. 定义2 .4 x1 4 f ( x ) 的非 线性度记为n f 定义如下 m m ,a) e f , + d ( f ( x ) , a o (d a , x i . 二 a n x n ) 其中 短距离. a o . a i x i . . . . (d a n x n 称为 仿射函 数，价即为f ( x ) 到 仿射函 数的 最 相应定义f w 的线性度 m ax ,n n ) e f 2 + , d ( f ( x ) , a o . a , x , . . . . (i n x n ) 显然有n f +c f 二2 n . 记f ( x ) 的最大可能非线性度为ma x n f . 引理2 . 2 1 1 0 1 n r =2 -1 _1 2m a x哟( 、 ) 1 根 据p a r s e v a l 公 式乙 么 呵( 、 ) = 2 2 n ， 所 以m a x ,哟( 、 ) 1= 2 + z 有 定理 2 . 1 1 1 0 1 绮 2 m且。 为 偶数 定义2 . 9 设 f ( x ) 为心 上的一个布尔函数， x 1 , ， 二 ， x 。是相互独立且满足 p ( x i ) =盖 的 随 机变 爹 ， 若f ( x i , . - . , x . ) 与x i , . . . , x 。 中 的 任 意t ( 1 t n ) 个都相互独立，即对于任意的 从 . . , x = j c x i , . , x . i ， 成立 p , ( f a ， 二， x n ) =b o x ; ， 二a t , ， x , ， 二a t ) =p r ( f ( x i , ， x n ) 二b ) , ( 2 .5 ) 对于任 意的( b , a 1 ， 二， a t ) e 玛+ 1 ， 则 称f ( x i , . . . , x . ) 是t 阶 相关 免疫的. 平街的 t 阶相关免疫布尔函数称为 t 阶 r e s i l i e n t 函数. 定义2 . 1 0 f ( x l , . . . , x) =( f l , . , f m ) 称为( 二 ， m , t ) 一 二 s i l i e n t 函数， 若任一固 定 f中任意 t 个输入后得到的函数是无偏的. - 一一 一一. 一一. 一 - -7 由引理2 . 1 我们得到下面推论， 推 论2 . 1 f ( x l , . . . , x ) 二 ( f l ， 二， f m ) 是 一 个味 ， 7 n , t ) - r e s i l i e n t 函 数 ， 当 且 仅当 所有昨零的h , . 二 ， f m的线性组合是( n , 1 , t ) 一 : e s i l i e n t 函数. 引 理2 .4 (2 -1 f ( x ) 为 一 个( n , 1 , t ) - r e s i li e n t 函 数， 当 且仅当 它的wa l s h 变 换 满 足 哟( 、 ) =0 , h o w t ( w ) 2 ，几 表示模m的剩余类环，黑 为n 个环氛 的直和. 称黑 到几 的映射f w 为欲 上的一个多值函数. 当m=2 时，f ( x ) 即为 布尔函数.定义在某一概率空间价， f , 只) 上且取值于几 的随机变量x k ， 若 丛木拟 . 念与钧 1二 只 ( x 、 = 约 二六，! 几， 则称x 、 具有 对称 分布 定义2. 14 设f ( 二 ， ， ， xn) 为2 决 上的一个多值函 数， x l ， . . ， 大 。 花相王独立且都 具有衬称分布的随机变量， 若f(x ， ， ， x 二 ) 与x l ， 二， 戈 中的任意以 1 三t 2 的情况. 推论3 . 1 f 为( n , m , t ) 一 : e s i l i e n t 函数， m 1 2 n i v r 2 n z / 2 . 再由引理 3 . 2得到 丛= 2 n , 叽 + 玛, ( 2 一 2 n f 2 ) ? 2 , n f 2 + 2 / 2 肠 引 理3 . 3 1 1 设f l ( x ) 是( n 1 , 1 , t ) 一 : e s i l i e n t 函 数, )q ,1 f ( x , , . . . 九 ( - n , + 1 , ， x n ) 是( n , 1 , t ) 一: e s i l i e n t 函数。 引 理3 .4 12 6 1 对于 任意f : 摺 曰 凡，f 的非线 性度满 足 x n ) =f i ( x i , 、 : 2 n - 2 4 0 m i 其中 二 。= 引 理3 .5 13 4 1 m i n l 0 ( a ) 日 a e 蜡， a 6 0. 若存在( n , k , 司线性码c，并且二 一k为偶数， 存在t 2 k 酬 一 。 (?)， 则 存 在 满 足“ 一 1 次 扩 散 准 则 的。 阶 、 二 、 。函 数 。 引理3 . 5 的证明中应用了引理 2 .5中提到的部分 b e n t 函数的形式. 中构造的函数 f ( 2 ) 全 。 ( 二 ) + t 46 二 +。 e f z，二ee， e和e 的直和为f 2 v et e心 一e上 e 1为e的正交集， . 其中e是( n , k , 司线性码本 9 ( v ) 为e 上的一个b e n t 函 身数 文献! 3 4 中指出由纠错码知识和引理的构造方式可知， 这种构造的函数是 相当多的. 引理 3 . 6 f对 在满足引理 3 . 5 的条件下，其非线性度 n f 2 “ 一 2 . ( 3 . 4 ) 证明; 若f w 满足引 理3 . 5 的条 件， 则f ( ) 为t 阶r e s i l i e n t 函数， 且满足d - 1 次 扩散准则. 行 一 -一一一 一一一一一一一一-. 一- - -分 - - -_1 1 而满足d 一1 次扩散准则，即存在一个ae摺 f ( x ) 在位移。下的4相关度为零，即 ( 叫-o . 再由引理 3 . 4的结论，有 n f 2 - 2 . 1 三w t ( a ) 三d 一1 ，使得 定理 3 . 1正整 数。， k , d ， 二， 其中。和k 为偶数， 。全2 r r r + k , 若存在。 a , k , 哟 线性码 c 函数 f ( x ) 且 存 在 正 整 数* ， 使 得 2 艺 挺 。 ( 约， 则 可 构 造( 、 ， 二 、 约 一 r e s i l i e n t ，并且 f ( x ) 的昨线性度 n , 2 - z . 证明: 一才面， 由定理的假设条件， 设 r是( 二 ， k , d ) 线性码本身，e和r 的直和 为心 ， 即e ， 为( 。 ， : 一 助码，e l为e的正交集， 则有引 理3 . 5 中构造的形如 f ( x ) 全 9 ( v ) + p u 的函 数， 其中x 二。 +。 玲 ，。 ee，v e e ，p 珍 一el ，9 ( 的为e 上的一个b e n t 函数.。 一k为偶数， 所以f ( x ) 为满足d 一1 次护散准则的t 阶 r e s i l i e n t 函数. 另一方面，已知n -k 之2 m， 且二为偶数， 由引理2 . 8 ，存在一个刀 止的 ( n 一k , m ) 一 b e n t 函数k ( x ) 。 令 k ( x ) =( k 1 ( x ) ， 二 ， k m ( x ) ) 因为n 一k 二，故可取线性无关的p i , _ - , p - e摺 一e 上， 令 f ( x ) 会 ( k i m+ p i u , .， k .n ( v ) + ; 。 二 ) ， 对任意c 二( c l , . . . , c - ) 3 ( 0 , ， 0 ) 、 有 f ( x ) g c i ( k i (v ) 。 p , u ) ， 二， .c-(km( 二 ) 。 ; 、 二 ) = ( e l k , ( v ) 。c m k , ( v ) ) 。u ( c i p , 。c m p m ) 三 二三i iy r a l- ! 工 性r e s i t i e l s t 布尔函数的 构达与 分4 h 因为k ( x ) =( k i ( x ) , . . . , k m ( x ) ) 是一个e 上的( 。 一 k , 2 m ) 一 b e n t 函数， 从 定义 2 . 8可知， c l k i ( 。 ) e. c m k m ( v ) 是一个 e ， 上的 b e n t 函数. 因为p l , . . . i p 。是蜡- e 1 上的m . 个线性无关的元素、 所以c i p i. 二 c - p 仍为f 2 - e 土 上的元素 . 由引理3 . 5 和引理3 . 6 , f ( x ) 为满足d -1 次扩散准p i 的t 阶r e s i l i e n t 函 数，且 f w 的非线性度 n f 全 2 - 2 . 所以 ，f ( x ) 为一个( n , m , t ) 一 : e s i l i e n t 函 数且丛 2 - 2 , 定理3 . 2对于任意满足h 2 m的偶数h ， 若存在n 2 m+ k 十 l a 的( n 一 h , k , d ) 线 性 码 c ， 且 存 在 正 整 数 满 足 2 k e :二 ， ( = h ) ， p i 可 构 造(二 ， ， 。 ， ， 卜r e s ilie n t 函数 f ( x ) ，其非线性度 n f 2 - 一 2 - h / 2 - 2 . ( 3 .5 ) 证明: 由定理 3 . 1 可知， 可构造一个 ( n 一h , m, 约一 r e s i l i e n t 函数d ( 幻， 且叫幼 的非线性度 n ,i, 2 - - 1- 2 . 令 d ( x t , ， 、 一 、 ) = o , ( x i , ， 、 一， ， w - ( x l , . 二 、 二 一 0, 另一方面， 由引理 2 . 3 , 对于满足h2 。的偶数 i l , 必然存在一个 伍, 7 17.) - g e n t 函数，故令 r ( x n - h + i , ， x , ) =l r 1 ( x n - k + i , - 二 ， x n ) ， 二 ， r m ( x n - h 4 i , ， x n ) 定 义 f ( x j , ， x n )全 仲i ( x i , ， x n - h ) 。 r i ( x n - h 千 ， ， ， .r n ) , - 一 - 一 一 一 一 一 -一- 一 一 一 一 一一一一. 一一 一一 _ 3 护 。 ( x ; ， ， 饰一 夕 ) 。际( 升一 、2 ， x 。 ) 对于任意 ( c ， ， ， c 动笋拟 0 ) ，令 八x ; ，1 。 )全c ， ( 甲 ， ( : l ; ， . 二 由 阮( 沪 。 ( x l ， ( c ， 沪 1 ( x l ， 二 ， ( c l : ， ( x ， ， 饰一 11): 1 ( 为 卜 ，、 、 ， . 二 二 ， 饰_ 、 ) 。: 。 ( 珠_ 、 + 1 ， 二 ，: ) ) ， x 卜、 ) 。 x 。 _ 、 ) 。. 。c 。 沪 、 ( 二 ， ， ， 踢一 。 ) ) 。鲡? 。 (x1 ， ， x 。 一 、 ) ) ， 由推论 忍 . 1，则 ( c l 沪 ， ( x l ， ， x 二 _ 1: ) 0c 、 甲 。 ( x l ，: ，: _ ， ) ) 为 t 阶 凡 e s 么 1 乞 e 几 t 的.从定义 牙 . 8 ( c l r l ( x 、 ， ， x 。 一 。 ) 。. 二 。气阮( x l ，: 。 _ 、 ) ) 为一个 b e 耐 函数.则由引理 夕 . 夕以及推论 夕 2 玛 七2 卜 八 ( 2 卜 一 2 ，!/ 2 一 ， 二 2 卜1 一2 几 一 九 / 2 一 2 _ f ( : ) 为乙 阶 几 。 s i l i e 7 、 t 函数， 且 +2 1 / 2 2 几 一 h 一 2 所以，f ( x) 为一个 ( 。 ， 7n， t)一二川z ent 函数且 zv f 全2 ” 一 1 一2 ， 一 h / 2 一 2 定理 3 2中，取偶数 的 t 和较大的 刀 尸;若 h h 满足2 。三h 兰二 一二. 较小，则可以得到较大的 若 h 较大，则可以得到较小 t 和较小的八 几. 文献 7 1 中的结论如下: 定理3. 3网对于任意满足h 数中 ( x) ，则必然存在 ( n ， 二， 全z m的偶数 h，若存在 ( 。一h ， 二， t ) 一: e 吕 乞 l i e 耐 函 扮匕 勺j t ) 一 r e s i l i e n t 函 数g ( x ， 夕 ) ， 其非 线性度 ng 全 zn 一 一 2 卜 州 2 一 ， . 三 鱼吵 韭些性几 e s i l i e n t 布尔函数的 构迅与分析 文献2 5 中，z h a n g 和z h e n g 提出一种 把线性r e s i l i n e t 函数转换成非线 性r e s i l i n e t 函 数的方法: 定 理3 .4 12 51 令f为( n , m , t ) 一 : e s i l i e n t 函 数，g为f 2上的 呈换函 数， 且非 线 性 度 为n c . 令p = g - f， 则户为( n ， 二 ， t ) 一 : e s i l i e n t 函 数 ， 且f的 昨 线 性 度 n f 二2 n - - n ,( 3 . 7 ) 设从定理3 . 2 得到 ( 二。 ， 约一 二 。 l i e n t 函数f， 其非线性度为n f; 从定 理 3 . 3 得到 ( n , m, 约一二s i l i e n t 函数 g， 其非线性度为 凡 ; 定理 3 .4得到 ( 。 ， 二 ， t ) 一 : e s i l i e n t 函 数户， 其非 线 性度为n i . 下面比较本文的结果和前面两个文献的结果，可以发现本文的构造的函数 类具有更高的非线性度. 由定理 2 . 1 和定义 2 . 7 ，定理 3 . 4中有 n c 2 一 1 一2 n - h / 2 - 2 定理 3 . 3 中有 n c 2 - 一2 n - h / 2 - 1 因为这里要求h 2 m， 故那 2 m， 所以 n cn f n f)n f _ _ _i 5 但n ,更优于n 的结论. 但必须指出， 从r e s i l i e n t 性来看， 定理3 . 3 中对构造的( 二 一 h ， 二 ， t ) - r e s i l i e n t 函数的存在性没有更多的要求， 而这里的结论中定理3 .2 ， 要求存在n全2 二十 k + h 的 (。 一 h , k , d ) 线 .t 码 c ， 且 存 在 正 整 数 满 足 2 k 艺 e 。 ( n 万 n ,_ o ( ) ， 这 样 对 于 较 大 的 t 不满足这个条件，这是本文定理中所加条件限制的不利方面. 四 . 多值函数的谱性质 引 理4 . 1( 逆变换) (2 n 变 元?m值函 数f ( x ) 与两种c h r e s t e n s o n 谱的关系 如 下 : f ( x ) 1 l f ( x ) 已知布尔函数 wa l s h 二艺 s f 间u ， 、 。 z m , e z 爪 =艺 s (f ) (w ) u , *、 。 z m we 2 票 谱有关系式 w f + g ( w ) =w f p ) + ,(w) 一 2 哟g ( w ) . 我们在多值函数 c h r e s t e n s o n 谱的定义的基础出发，展开讨论得到如下定 理及推论: 定理4 . 1设 f ( x ) ，g ( x ) ，x e黑 都是 m值函数，则f ( x ) +.g ( x ) 和f ( x ) 、 g ( x ) 三者的 c h r e s t e n s o n循环谱之)p1 的关系式 s (f + g ) p ) s (f + g ) ( 0 ) s ( f ) ( w 卜 s ( g ) ( w ) ， 、 j40 s ( f ) ( 0 ) +s (.o ) ( 0 ) 一1 ( 4 . 1 ) 成立当且仅当f ( x ) 与g ( x ) 的支撑集不交. 证明:由c h r e s t e n s o n循环谱的定义 s (f + s ) ( w )= v w任z n r u f (- )+ e 二 ， 一 目 x e 2 从 1 y-rn n _ . . 击匕从 u - -u f ( x ) + 9 ( x ) ( 4 . 2 ) s u ) ( w ) + s (a ) ( w )=共又o f (x )- ,.x + 艺 u 9 ( x ) 一 x x e z 孟 二 一 “ 、 “ ” + 二 “ ， ( 4 . 3 ) 艺吼 1-耐 充分性:显然，若f ( x ) 与9 ( x ) 的支撑集不交，则 x : x e 嵘， f ( x ) 0 0 c x : x e 礁， 9 ( x ) =0 , 月 -一 ， - -一 一 . 一一 . 一 一. 一一 一 一 一一一一】 7 :x ; 歇， s ( x ) 31 0 c x: .f ( x ) 4 0 , 9 ( 二 ) =o ， :1; “ e z r n , f ( x ) =0 ) 则x e z m分为 x ; s ( x ) =o 三部分， 则式 4 . 2变为 厂 ( 二 ) =0 , 9 ( 二 ) 另。 和 二: f ( . : ) s ( f + s ) ( w )=艺。 一 “ u f ( = ) + 又。 一“ u s (- ) f ( x ) a o ,s ( :r ) = o f ( 0 ) = o , s ( x ) o 网 !广jr z 山 一 祝 +艺 f ( x ) = 4 9 ( x ) = 0 而式 才 . 3变为 su ) (w ) “(，)? ， 一 1 ，(二)#y (x)二。一 。一: 艺二 一us(x) + 1 f ( x ) ? 0 , 9 ( x ) = o 、1产esj x 以 l u q +艺 f ( x ) = 4 9 ( x ) = 0 e二 一 . x u f (x ) +艺二 一 “ 二 ” ( ) f ( x ) ? e o , h ( x ) = of ( x ) a o ,9 ( 二 ) = o +艺 。 一 介十艺 x e z ,f ( x ) = 0 , 9 ( x ) = 0 显然，通过比较式 不 不与式 4 . 5 右式，成立如下关系 行卜 廿q s ( f + s ) ( w )二 s v ) (w ) + s o ) p ) - ) l二 一 x e z 朵 因为w铸0时，由对称性，w- x , x黑 m几 一 1 次方 根， 所以 有1 : - e z - u - 二 0 ， 而、 = 。 叶 ， 次遮历 z m，由于 e . e z - u - w ， = m ，、 为 1的 m 故得到关 系式4 . 1 必 要性 :若关系式 4 . 1 成立，则由还变换公式， y d t ( x ) + 9 ( s ) = 艺 s (! + s ) ( w ) w e z , 一 e i s (i ) (w ) + s (e ) p ) 卜 s u ) (0 ) + s (9 ) (0 ) 一 w e z _, w 护 0 1 8 四 .多值函数的i6 性质 二 艺 s (f ) (w we z 及 二 o f ( _ ) +96 9 ( x ) +艺 s (s ) ( w ) 一 1 w g z , 一 1 , 即对任意的x e 黑 ， 成立u f (x ) = 1 或u 9 (x ) =1 ， 即f w =。 或9 ( x ) =。 ， 亦 即f ( x ) 与9 ( x ) 的支撑集不交. 推论4 . 1设 f ( x ) ，x歇 ，二 1 , 、 k为 9 n值函数，则对 1三 7 1 7 2 了 ， k， 一了 以 s (方 : + s u i , 十 + 乃 r ) ( w ) + h * ) ( 0 ) s (f r n ) ( w ) + + s ( f i* ) ( w ) ，。 护 。 s (h , ) ( 0 ) + + s (f j ， ) ( 0 ) 一( : 一 1 ) jj翎， 成立，当且仅当对于任意 1 i ,- e 7 , n ) 证明: 由c h r e s t e n s o 。线性谱的定义，h w e 歇 if ( x ) +9 ( x ) 1 u - x 艺吼 1一mn s f + g= 、，.少 工 田 一 祝 又( f ( x ) + 9 ( x ) 1 。 一 + 7 l - w x 又 ( f ( x ) +9 ( x ) 1 f ( x ) + g ( x ) m ) 上淤 e(f ( x ) + 9 ( x ) 1 、 一 x +又(f (x ) + 9 ( x ) 一 。 二 一 f ( x ) + g ( 二 ) m) 上耐 f ( x ) u - x 十艺 9 ( x ) 、 一 一 二 x e z - 艺 x : f ( x ) + g ( x ) ? m =s f ( w ) + s 9 ( w ) 一 m , ,+ 1艺 x :f ( x ) + g ( x ) ? m 推论4 . 2设f ( x ) ，g ( x ) 9 ( x ) 三者的c h r e s t e n s o n x e蹂 都是 m值函数，则f ( x ) +g ( x ) 和f ( x ) 、 线性语之问的关来式 s f + 9 ( w ) =s f ( a ) + s 9 ( w ) ， 。e z -( 4 . 9 ) 成立的一 个充分条件是， 对于任意x e 蹂 ， 郑有f ( x ) + g ( x ) n c . 推论4 . 3定理子 . 1 中的条件是使式毕 . 9 成立的另一个充分条件. 推论4 . 4设f i ( x ) , x e跺 ，j = 1 , . . . , k为二值函数，则对 1 j l j 2 (w ) + 、 二 + s fi* (w ) 一 7ii + 1 g . ( - f i , ( x 卜 斗儿 ( x ) z mj - 2 7 1b n + 1艺。 一 玄 - . :2 m 乃 , ( x ) + 石 ， ( . ) 3 m ) 一 ( : 一 1 ) 7i n + l艺u - x . ( 4 .1 0 ) 二 : ( : 一 1 ) m f i , ( x ) + . . .+ f i * ( 二 ) z m， 记 f ( x ) =k ; f ( x ) 54 k . ( 4 . 1 1 ) 11c 了.j、1 -一 x 几 则函数f ( x ) 可表示为 f ( x ) =艺k i k ( x ) x e z m , 显然和式中的 k i k ( x ) , c h r e s t e n s o n谱完全由 构造有一定的实用意义 k=1 . . . . , m一1 满足定理 4 . 1 的条件， 所以 f ( x ) 的 k i k ( x ) 来确定.由此可见本文的结论对于多值函数的 五 . 总结 密钥生成器中组合函数的优劣决定了序列密码系统的安全性的强弱， 关干 组合函数的性质的研究还会随着实用要求和信息理论的发展而深人下去。为了 抵制可能的攻击， 组合函数必须具有的非线性， 相关免疫性， 平衡性等性质， 尤其 是组合函数必须具有高阶的非线性来抵制各种的线性攻击. 这里通过部分 b c 7 1 t 函数的函数形式构造了一种新的具有更优非线性度下界的 。 l , i n , 约一r e s i l i e n t 函数. 后一部分中， 给出了多值函数的 c h r e s t e n s o n谱的一些性质，对两个多值 函数的和的循环谱和线性谱与两个函数的循环谱和线性谱的和进行讨论. 对应 wa l s h谱的结论，这些结论虽然因为环的限制需要比较强的各件，但是仍可以 在多值函数的构造中有一定的作用. .- 参考文献 1 1 b e n n e t t b . , b r a s s a r d g . a n d r o b e r t j . , p r i v a c y a m p l i fi c a t i o n b y p u b l i c d i s - c u s s i o n ,s i a m j o u r n a l o n c o m p u t i n g , v . 1 7 , 2 1 0 - 2 2 9 , 1 9 8 8 2 1 c a r l e t c . , p a r t i a l l y - b e n t f u n c t i o n s , p r o c e e d i n g s o f c r y p t o 9 2 . 3 1 c a r l e t c . a n d s a r k a r p . , s p e c t r a l d o m a i n a n a l y s i s o f c o r r e l a t i o n i m m u n e a n d r e s i l i e n t b o o l e a n f u n c t i o n s , f i n i t e f i e l d s a n d t h e i r a p p l i c a t i o n s , v . 8 , 1 2 0 - 1 3 0 , 2 0 0 2 . 4 1 c h o r b， e t a l . , t h e b i t e x t r a c t i o d p r o b l e m o r t - r e s i l i e n t f u n c t i o n s ,