布尔函数特征矩阵变换的若干性质及其应用
青春年少赵静;赵清香
【摘 要】证明了布尔函数的零化子在其特征矩阵变换下具有同变性,由已知的代数免疫函数得到其它的代数免疫函数,并给出了若干实例.
【期刊名称】《商丘职业技术学院学报》
【年(卷),期】2011(010)002
【总页数】3页(P4-6)
【关键词】布尔函数;特征矩阵;零化子;代数免疫
影视编导【作 者】赵静;赵清香
【作者单位】河南师范大学外国语学院,河南新乡453007;河南师范大学附属小学,河南新乡453007
【正文语种】中 文
【中图分类】O151.21
2003年，法国的密码学家Nicolas和Wilimeier提出了基于线性反馈移位寄存器的代数攻击方法［1］，使以前具有很好密码学性质的布尔函数受到了极大的挑战，对密码学中使用的布尔函数提出了更高的要求，代数攻击引起了密码学家们的广泛关注.为了衡量布尔函数抵抗代数攻击能力，Meier等提出了代数免疫(algebraic immunity，简记为AI)的概念［2］，使用代数免疫度高的布尔函数是抵抗代数攻击的必要条件，如何得到具有良好代数免疫特性尤其是具有最优免疫度的布尔函数的构造问题是目前的一个热点问题，出现了一大批有价值的结果［1-10］.
本文在特征矩阵变换的基础上初步研究了具有代数免疫性的布尔函数的性质问题，得到了一些结果，给出了一个由布尔函数特征变换的方法来构造最优代数免疫函数的方法.
设n是任意的正整数，F2是二元域表示n维Boole空间，映射称为n元Boole函数，Bn表示所有n元Boole函数构成的集合，Boole函数f的Hamming重量记作wt(f)，若wt(f)=2n-1，则称f
为平衡函数，一个n元Boole函数f(x)=f(x1，x2，……，xn)可以用如下的代数标准型(ANF)来表示:
重拾记忆这里的系数a0，a1，……，a12……n∈F2.
定义1［11］设n=2t+1为奇数，称函数F(x)为严格择多函数.
定义2［12］设Cf为Boole函数f(x)的特征矩阵，交换特征矩阵的任意两行，我们称为特征矩阵行变换;交换特征矩阵的任意两列，我们称为特征矩阵列变换;将特征矩阵某列的数码0和1互换，我们称之为特征矩阵数码变换;特征矩阵的行变换，列变换和数码变换统称为特征矩阵变换.
mv下载
由于特征矩阵的行变换并不改变这个矩阵所对应的布尔函数，因此下文中的特征矩阵变换是指特征矩阵的列变换和数码变换.
定义3［2］设f(x)和g(x)是n元Boole函数，如果f(x)g(x)=0，称g(x)是f(x)的零化子，f(x)的非零零化子和f(x)⊕1的非零零化子的次数k称为f(x)的代数免疫阶，记为AI(f)，当k取得最大值时，则称f(x)为代数免疫函数或者具有最优AI的布尔函数.如未特别说明，下文中的零化子
均指非零的.
若对Boole函数f(x)的特征矩阵进行特征矩阵变换，若记变换以后得到的特征矩阵所对应的Boole函数为g(x)，则f(x)和g(x)具有相同的代数次数，那么Boole函数的代数次数是特征矩阵变换中的不变量，显然Boole函数的相关免疫阶也是特征矩阵变换中的不变量，关于特征矩阵变换，我们有以下结果:
定理1设f(x)=f(x1，x2，……，xn)是一个n元Boole函数，那么函数g(x)=g(x1，x2，……，xn)是f(x)的零化子的充分必要条件是:g'(x)=g(x1，x2，…，xi-1，xi+1，xi+1，…，xn)是函数f'(x)=f(x1，x2，…，xi-1，xi+1，xi+1，…，xn)的零化子
证明:必要性.设f(x)是一个n元Boole函数，g(x)是它的一个零化子，f'(x)=f(x1，x2，…，xi-1，xi+1，xi+1，…，xn)，那么f'(x)的特征矩阵实际上就是将f(x)的特征矩阵的第i行进行数码变换后得到的，g'(x)=g(x1，x2，…，xi-1，xi+1，xi+1，…，xn)是由g(x)的代数标准型中的xi变为xi+1而得到的，它的特征矩阵是由g(x)进行第i列的数码变换后得到的，由零化子的定义可知:g'(x)是f'(x)的零化子.由于以上各步可逆，充分性由必要性可得.
铬黑t指示剂
这个定理说明了:Boole函数的零化子对于数码变换具有同变性，而且揭示了这种变化的规律性，自然地有下面的推论:
推论设f(x)=f(x1，x2，……，xn)是一个n元布尔函数，那么函数g(x)=g(x1，x2，……，xn)是f(x)的零化子的充分必要条件是:
g'(x)=g(x1+c1，x2+c2，…，xi+ci，…，xn+cn)是f'(x)=f(x1+c1，x2+c2，…，xi+ci，…，xn+cn)的零化子，其中的(c1，c2，……，cn)∈Fn2.
定理2 Boole函数f(x)=f(x1，x2，……，xn)与f'(x)=f(x1，x2，…，xi-1 xi+1，xi+1，…，xn)具有相同的代数免疫阶.
证明:由定理1可知:f(x)=f(x1，x2，……，xn)经过数码变换以后得到
如果g(x)是f(x)的零化子等价于g'(x)=g(x1，x2，…，xi-1，xi+1，xi+1，…，xn)是f'(x)的零化子，显然g'(x)可以看做是由g(x)进行数码变换后得到的，由定理1可知，它们具有相同的代数次数，那么如果函数g(x)是k阶代数免疫函数f(x)的零化子，那么g'(x)是f'(x)的k次零化子，反之亦然.这就是说，对于f(x)和f'(x)，只要找到了其中一个函数的k次零化子，相应的
就可以另外一个函数的一个k次零化子.所以它们一定有相同的代数免疫阶.
这个定理说明了一个Boole函数的特征矩阵经过列的数码变换后得到的新的特征矩阵所对应的新的Boole函数与原来的函数具有相同的代数免疫阶，即代数免疫阶是特征矩阵变换中的不变量.
定理3 交换一个Boole函数f(x)的任意两列，得到Boole函数f'(x)，若g(x)是f(x)的零化子，那么交换g(x)的对应两列得到的矩阵是f'(x)的零化子g'(x).进一步，它们有相同的代数免疫阶.
证明:设交换Boole函数f(x)的第i列和第j列(i＜j)，得到的函数记为f'(x)，f'(x)的零化子记为g'(x).而f'(x)的代数标准型是将f(x)的代数标准型表达式中的xi和xj互换而得到的，若g(x)是f(x)的零化子，则f(x)g(x)=0，在f(x)和g(x)得代数标准型中交换自变量x的第i和第j个分量后有:
f(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)g(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)=0，这说明g(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)是f'(x)=f(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)的
零化子，而g(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)是由g(x)交换自变量x的第i和第j个分量后得到的，从而g(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)的特征矩阵是将g(x)的特征矩阵交换第i列和第j列得到的，即g'(x)=g(x1，x2，…，xi-1，xj，xi+1，…，xj-1，xi，xj+1，…，xn)，f(x)可以看做由f'(x)变来的，反过来也是成立的，f(x)和f'(x)有相同的代数免疫阶，命题获证.
相与步于中庭
这个定理说明了一个布尔函数与它的零化子具有同变性.
设f(x)为严格择多函数，C为其特征矩阵，那么将C进行列变换以后得到的函数还是f(x)，显然将C进行数码变换后得到的矩阵对应的函数也是代数免疫函数.
例设f(x)为3元的择多函数，则f(x)的特征矩阵为
由引理可知它是具有最优代数免疫的布尔函数，对第一列，第二列，第三列分别进行数码变换后得到的函数依次为:C1，任意两列同时进行数码变换后得到的布尔函数依次为:
C12，对三列都做数码变换得到:C123，然后考虑对以上的7个矩阵进行列变换得到的矩阵仍然是上面的7个.根据上述定理可知:这些函数的代数免疫阶都是2，这些函数虽然没有文
［10］中定理1、3、5构造的函数个数多，但是可以看出:C12、C13、C23、C123中包含了全零行，所以它们并不包含在文［10］中任何一种方法构造的函数中，是新得到的4个3元代数免疫函数.
【相关文献】
［1］Courtois N，Meier W.Algebraic attacks on stream ciphers with linear feedback.In:Biham E，ed.Advances in Cryptology-EUROCRYPT 2003［C］.LNCS，Vol.2656.Berlin:Springer-Verlag，2003.346-359.手冷怎么办
［2］Dalai D，Maitra S，Sarkar S.Basic theory in construction of Boolean functions with maximum possible annihilator immunity［J］.Des Code Crypt，2006，40(01):41-58.
［3］Braeken An，Preneel B.On the algebraic immunity of symmetric Boolean functions［C］.INDOCRYPT2005.Springer-Verlag，3797:35-48.
［4］Li N，QiW.Construction and Analysis of Boolean functions of 2t+1 Variables with Maximum Algebraic Immunity［C］.Advances in Cryptology-ASIACRYPT 2006.Ber-lin:S
pringer-Verlag，2006，4282:84-98.
运动素材
［5］Li N，Qu L J，QiWF.On the Construction of Boolean Functions with Optimal Algebraic Immunity［J］.IEEE Transon Information Theory，2008，54(03):1330-1334.
