《武汉工程大学学报》 2014年11期
75-78
出版日期：2014-11-30
ISSN:1674-2869
CN:42-1779/TQ
拟Bent函数的代数免疫性
0引言布尔函数作为序列密码、分组密码和Hash函数的重要组件，其密码学性质的好坏直接影响到密码系统的安全性. 文献［1］`提出了一类密码学性质优良的函数——拟Bent函数, 它是包含Bent函数和部分Bent函数的更大的函数类, 可以具有Bent 函数所不具有的密码学性质, 如: 平衡性、相关免疫性, 能有效抵抗线性攻击、相关攻击和差分攻击等. 随后, 人们相继研究了拟Bent函数的一些构造方法及其非线性度、代数次数、相关免疫性、扩散性、正规性、对偶性等密码学指标［26］. 研究表明, 拟Bent 函数的密码学性质优良, 在密码设计及通信领域中有广泛的应用.随着密码技术的不断发展, 各种新兴的攻击方法相继出现. 尤其是代数攻击［7］的出现, 在密码学界引起轩然大波, 人们利用代数攻击成功地破译了Toyocrypt和LILI. 代数攻击对现有的密码体制形成了巨大威胁, 为抵抗代数攻击, Meier等人于2004年引入了度量布尔函数安全性的新指标——代数免疫性 ［8］. 代数免疫一经提出就受到密码学界的广泛关注, 研究成果主要集中在两方面: 一是最优代数免疫函数的构造方法研究［912］; 二是对已有的密码学性质良好的布尔函数的代数免疫性研究［1315］ .关于代数免疫与其他密码学指标之间的关系已有少量的研究，如文献［16］研究了布尔函数的代数免疫与扩散阶之间的关系. 但是, 针对拟Bent函数的代数免疫性分析还未得到系统的成果, 探讨拟Bent函数是否存在低次零化子, 能否抵抗代数攻击, 具有很强的现实意义. 本文基于布尔函数非线性度与代数免疫度之间的关系, 利用Walsh谱、组合数等工具对拟Bent函数(包括偶数变元和奇数变元)的代数免疫性进行系统地分析, 得到了判定其存在低次零化子的一个充分条件. 该条件只需要根据拟Bent函数的阶数k与变元个数n之间的关系就可进行判定, 不需要利用Walsh循环谱或代数正规形来判定, 非常直观有效. 进一步, 还研究了如何根据拟Bent函数的阶数k与变元个数n之间的具体关系来确定其代数免疫度的上界.1预备知识一个n元布尔函数f是指从GFn(2)={0,1}n到GF(2)={0,1}的一个映射. 记Bn为所有n元布尔函数组成的集合, 记An为所有n元仿射布尔函数的集合.定义1［17］设f(x)∈Bn, 称S(f)(w)=2-nΣx∈F2n(-1)f(x)+w·x为f(x)的一阶Walsh循环谱. 其中w∈F2n. 定义2［17］设f(x)∈Bn, 称Nf=minl∈AndH(f,l)为f(x)的非线性度. 其中dH(f,l)为汉明距离, 即dH(f,l)=|{x∈F2n}|f(x)≠l(x)}|.定义3［1］一个n元布尔函数f(x)称为n元k阶拟Bent函数, 如果对任意的w∈F2n, 均有|S(f)(w)|=0或2n-k2. 易知, n为偶数时, 0阶拟Bent函数就是Bent函, n阶拟Bent函数就是仿射函数.定义4［7］设f∈Bn, 若0≠g∈Bn, 使得f·g=0恒成立, 则称g是f的零化子. 由于f·(1+f)=0, 因此f的零化子一定存在. 记f的全体零化子构成的集合为An(f).定义5［8］设f∈Bn, 称f的零化子和1+f的零化子的代数次数的最小值为f的代数免疫度. 记作AI(f), 即AI(f)=min{deg(g)|g∈An(f)or g∈An(1+f)}. 第11期刘志高,等：拟Bent函数的代数免疫性武汉工程大学学报第36卷2主要结论引理1［17］设f(x)∈Bn, 则Nf=2(n-1)1-maxw∈F2N|S(f)(w)|.引理2［8］设f(x)∈Bn,若AI(f)=d,则Nf≥2Σd-2i=0Cin-1. 引理3［7］设f(x)∈Bn, 则AI(f)≤n2. 定理1设f(x)是n元k阶拟Bent函数. (1) 当n为偶数时, 若k＞2log22Cn2n-n, 则AI(f)≤n2-1, 即f(x)存在低次零化子; (2)当n为奇数时, 若k＞2log22Cn-12n-1-n, 则AI(f)≤n-12, 即f(x)存在低次零化子.证明由引理1和定义3知,Nf=2n-11-maxw∈F2n|S(f)(w)|=2n-1-2n+k2-1. 设AI(f)=d,则由引理2知,2n+1-2n+k2-1≥2Σd-2i=0Cin-1, 即Σd-2i=0Cin-1≤2n-2-2n+k2-2=12Σn-1i=0Cin-1-2n+k2-2.(1) 当n为偶数时,12Σn-1i=0Cin-1-2n+k2-2=Σn2-2i=0Cin-1+Cn2-1n-1-2n+k2-2. 若Cn2-1n-1-2n+k2-2＜0, 即k＞2log22Cn2n-n时,Σd-2i=0Cin-1＜Σn2-2i=0Cin-1, 即d＜n2, 亦即AI(f)≤n2-1, 再由引理3知, f(x)存在低次零化子. (2) 当n为奇数时,12Σn-1i=0Cin-1-2n+k2-2=Σn-32i=0Cin-1+12Cn-12n-1-2n+k2-2. 若12Cn-12n-1-2n+k2-2＜0, 即k＞2log22Cn-12n-1-n时,Σd-2i=0Cin-1＜Σn-32i=0Cin-1, 即d＜n+12, 亦即AI(f)≤n-12, 再由引理3知,f(x)存在低次零化子.定理1给出了n元k阶拟Bent函数存在低次零化子的一个充分条件, 它只需要根据k与n的关系来进行判定, 而不需要利用Walsh循环谱或代数正规形来判定, 非常直观有效. 由定理1知, 在变元个数确定的情况下, 拟Bent函数的阶数越高, 其存在低次零化子的可能性越大, 抵抗代数攻击的能力越弱. 反之, 在阶数确定的情况下, 拟Bent函数的变元个数越大, 其存在低次零化子的可能性越小, 抵抗代数攻击的能力越强. 进一步, 还可分析拟Bent函数的阶数k与其变元个数n之间的距离对代数免疫性的影响.f(x)为此, 需要探讨一些组合数的性质.结论1对于一切偶数n≥10, 有Cn2n＜2n-2.证明(1)n=10时,C510=252＜28. (2) 假设n=k时, 命题成立, 即Ck2k＜2k-2. 则n=k+2时, 有Ck+22k+2=4k+1k+2Ck2k＜4Ck2k＜2k, 命题亦成立. 综合(1)、(2)知原命题成立.类似可得如下结论:结论2对于一切奇数n≥5, 有Cn-12n-1＜2n-2.由定理1和结论1可得如下推论:推论1设f(x)是n元k阶拟Bent函数, 且n为偶数. 若n-k=2, 则对于一切n≥10,f(x)存在低次零化子.证明由结论1知, 当n为偶数时, 对于一切n≥10, 有Cn2n＜2n-2, 从而有2log22Cn2n-n＜n-2=k, 再由定理1知, f(x)存在低次零化子.类似可得如下推论:推论2设f(x)是n元k阶拟Bent函数, 且n为奇数. (1) 若n-k=2, 则对于一切n≥5, f(x)存在低次零化子; (2) 若n-k=4, 则对于一切n≥11, f(x)存在低次零化子.推论1和推论2表明, 拟Bent函数的阶数k与其变元个数n之间的距离对代数免疫性的影响很大, 距离越小, 代数免疫能力越弱.进一步, 还可把定理1推广得定理2.定理2设f(x)是n元k阶拟Bent函数. (1) 当n为偶数时, 若k＞2log24Σn2-1i=mCin-1-n, 其中m为不大于n2 -1的整数, 则AI(f)≤m; (2)当n为奇数时, 若k＞2log2(4Σn-12i=mCin-1-2Cn-12n-1)-n,其中m为不大于n-12的整数, 则AI(f)≤m.证明(1) 当n为偶数时, 由定理1的证明知, Σd-2i=0Cin-1≤Σn2-2i=0Cin-1+Cn2-1n-1-2n+k2-2=Σm-1i=0Cin-1+Σn2-1i=mCin-1-2n+k2-2当Σn2-1i=mCin-1-2n+k2-2＜0,即k＞2log24Σn2-1i=mCin-1-n时,Σd-2i=0Cin-1＜Σm-1i=0Cin-1, 即d＜m+1,亦即AI(f)≤m. (2) 当n为奇数时, 由定理1的证明知, Σd-2i=0Cin-1≤Σn-32i=0Cin-1+12Cn-12n-1-2n+k2-2=Σm-1i=0Cin-1+Σn-12i=mCin-1-12Cn-12n-1-2n+k2-2当Σn-12i=0Cin-1-12Cn-12n-1-2n+k2-2, 即Σn-12i=mCin-1-12Cn-12n-1-2n+k2-2时＜0, 即k＞2log2(4Σn-12i=mCin-1-2Cn-12n-1)-n时，Σd-2i=0Cin-1＜Σm-1i=0Cin-1，即d＜m+1,亦即AI(f)≤m. 定理2表明, 可以根据拟Bent函数的阶数k与变元个数n之间的具体关系来确定其代数免疫度的上界.3结语本文研究表明当拟Bent函数的阶数k与变元个数n满足一定的关系时, 就可充分判定其存在低次零化子, 为密码系统中密码函数的选择提供了借鉴. 遗憾的是, 该条件是充分的而非必要的. 能否找到充要条件, 还有待进一步研究. 致谢 感谢安徽省高校优秀青年人才计划给予的经费支持,诚挚感谢张福泰教授的辛勤指导!