刘华宁,陈晓林

(西北大学数学学院,陕西西安 710127)

1 引言

Boolean函数在流密码,分组密码以及散列函数的研究中起着重要作用.为了研究Boolean函数,人们提出了许多有关Boolean函数的密码学指标.

设 F2是一个二元域,Fn2是 F2上的一个n维线性空间,所谓n元Boolean函数B(x1,···,xn)是指从 Fn2到 F2的一个映射. 设 x=(x1,···,xn),a=(a1,···,an)∈Fn2,则〈a,x〉=a1x1+···+anxn表示通常的内积.Boolean 函数B(x1,···,xn)的最大 Fourier系数 ^B(a)定义为

Boolean函数B(x1,···,xn)的非线性定义如下

每一个Boolean函数都可以唯一地表示成多项式的形式,称为Boolean函数的代数正规型

Boolean函数的稀疏性spr(B)是代数正规型中非零系数单项式的个数.此外Boolean函数的平均灵敏度σav(B)定义如下其中a(i)是a改变第i个坐标后所得的向量.

近几年来,一些密码学研究者从数论的角度出发构造了许多具有“好”的密码学性质的Boolean函数.例如,Coppersmith与Shparlinski[1]利用模p的二次剩余构造了如下的Boolean函数.

命题1.1 设p为奇素数,s=blog2pc,其中bxc表示不超过x的最大整数.定义Boolean函数为

其中uj∈{0,1}且1≤j≤s.则有

Lange与Winterhof[2]将上述命题进行了推广.

命题1.2 设p为奇素数,Fq是阶为q=pr(r≥1)的有限域,β0,···,βr−1是Fq在Fp上的一组基,s=blog2pc.定义Boolean函数如下

其中ki−1=ui1+ui2·2+···+uis·2s−1,uij∈{0,1}且 1≤j≤s,1≤i≤r.则有

随后文献[3]进一步研究了命题1.2中Boolean函数的性质,得到了以下结果.

命题1.3 设p,r,s,B如以上命题所定义.则有

最近几十年来,随着数论、组合以及相关学科的发展,伪随机子集得到了深入的研究和广泛的应用.许多论文都是关于这一领域的,这些论文中提出了大量的思想、方法和工具.1992年,Chung与Graham[4]发现整数环的子集具有一类令人惊奇的互相等价的性质,并且如果一个子集满足这类性质中的任何一条,则满足其余性……