布尔函数的代数免疫性+孙占高1 孙兵1 李超1 ( 1 国防科技大学理学院数学与系统科学系长沙4 1 0 0 7 3 ) ( 2 东南大学移动通信国家重点实验室南京2 1 0 0 1 8 )( 3 国防科技大学计算机学院网络与信息安全研究所长沙4 1 0 0 7 3 ) ( s z h g n u d t 1 6 3 e o m )摘要本文对n 元非线睦布尔函数，的代数免疫性、代数次数和非线性| 生进行了研究，得出了以下结果：1 ) 缮出了n 元非线性布尔函数，代数免疫性的上界：爿，( 厂) sm i n 爿，d e g ( f ) 2 ) 证明了疗元非线性布尔函数，代数免疫| 生和非线性度之间的相互制约关系：当A I ( f ) d + ，时，则兰( ? N f 2 1 = 0H 一兰i = 0 ( ? 。当 d + 1 时，则I ，I I 2 “ - 壹。w 1 7 ，那么A I ( 力d 。址明嵌g ( 叫是以一一h i , b 为参数，次数d 的布尔函数，其代数标准型为：g ( b o ，。b ，z ) = b o + 弧+ 叩，+ + 6 。x r _ 。 l a b a nl s l J E nl s l iE 妇粼燃M c 小副的慨令F = f g ，1 = x l f ( x ) = 1 ，x e G F ( 2 ) ” ，对所有x 1 ，考虑以6 0 ，为变元的善元方程组甩，一o ，川，显然这些方程均舻次的。因为川，所以这个方程组又可以等价为，。为变元的善( 刁元_ 次方程组矾扎剐1 ，热方程爪数为撑，= w r 。因为w c 门 纠，同引理的证明：当g 的次数J 取到时，关于，气。的部dn 元一次方程鲥u ，加。，川，只有稚。眦咐，砉若堋圳u 阡三m 为徽则阱孚堋弘阱州州，5 Z 困Y J ：w t ( f ) + w t ( f + 1 ) = 2 ”，所以从而由引理3 得：A l ( f ) d ，矛盾鲥例吲巾删w ) 阱因为厂( ，+ 1 ) = O 恒成立，所以，A I ( f ) d e g ( f + 1 ) = d e g ( f )因此，对任意的，鼠降】，总有彳，( 门m i I I f 兰 ，d e g ( f ) n 一( d + 1 ) = 丁n - 1 = d ，由引理3 得胝w 阶副钉为张瞅通过上面的讨论，代数免疫性与非线性度之间有如下关系定理2懑 吣口阡孚俐= 即棚女l J A I ( f ) d + 1 。证明设e G F ( 2 ) ”满足f & ，) ( ) I -I S m ( o O I ，则由引理1 可得，= m i n w t ( f ( x ) + C O o 。工) ，w t ( f ( x ) + c o o 。x + 1 )口8 5 7、，J栉f，Lo 己ml l、，；J疗f，。m一2卜玎f，。珊z L 黝脚戡删酬川w w 由于，= ( f + c o o x ) + X ，由引理1 可得：A l ( f ) d + 1 。考虑定理2 的逆否命题，有：触榭c 门蚺，删利_ 掣一黝4 小结口尽管有些低代数次数的布尔函数具有高非缌陛度，但其代数免疫性却有可能很低，如：二次B e n t函数；另一方面，从定理1 可知，高代数次数并不能保证高代数免疫性，如函数厂= 1 + x l x 2 x 。，虽然，只有次数为n 的零化子g = x 2 x 。，但厂+ l 却有零化子：g ，= 1 + x 。( 1 f “ ) ，其代数免二 疫E ，一1 。由定理2 可以看出，当布尔函数的非线性度很高时，将导致其代数免疫性降低，因此在设 计布尔函数时，应综合考虑，方能使所设计的函数具有较好的性质。 参考文献【1 l 温巧燕，钮心忻，杨义先现代密码学中的布尔函数北京：科学出版社，2 0 0 01 2 1W i l l iM e i e r ，E n e sP a 翱m c ，C l a u d eC a d e t ：A l g e b r a i ca t t a c k sa n dd e c o m p o s i t i o no fB o o l e a n 缸l 胡咖sP r o c c e d 吨o fE u m 廿y p I2 0 0 4 , L N C S3 0 2 Lp p 4 7 4 - 4 9 1 ，S p r i n g e r , 2 0 0 4 【3 】A d i S h a m i r ，J a c q u e s P a t m i n ，N i c o l a s C o u r t o i s ，A l e x a n d e r K l i m o v ， E f f i c i e n t A l g o r i t h m s f o rs o l v i n g O v e r d e f m e d S y s t e m so f M u l t i v e r i a t e P o l y n o m i a l E q u a t i o n s ，”E u r o n r y l p t 2 0 0 0 ，L N C S1 8 0 7 ，S p r i n g e r ，p p 3 9 2 - 4 0 7 4 1C o u R o i sN F a s ta l g e b r a i ca t t a c ko ns h B mc i p h e r sw i t hl i n e a rf e e d b a c k A d v a n c e si nC t y p t o l o g y - C r y p t o2 0 0 3 ，L N C S2 7 2 9 ，S p r i n g e r - V e r l a g ，2 0 0 3 1 7 6 - 1 9 4 【5 1 C o u r t o i sN M e i e r W A l g e b r a i c a t t a c k o ns t r e a m c i p h e r s w i t h l i n e a r f e e d b a c k A d v o n c e s i n C r y p t o l o g y - C r y p t 0 2 0 0 3 ，L N C S2 6 5 6 ，S p r i n g e r - V e r l a g ，2 0 0 3 3 4 5 - 3 5 9【6 】C l a u d e C e r l e t I m p r o v i n g t h e a l g e b r a i c i m m u n i t y o f r e s i l i e n ta n d n o n l i n r u n o n sa n dc o n s t r u c t i n g b e n t f u n c t i o n sh t t p ：e p r i n t i a e r o r g 2 0 0 4 2 7 6 p d 作者简介孙占高，1 9 7 8 年生，男，山东淄博人，国防科学技术大学硕士研究生，主要方向为编码密码理论及其应用。