一类代数免疫度最优的奇数变元旋转对称布尔函数的构造*

沈黎鹏,陈克非,2,3

1.杭州师范大学 理学院,杭州311121

2.杭州市密码与网络安全重点实验室,杭州311121

3.卫士通摩石实验室,北京100070

1 引言

密码系统中使用的布尔函数应该满足一些安全性指标:代数次数,平衡性,相关免疫度,非线性度,差分均匀度等.随着代数攻击[1,2]的出现,代数免疫度成为选择布尔函数的一个重要的新指标[3,4].从文献[4]的研究成果我们可以知道n元布尔函数的代数免疫度上界是如果达到了这个上界,那么我们称布尔函数是代数免疫度最优的.近年来,许多最优代数免疫度函数类被密码学者提出[3,5–8].

如今,学者们还致力于研究性质优良的旋转对称布尔函数(RSBFs).这是一类具有在循环群作用下函数值保持不变的布尔函数,其旋转对称性使得布尔函数具有结构简单、运算速度快、实现代价小等优点.旋转对称布尔函数在一定条件下可以具备优良的密码学性质,比如文献[9]构造的布尔函数具有1 阶弹性,文献[10]构造的布尔函数具有bent 性.因此,旋转对称布尔函数在密码学领域发挥着极其重要的作用.

目前,关于奇变元的最优代数免疫度RSBFs 已经有了较多的研究成果.2007年,Sarkar和Maitra[11]修改择多函数,给出一类具有最优代数免疫的RSBFs,但是其非线性度不高,为年,Su 等人[12]基于正数拆分理论分别构造了奇数和偶数变元的代数免疫度最优RSBFs 构造,具有较高的非线性度,当函数变量个数n为奇数时的非线性度为同年,文献[13]构造了一类最优代数免疫的奇数元BFSRs,其非线性度为年,Fu 等人[14]中改进了文献[12]的方案,构造的布尔函数非线性度为之后,Sun 等人[15]给出了两类最优代数免疫的奇数元RSBFs,也都是基于整数拆分理论构造的,而且第一类函数的非线性度超过了以往的构造.

对于代数免疫度最优的奇数元RSBFs 本文给出了一种新的构造,在构造方法上受到了文献[15]的启发.通过对集合元素的计数可以发现,构造出的函数在非线性度和代数次数上具有较大的优势.本文所得结果也为今后使用密码函数提供了一种新的选择.

2 准备知识

2.1 布尔函数的基础知识

一个n元布尔函数是到F2的一个映射.任一布尔函数f均可由它的真值表表示:f=[f(0,··· ,0),f(0,··· ,1),··· ,f(1,··· ,1)].f是平衡的,如果wt(f)=2n−1.

记Bn为所有n元布尔函数组成的集合.对任意f(x0,x1,··· ,xn−1)∈Bn,都可唯一表示成上次数不超过n的一个多项式:

这种表示方法被称为布尔函数的代数标准型.式(1)中f的代数次数定义为:

代数次数小于或等于1 的函数被称为仿射函数.所有仿射函数的集合记为An,即An={f∈Bn|deg(f)≤1}.

定义1对于f∈Bn,如果存在g∈Bn,使得fg=0,则称g为f的零化子.f的代数免疫度是定义为:

定义2对于函数f∈Bn,定义f的Walsh 变换:

对于f,g∈Bn,定义d(f,g)=wt(f+g)为f与g的Hamming 距离.布尔函数f的非线性度是f与所有仿射函数的最小Hamming 距离,记作nl(f),即:

等价于:

2.2 旋转对称布尔函数

定义3布尔函数f∈Bn称为旋转对称布尔函数,如果对任意的以及1≤l≤n−1 均成立.

定义4如果

则称F(x)为择多函数[16].

文献[3]指出了择多函数F(x)的代数免疫度达到最优,其代数次数为deg(F)=2⌊log2n⌋.

3 布尔函数的构造

3.1 整数拆分

首先,我们引入整数拆分的相关知识,这是接下来函数构造的基础.

一个正整数k的拆分可以表示成一个序列(k1,k2,··· ,km),且满足k1+k2+···+km=k.同时也要注意到,仅是顺序不同的序列表示整数k不同的拆分.我们把每一个ki称为一个部分.易知,整数k拆分成m个部分的计数为

引理1给定正整数k,m1和m2,m=m1+m2,k的拆分满足以下3 个条件:

(1)a1+a2+···+am=k;

(2)am≥2;

(3)(a1,a2,··· ,am)中m1个部分等于1,其余m2个部分大于等于2.

记k的拆分数为pm1,m2(k),则

证明:等同于分球入盒问题,即有k个相同的球,m个不相同的盒子,其中m1个盒子只放一个球,另外m2个盒子至少放两个球,已确定某一个盒子至少放两个球,求分法数.首先盒子的分法有种,盒子确定的情况下球的分法有种,因此共有种分法.

推论1在引理1相同条件下,如果am−1≥2,则拆分数如果am−1=1,则拆分数

引理2给定正整数k,m1和m2,m=m1+m2,k的拆分满足以下两个条件:

(1)a1+a2+···+am=k;

(2)已知(a1,a2,··· ,am)中ai1,ai2,···aim2≥2.

记k的拆分数为qm1,m2(k),则

证明:同样利用分球入盒模型易证.

引理1和引理2给出了整数k在两种特定情况下的拆分数计算公式,更多关于整数拆分的知识见文献[17].

3.2 集合的构造与计数

下面我们根据不同的m1和m2,对Sh,m1,m2进行分类.

当m1≥1,m2≥2,dm−1≥2时,记由1和2

当m1≥1,m2≥2,dm−1=1时,记则

当m1=0,m2≥2,记由引理1和2

当m2=1时,记由引理1和2

为便于计数,令

其中k1≥2,dm≥2,对任意1≤i≤m−1,若di≥2,则ki+1≥2.

其中t∈Ik,h,集合

命题1是上述构造的向量集合,以下结论成立.

(2)对任意的t1,t2∈Ik,h,如果则

证明:(1)对任意的设任意的可表示成n/t1或n/t2个分块的级联,所以必可表示成[n/t1,n/t2]个相同分块的级联,即n/(t1,t2)个相同分块,由β1存在性知反之,若存在r|(t1,t2)且r∈Ik,h,设任意的β2可表示成n/r个相同分块的级联,又有(n/t1)|(n/r),(n/t1)|(n/r),所以β2必可表示成n/t1或n/t2个相同分块的级联,于是

(2)可由(1)的证明得到.

例1给定k=103,当h=99时,取t1=69,t2=23 ∈I103,99.对任意的向量必可表示为(a,a,a)的形式,其中a[x0,··· ,x68]是γ的一个分块.根据集合的定义可知

再令

根据式(5)和式(6),我们可按以下算法计算|T2h|.

算法1 计算|T2h|Input:k,h,Ik,h={t1,t2,··· ,tm}Output:|T2 h|1 输入k,h,Ik,h={t1,t2,··· ,tm},其中t1< t2< ··· < tm,令i=1.2 计算|T′′h,ti|=|T′h,ti|−∑tj|ti,j

例2给定k=16,当h=15时,我们有此时由于k+h+ 1=32 为偶数,所以

3.2.3T和U的构造与计数

将T和U排列如下:

简记为

3.3 函数的构造

其中F(x)是n元择多函数.于是f(x)是一个平衡的n元旋转对称布尔函数.

例3给定k=5,我们有

则有

令T=T3∪T4∪T5,U=U3∪U4∪U5.对任意α∈T∪U,有记F(x)是11 元择多函数,则

是一个平衡的11 元旋转对称布尔函数.

4 布尔函数的性质分析

4.1 代数免疫度

引理3对任意的h∈H,αhs∈Th以及uhs,uht∈Uh,1≤s,t≤|Th|,1≤s,t≤|Th| 以下结论成立.

(4)对任意的0≤l≤n−1,h1,h2∈H且

(5)对任意的0≤l≤n−1,当s>t时,

证明:(1)由Uh的定义显然成立.

满足k1+···+km=h,d1+···+dm=h−1.

当1≤l≤dm+1,有

当dm+2≤l≤n−∆h,如果存在l,使得则有

即存在di≥2,ki+1=1(1≤i≤m−2),与Th和Uh的定义矛盾.

当n−∆h+1≤l≤n−1,有

(4)设

满足k1+···+km=h1,d1+···+dm=h1−1.

我们分①和②两种情况讨论:

①∆h1≥2(k+1−h2)

当0≤l≤∆h1−2(k+1−h2)+1,有

当∆h1−2(k+1−h2)+2≤l≤n−∆h2,分以下两种情况:

(i)n−∆h1≥∆h2

当∆h1−2(k+1−h2)+2≤l≤∆h1,假设存在l使得必有km=1,且有

当∆h1+1≤l≤n−∆h2,有

假设存在l使得如果则有

否则,存在di≥2,ki+1=1(1≤i≤m−2),与Th和Uh的定义矛盾.

(ii)n−∆h1<∆h2

∆h1−2(k+1−h2)+2≤l≤n−∆h2时的证明与1)中∆h1−2(k+1−h2)+2≤l≤∆h1的情况相同.

当n−∆h2+1≤l≤n−1,有

②∆h1<2(k+1−h2)

当l=0,式(8)仍成立.当1≤l≤n−1,证明与(i)中∆h1−2(k+1−h2)+2≤l≤n−1 的情况相同.

(5)当l=0,若则αhs=uht,s=t,矛盾.当1≤l≤n−1,可通过结论(4)中①的证明方法得到,将α(h1)s替换成αhs,将替换成uht,∆h1替换成∆h,∆h2替换成

引理4[18]设如果集合和中的向量满足:

则布尔函数

代数免疫度最优,其中F(x)是择多函数.

记

定理1式(7)中的f(x)代数免疫度最优.

证明:根据引理4,考虑到中向量的顺序,要证f(x)代数免疫度最优,即证中的向量满足:

由引理3,上述条件均成立.于是f(x)代数免疫度最优.

4.2 非线性度

首先我们给出一些必要的引理和命题.

引理5[3]F(x)是n元择多函数,其中n=2k+1.对任意的以下结论成立.

(1)如果wt(α)=1,则

(2)如果wt(α)=n,则

(3)如果2≤wt(α)≤n−1,则

命题2设n=2k+1(k≥220),则以下不等式成立:

证明:对k进行归纳易证.

命题3令则

证明:当15≤k<220,直接计算可知不等式成立.

当k≥220,令

易见|R|=g(k+1).再令由(k+1,2k+1)=1 知,

引理6设n=2k+1(k≥17),则有

证明:令计算可得F(17)>0.F(k)是一个增函数(k≥17),因为

其中最后一个不等号用到了命题3的结论.

所以k≥17时,F(k)>0.于是

定理2设n=2k+1(k≥3),式(7)中f(x)的非线性度满足:

证明:对任意的ω∈,由式(4),式(7)和式(9),我们有

我们分以下四种情况讨论:

(1)wt(ω)=0,即ω=(0,0,··· ,0),由于f是平衡的,故Wf(w)=0.

(2)wt(ω)=1,我们有由引理5

此时,记|Wf(w)1|=|Wf(w)|.

(3)wt(ω)=n,即ω=(1,1,··· ,1),我们有n(−1)k+1.由引理5

(4)2≤wt(ω)≤n−1,由引理5

当3≤k≤12,直接计算可得当13≤k≤16,|Wf(w)| <|Wf(w)1|.当k≥17,由引理6

综上,当3≤k≤12,我们可以得到非线性度的一个下界,即当k≥13,在wt(ω)=1时,|Wf(w)| 最大,因此

表1比较了文献[12–15]与式(7)的布尔函数在k≥12时的非线性度.从表中可以看出本文构造的函数非线性度远大于其他构造,尤其是当k逐渐增大时,其优势更为明显.

表1 非线性度超过部分的比较Table 1 Comparison of enhanced values of nonlinearity upon

表1 非线性度超过部分的比较Table 1 Comparison of enhanced values of nonlinearity upon

n 文献[12]文献[13]文献[14]文献[15]本文f(7)25 4094 8034 5108 24 372 ≥87 520 27 8190 16 200 10 227 61 660 480 642 29 16 382 32 556 20 466 151 836 1564 614 31 32 766 65 294 40 945 376 958 5106 518 33 65 534 130 798 81 904 919 506 16 705 158 35 131 070 261 836 163 823 2249 930 54 760 830 37 262 142 523 944 327 662 5435 062 179 839 434

另一方面,从非线性度的表达式看,文献[13,15]与本文构造的布尔函数其非线性度的大小都与集合Th中的元素个数有关,而本文在集合的构造上保证了Th和Uh中有尽可能多的元素,从而使得布尔函数在非线性度上具有更大的优势.

4.3 代数次数

定理3式(7)中函数f(x)的代数次数满足的:

其中m是正整数,m≥3.

证明:函数f(x)等价于f(x)=F(x)+G(x),G(x)满足

因为wt(G)是偶数,所以由式(2)和式(3)知deg(f)≤n−1.G(x)的代数标准型中n−1 次项x0x1···xn−1/xi(0≤i≤n−1)的系数是集合和中满足第i个分量为0 的向量个数N(mod 2).由向量x={x0,x1,··· ,xn−1} 生成的轨道定义知,x的每一个分量都会出现在第i个位置.又知对任意的k≥3,有|T3|=1,|T4|=3.于是

由于deg(F)=2⌊log2n⌋,当n=2m+1时,deg(F)=n−1.由于F和G的代数标准型都包含所有的n−1 次项x0x1···xn−1/xi(0≤i≤n−1),因此deg(f)=deg(F+G)≤n−2.当2m+2≤n≤2m+1时,deg(F)≤n−2,因此deg(f)=deg(G)=n−1.

5 结语

本文构造了奇数元代数免疫度最优的旋转对称布尔函数,这类布尔函数在构造方法上通过修改择多函数支撑集,以增加函数的复杂性和改变密码学性质.从集合的构造看,我们构造的集合T和U比同类构造相应的集合拥有更多的元素,这就使得布尔函数具有比较高的非线性度.通过取特殊子集,我们保证了函数在n=2m+1时的最优代数次数.

但是,仍有一些问题值得我们深入研究,比如此类函数在7≤n≤23时是否仍有高非线性度,此类函数是否能有效抵抗快速代数攻击,如何构造相关免疫的旋转对称布尔函数等.这些都是我们今后的研究方向.