一次扩散布尔函数的一些密码学性质

黄景廉， 张椿玲

（西北民族大学 电气工程学院，甘肃 兰州 730030）

0 引言

在现代密码体制的安全性中，布尔函数的密码学性质是起关键作用的因素之一[1-3]。将导数和自定义的 e-导数结合在一起引入到布尔函数密码学性质研究中[4]，有将布尔函数取值的不同特点区分开，以区别分析的优点，能导出一些用传统研究工具，如频谱方法等[5-6]不易导出的新的密码学性质，这里以导数和自定义的 e-导数结合作为新的研究工具，来研究H布尔函数[7-8]的一些密码学性质。

1 一些预备性概念

e-导数是为研究布尔函数的密码学性质自定义的，导数在密码学研究中因单独使用起不了什么作用而几乎不用[1-2,5]。本文以e-导数和导数作研究工具，因此，需要对e-导数的概念，及e-导数和导数与布尔函数的扩散性的基本关系作一简略介绍。

定义1 n元布尔函数f (x)对变元xi1,xi2,…,xir的e-导数记为ef(x)/e(xi1,xi2,…,xir)，并定义为：

其中，f (x)对单个变元xi(i=1,2,…,n)的e-导数，经简单推导，有如下便于使用的形式：

由e-导数和导数的定义，可直接得到引理1和引理2。

引理1 n元布尔函数f(x)对相同变元的e-导数和导数的积为零。

引理2 对任意n元布尔函数f(x)，有如下关系：

很轻易就能用导数来描述布尔函数 f(x)的扩散性。

引理3 布尔函数f(x)满足k (1≤k≤n)次扩散准则，当且仅当对一切 xi1,xi2,…,xik，(1≤k≤n, 1≤i1＜i2…＜ik≤n)，有：

特别地，f(x)满足一次扩散准则，当且仅当对一切xi，(i=1,2,…,n)，有：

由引理2的关系4和引理3，可以得出引理4和引理5。

引理4 f(x)是平衡H布尔函数，当且仅当对一切i=1,2,…,n，有：

2 布尔函数、H布尔函数的密码学性质

下面对 0＜w(f (x))＜2n中的布尔函数讨论其密码学性质。

性质 1 对布尔函数 f(x)（x∈GF(2)n，f(x)≠c，c∈GF(2)），若：

则f(x)是一阶相关免疫函数[9]。

式(3)只是 f(x)一阶相关免疫的充分条件，而不是必要条件。

性质 2 若 n元布尔函数 f1(x)和 f2(x)有w(f1(x))=w(f2(x))，且：

则f1(x)和f2(x)的级联函数：

是n+1元一阶相关免疫函数[9]。

由性质2可得如下推论。

推论1 把n元布尔函数f(x)看成由2n-3个3元布尔函数 fi(x) (x = xn-2xn-1xn，i=1,2,…,2n-3)级联构成，且有：

∂fi(x)/∂(xn-2xn-1xn)=0, i=1,2,…, 2n-3, 即：

则f(x)是一阶相关免疫函数。

性质 3 在 w(f(x))=2n-1+2n-2的布尔函数中，当n≥3时，存在一阶相关免疫的H布尔函数；当n≥5时，存在二阶相关免疫的H布尔函数[9]。

下面给出对任意n的一般性讨论结果。

1）对f(x)为w(f(x))=2n-1+2n-2的H布尔函数，n≥3时，存在而且可构造出一阶相关免疫的f(x)。

2）对 f(x)是 w(f(x))=2n-1+2n-2的一阶相关免疫的H布尔函数，将2个n=4的函数级联得到的n=5的f(x)为二阶相关免疫的H布尔函数。

由 f1(x)、 f2(x)、 f3(x)、f4(x)任意次序的级联，只要保证在第i次级联时，df(x)/dxi都保证不会使其中某一个函数和自身相加，则级联构成的f(x)就一定是H布尔函数（由引理3即可证明）。

例1 将f1(x), f2(x), f3(x), f4(x), f4(x), f3(x), f2(x), f1(x)依次逐步级联，所得函数：

是二阶相关免疫的H布尔函数。

例2 以3元函数f3(x), f4(x), f1(x), f2(x), f2(x), f1(x),f4(x), f3(x)依次序两两逐步级联得：

则fr(x)是二阶相关免疫H布尔函数。

3）存在任意 n维的二阶相关免疫的w(f(x))=2n-1+2n-2的H布尔函数。

4）当 n≥6时，存在三阶相关免疫w(f(x))=2n-1+2n-2的H布尔函数。

给出一个三阶免疫的例子例3。

例3 将例1中的二阶相关免疫H布尔函数f(x)改记为ft(x)，对ft(x)和例2中的fr(x)，有：

但对其余xi+xj+xk，均有：

将ft(x)和fr(x)的变元角标均增大1，即将x5记为x6，表示为 x5→x6，其余 x4→x5，x3→x4，x2→x3，x1→x2，然后将改变角标后的ft(x)和fr(x)用变元x1作级联，所得级联函数 f(x)=(1+x1) ft(x)+x1fr(x)是 n=6的w(f(x))=2n-1+2n-2的三阶相关免疫H布尔函数。

性质4 平衡H布尔函数如果是相关免疫的，则它只能最高为一阶相关免疫函数。

证明 根据引理4，性质1和性质2的推论1可知，当n≥4时，一阶相关免疫的H布尔函数是存在的且易于构造的。如，可由二元 H布尔函数f44(x)=1+xn-1+xn+xn-1xn逐步级联构成且总保持性质2推论1的要求，即一阶相关免疫的平衡H布尔函数是存在的，取f(x)为一阶相关免疫的平衡H布尔函数，故有：

由引理 4及式(8)、式(9)知，f(x)是一阶相关免疫,当且仅当:

由于 f(x)一阶相关免疫,必有 w(xif(x))=2n-2,又w(xi)=2n-1,故必有:

故必有:

由于式(11)、式(12)，若假设 w(xief(x)/exk) ≠2n-3而 是 w(xief(x)/exk)=2n-3+2n-r(r≥3)， 则 必 有w(xidf(x)/dxk)=2n-3-2n-r，于是式(10)要成立，必有：

由式(13)及式(10)，必有：

反之，若式(13)、式(14)成立，则式(10)成立，f(x)是一阶相关免疫。故 f(x)一阶相关免疫当且仅当式(13)、式(14)成立。

在f(x)已一阶相关免疫的条件下，现在来讨论f(x)是否为二阶免疫。和性质3的讨论相似，可得到：f(x)是二阶相关免疫，当且仅当：

和式(13)、式(14)的讨论相似，也有 f(x)二阶相关免疫，当且仅当：

取 k=n，则 w(ef(x)/exn)=2n-2。分析 xn-1，1+xn-1，xn-2xn-1，xn-2(1+xn-1)，(1+xn-2)xn-1，xn-3xn-1这几个函数的特点，以及如下关系：

则若f(x)二阶免疫，由式(16)，必有：

若式(19)不成立，f(x)不是二阶免疫已得证，若成立，又必有：

则由于式(17)的关系，可能((1+xn-2)xn-1ef(x)/exn)=0，这时f(x)不是二阶免疫已得证，或者可能仍有：

但若式(21)成立，则由于式(18)的关系，必有：

故知，f(x)一定不是二阶相关免疫函数，性质得证。

从性质4的式(13)，式(16)的证明中，以及性质1的结果，可得出如下推论。

推论1 如果布尔函数f(x)有w(f(x))=2n-2，且df(x)/dxn=0，w(ef(x)/exn)=2n-2，则 f(x)相关免疫的阶数最高为一阶，f(x)一定不是二阶相关免疫函数。

从性质 3、性质 4的式(13)、式(14)、式(16)的证明及结论，可以得出如下推论。

推论2 对布尔函数 f(x)，若 df(x)/dxi≠0，ef(x)/exi=0,i=1,2,…,n，则 f(x)二阶相关免疫当且仅当 g(x)=df(x)/dxi,i=1,2,…,n二阶相关免疫。

推论3 对布尔函数f(x)，记g(x)= f(x)df(x)/dxn，h(x)=ef(x)/exn，则f(x)二阶相关免疫当且仅当g(x)与h(x)均二阶相关免疫，即当 g(x)与 h(x) 均不二阶相关免疫，也必有f(x)不是二阶相关免疫函数。

推论3说明，g(x)与h(x)只要其中有一个不二阶相关免疫，则必有f(x)不二阶相关免疫。

性质 5 布尔函数 f(x)有 0＜w(f(x))= w(ef(x)/ exn)＜2n-1，即df(x)/dxn=0，则f(x)一定不是二阶相关免疫函数[9]。

由性质4的推论3和性质5，可得到如下一系列推论：

推论 1 若 f(x)为 w(f(x))＜2n-2，ef(x)/exn=0，则f(x)一定不是二阶相关免疫函数。

证明 由性质1知，存在一阶相关免疫的f(x)，而由性质5知f(x)二阶相关免疫当且仅当g(x)= df(x)/dxn二阶相关免疫，但g(x)由性质5知不是二阶相关免疫函数，故f(x)不是二阶相关免疫函数。

推论2 对w(f(x))＞2n-1+2n-2的f(x)，必不是二阶相关免疫函数。

推论 3 对 2n-2＜w(f(x))＜2n-1+2n-2中的 H 布尔函数，一定不是二阶相关免疫函数。

由于 w(df(x)/dxn)=2n-1，0＜w(ef(x)/exn)＜2n-1，则由性质4的推论3及性质5即得证。

3 结语

本文对一次扩散布尔函数的一些密码学性质进行了讨论，为提高密码系统抵抗相关攻击的能力提供了理论依据，这一结果对指导设计具有较高安全性的密码系统有实际意义。

[1]李世取,曾本胜, 廉玉忠,等.密码学中的逻辑函数[M].北京: 北京中软电子出版社,2003.

[2]温巧燕,钮心忻,杨义先.现代密码学中的布尔函数[M].北京:科学出版社,2000.

[3]陈民,邹传云.基于非线性译码问题的RFID安全协议[J].通信技术,2010,43(11):118-122.

[4]LI Weiwei, WANG Zhuo, HUANG Jinglian.The E-derivative of Boolean Functions and Its Application in the Fault Detection and Cryptographic System[J].Kybernetes(SCI), 2011,40(5-6): 905-911.

[5]温巧燕,张劼,钮心忻,等.现代密码学中的布尔函数研究综述[J].电信科学,2004,20(12):43-46.

[6]齐云,刘玉孝.相关免疫函数和Hamming重量之间的关系[J].通信技术,2008,41(12):363-365.

[7]杨义先.N元H-布尔函数[J].北京邮电学院学报,1988,11(03):1-9.

[8]杨义先,邢育森.N元H布尔函数(Ⅱ)[J].电子科学学刊,1997,19(02):214-216.

[9]HUANG Jinglian, WANG Zhou.The Categories of the Correlation-measure of the Linear Proliferation Boolean Functions[C].[s.l.]:WNIS, 2010:93-96.