具有高代数免疫阶的平衡布尔函数的构造.pdfVIP

第29卷第5期 长春师范学院学报(自然科学版) 2010年10月 V01．29No．5 of Normal Oct．2010 Journal Science) ChangchunUniversity(Natural 具有高代数免疫阶的平衡布尔函数的构造 周景芝 (连云港师范高等专科学校数学系，江苏连云港222006) [摘要]在探讨密码学中布尔函数性质的基础上，构造一类具有高代数免疫阶的布尔函数。它具有 好的代数次数，并且具有平衡性． [关键词】布尔函数；代数次数；平衡性；代数免疫阶 [中图分类号]TN918．1；015[文献标识码】A 【文章编号]1008—178x(20m)05—0001—02 O引言 密码技术是网络与信息安全的关键技术之一．基于线性反馈移位寄存器的流密码的代数攻击由Courtois和 Meier提出【1|，此法一经提出就对现有流密码体制形成了巨大威胁．代数攻击中，最为关键的步骤就是构造关于 初始密钥的超定义代数方程，文[2]将该问题转化为寻找布尔函数的低次数代数关系，又进一步将其转化为布 尔函数的低次数零化多项式的问题．文[3]指出抵抗代数攻击需要高的代数免疫阶．但是，具有高的代数免疫阶 不一定能抵抗快的代数攻击[4|．目前，两类布尔函数具有最高的代数免疫阶．第一类是变量的个数忍为偶数的 函数，文[5]对第一类函数作了进一步的研究，指出它的代数次数接近，l，但是它不具有平衡性．另一类是对称 函数，它依赖输入向量的哈明重量．这两类函数抵抗代数攻击是非常弱的[6]6．本文构造了一类具有高代数免疫 阶的布尔函数，它具有好的代数次数，并且具有平衡性，从而可以有效地抵抗代数攻击． I预备知识 定义1 {0，I}“一{0，l}的映射称为n元布尔函数，n元布尔函数的全体记为鼠． 式： ／．(茹)=／．(菇l，X2，…，髫。)=∑ C(a)菇4，(c(a)∈F2)． (1) 4=(41．．。．％)∈}O．I{“ …+口。)． 对于．厂，gEB。，定义它们的哈明距离为 幽(／，g)={菇∈F量：以茗)≠g(x)}_蛳(厂一g)， 其中埘Ⅳ(／)={石EF置-f(戈)=1}叫做厂的哈明重量． 定义2 B。叫做是平衡的是指埘Ⅳ(一=2”1． fE 化多项式组成的集合记为Arm(f)．Ann(f)UAnn(1+力中非零多项式次数的最小值称为厂的代数免疫阶，记为 朋(一． F?＼Supp(p． 引理[1]M(厂)≤rn／21． 证明 Supp(f)l≤2“-。，下证 由F譬=Supp(f)U面而可知lSupp(f)I≤2“一1或I—Supp—(f)l≤24．。．不妨设l 存在gE g≤rn／2]使得旷=0．(若I B。，g#O，deg 0)． 令d=r n／2]，则g可表示成 [收稿Et期]2010—06—23 [作者简介】周景芝(1974一)，女，江苏连云港人，连云港师范高等专科学校数学系讲师，硕士，从事代数编码理论研究。 万方数据 9(c(口)∈F2)， g=d。．釜怅霹c(口)xa ‘ ‘(。)《： g的系数c(口)的个数等于蔷d(3=‘娶(?)2”1． 由于fg=0等价于g step(f)=0，对于每个b=(bl’．一，b。)∈Supp(f)， a)64=0· (2) g(6)-州。，釜小嵋c