[最优代数免疫布尔函数的完全构造] 布尔逻辑运算符

   文章编号:1001-9081(2012)01-0049-03 doi:10.3724/SP.J.1087.2012.00049      �摘 要:任意的布尔函数可以唯一地表示成有限域上的单变元多项式函数,利用布尔函数的单变元多项式表示和代数编码理论,讨论了布尔函数的代数免疫达到最优的判别条件,得到了布尔函数的变元个数为奇数时,布尔函数具有最优代数免疫(MAI)的等价判别条件。利用该等价判别条件,给出3元布尔函数满足MAI的等价判别条件,进而构造出所有3元的MAI布尔函数。
  
  �关键词:布尔函数;代数免疫;代数攻击;Reed�Soloman码;代数编码
  �中图分类号: TN918.3; TP301 文献标志码:A
   �
   �
  Abstract: Any Boolean function can be uniquely expressed as a univariate polynomial function onover finite field. By using this representation and algebraic coding theory to discuss the criterion, by which a Boolean function achieves its Maximum Algebraic Immunity (MAI), the authors provided an equivalent criterion by which the algebraic immunity of a Boolean function with odd variables reaches MAI. According to the criterion, an equivalent condition to Boolean function of three variables that achieves MAI was reached. Thus, all MAI Boolean functions of three variables got constructed.
  
   Key words: Boolean function; algebraic immunity; algebraic attack; Reed�Soloman code; algebraic coding
  �
  
  0 引言�
  基于线性反馈移位寄存器的代数攻击方法一经提出,就对现有流密码体制形成了巨大的威胁。运用代数攻击的方法人们成功破解了用具有良好性质的布尔函数所设计的,能够抵抗所有已知攻击的Toycrypt和LILI�128[1-4]。布尔函数代数免疫的概念是由Meier等[5]于2004年美密会上提出的,代数免疫是衡量其抵抗代数攻击的能力。如何确定布尔函数的代数免疫及具有最优代数免疫(Maximum Algebraic Immunity, MAI)布尔函数的构造与计数成为密码学者关注的热点问题之一。文献[6-8]分别给出MAI布尔函数的三种构造方法,为布尔函数满足最优代数免疫判别提供一些依据。本文通过研究文献[8]中构造出的MAI函数,利用代数编码的相关理论,得到布尔函数满足最优代数免疫的一个判别条件,进而给出变元个数为奇数时布尔函数达到MAI的一个等价判别条件,并给出所有3元MAI布尔函数和4元MAI布尔函数的取值特征。�
  
  1 预备知识�
  本文中假设读者已经了解关于布尔函数的一些基础知识。�
  �设B�n是所有n元布尔函数f=f(x�1,…,x�n):GF(2)�n→GF(2)的集合,A�n是所有仿射函数的集合,A�n={f(x�1,…,x�n): f=λ�1x�1+…+λ�nx�n+λ},λ�i,λ∈F�2。�
  每个f∈B�n都可以表示成一个多变元多项式,即代数正规型(�Algebraic Norm Form, ANF�):�
  f(x�1,x�2…,x�n)=∑I�{1,2,…,n}a�I∏i∈Ix�i; a�I∈F�2�
  f≠0的代数次数定义为�deg�(f)=�max�{I:I�{1,2,…,n},a�I=1}。�
  通过选择F��2��n�在F�2上的一组基(α�1,α�2,…,α�n),可以建立F�n�2到F��2��n�的同构:�
  F�n�2F��2��n�:(x�1,x�2,…,x�n)x�1α�1+x�2α�2+…+x�nα�n�
  这样每个f∈B�n可以表示单变元多项式f=f(x)=∑2�n-1i=0a�ix�i,其中x,a�i∈F��2��n�。�
  在单变元多项式表示的情况下,0≠f∈B�n的代数次数定义为�deg�(f)=�max�{w�2(i):a�i≠0,0≤i≤2�n-1},其中w�2(i)为整数i的2��adic�分解的汉明重量,即若i=i�0+i�1•2+…+i��n-1�•2��n-1�,i�0,i�1,…i��n-1�∈{0,1},则w�2(i)=i�0+i�1+…+i��n-1�。易知在两种表示形式下, f代数次数的定义是等价的。�
  若f���-1�(0)=f���-1�(1)=2��n-1�,则称f是平衡的,此时�deg�(f)≤n-1。�
  向量(x�1,x�2,…,x�n)的汉明重量定义为w(x�1,x�2,…,�x�n)=�{x�i:x�i≠0,1≤i≤n}。n元布尔函数f的汉明重量定义为w(f)={α:α∈F��2��n�, f(α)=1}; f,g∈B�n,两者的汉明距离定义为d(f,g)={α∈F��2��n�: f(α)≠g(α)}。�
  在代数正规型的表示下,n元布尔函数f的�Walsh�变换定义为W�f(�λ�)=∑�x�=(x�1,x�2,…,x�n)∈F���n��2(-1)��f(�x�)+�λ�•�x��,其中�λ�=(λ�1,…,λ�n)∈F�n�2,�λ�•�x�=λ�1x�1+λ�2x�2+…+λ�nx�n。�
  在单变元多项式表示下, f的�Walsh�变换定义为�W�f(λ)=�∑x∈F��2��n�(-1)��f(x)+�tr�(λx)�,其中�tr�(α)=∑n-1i=0α��2���i�,α∈F��2��n�。非线性度是衡量布尔函数的密码学性质的重要指标, f∈B�n的非线性度定义为nl(f)=�min�{d(f,g):g∈A�n}。它也可以用�Walsh�表示为nl(f)=2��n-1�-12�max�{W�f(λ)},�nl(f)≤��2��n-1�-�2����n2-1�。�
  设f∈B�n,满足f(x)g(x)=0的非0函数g称为f的零化子。 f的所有零化子的集合记作An(f)。代数攻击的主要思想利用布尔函数的零化子,得到一个关于初态和输出密钥流序列的代数次数比较低的方程,从而减少多变量方程中变元的个数[4]。零化子代数次数越低,所得超定方程组的变元个数越少,代数攻击的复杂度越低。人们用代数免疫度来衡量布尔函数抵抗代数攻击的能力,定义如下。�
  定义1 设f∈B�n, f的代数免疫度记为AI(f),它是f的零化子和f+1的零化子中代数次数最低的零化子的次数,即:�
  AI(f)={�min� �deg�(g)|g∈An(f) �or� g∈An(f+1)}�
  布尔函数f的代数免疫度越大,函数抵抗代数攻击的能力越强;反之越弱。定理1是代数免疫度的一些性质。�
  定理1[5-6] 设f∈B�n,则:�
  1)AI(f)≤「n/2�;�
  2)设dd,则有∑d�i=0�C�i�n≤W(f)≤∑�n-(d+1)��i=0�C�i�n。��
  
  2 MAI布尔函数构造方法�
  Carlet等[8]利用布尔函数的单变元表达式以及代数编码的相关结论,构造出一类具有最优代数免疫的布尔函数。�
  �定理2[8] n为正整数,α为F��2��n�的一个本原元。设f是F��2��n�上的一个单变元多项式函数,其支撑集为{0,1,α,α�2,…,α��2��n-1�-2�},则f具有最优代数免疫「n/2�。�
  显然定理1中构造的函数是平衡函数,并且文献[8]还说明函数f具有较高的代数次数�deg�(f)=n-1和较高的非线性度nl(f)≥2��n-1�-(�ln� 2)n•2��n/2�-1。�
  文献[8]中还给出了定理2中函数的一般形式。�
  推论1 n为正整数,α为F��2��n�的一个本原元。设f是F��2��n�上的一个单变元多项式函数,其函数取值满足:对于任意的0≤i≤2��n-1�-1,�
  f(x)=0, x∈{α�i,α��i+1�,…,α��i+2��n-1�-1�}�1,其他�
  则AI(f)=「n/2�。�
  定理2利用�BCH�码的相关知识得到一类代数免疫达到最优的平衡函数。下面深入分析定理2中的方法,讨论布尔函数具有最优代数免疫时的判别条件,特别是在变元个数为奇数时,得到布尔函数函数代数免疫达到最优的等价判别条件。�
  设n为正整数,α为F��2��n�的一个本原元。设f是F��2��n�上的一个单变元多项式函数,其函数取值如定理1中所述,若g是f的零化子,则满足方程组式(1),即:�
  
  
  
  111…1�
  1αα�2…α��2���n-2��
  1α�2(α�2)�2…(α�2)��2���n-2��
  �����
  1α��2����n-1�-2�(α��2����n-1�-2�)�2…(α����2����n-1�-2��)��2���n-2�
  
  g��0��g��1��g��2����g��2���n-2�=0(1)�
  
  以(g�0,g�1,…,g��2�n-2�)为变量的方程组的解空间是设计距离为2��n-1�的�BCH�码。此时矩阵�
  
  H=111…1�
  1αα�2…α��2���n-2��
  1α�2(α�2)�2…(α�2)��2���n-2��
  �����
  1α��2����n-1�-2�(α��2����n-1�-2�)�2…(α����2����n-1�-2��)��2���n-2��
  
  
  的任意2��n-1�-1列都可以转化为是�Vandermonde�行列式,且�α�i≠�α��j, i≠j,故矩阵H的任意2��n-1�-1列都线性无关,故该�BCH�码的最小距离≥2��n-1�,即每个零化子的系数(g�0,g�1,…,g��2�n-2�)的汉明重量都≥2��n-1�。从而至少存在一个i,满足�w�2(i)≥�「n/2�+1,且g�i≠0。由此可知�deg�(g)≥「n/2�,即f没有代数次数0且当�w�2(i)≥��「n/2��时g�i=0。此时式(4)简化为:�
  ∑0≤i≤2�n-2,w�2(i)≤「n/2�-1H�ig�i=0(5)�
  令H′=(H�i)��w�2(i)≤「n/2�-1�,则式(5)无解当且仅当矩阵H′非退化。此时f没有代数次数0,即式(6)有非零解。这与已知条件矩阵H′非退化矛盾。故�deg�(g)   当n为奇数时,具有最优代数免疫的布尔函数一定是平衡的[5],若一个平衡布尔函数的单变元多项式表示满足定理2的条件,就具有最优代数免疫。实际上,矩阵H′非退化是奇数元布尔函数代数免疫达到最优的充要条件。�
  定理4 设n为奇数, f∈B�n是平衡函数,α是F��2��n�上的一个本原元, f的支撑集为{α����i��1�,…,α����i���2���n-1���}。符号H,H′和A的定义同上,则f具有最优代数免疫「n/2�的充要条件是矩阵H′非退化。�
  证明 充分性已证,下面证明必要性。�
  设g是f的一个零化子,g的单变元表示为g=∑2�n-2i=0g�ix�i,若矩阵H′=(H�i)��i∈A�退化,不妨H′=(H��i�0�,H��i�1�,…,H��i��|A|-1��),则存在非零向量(s��i�0�,s��i�1�,…,s��i��|A|-1��)满足:�
  s��i�0�H��i�0�+s��i�1�H��i�1�+…+s��i��|A|-1��H��i��|A|-1��=0�
  即:�
  α��i�0��1α��i�1��1…α��i��|A|-1���1�
  α��i�0��2α��i�1��2…α��i��|A|-1���2�
  ����
  α����i�0����2��n-1��α����i�1����2��n-1��…α����i��|A|-1�����2��n-1��
  s��i�0��s��i�1����s��i��|A|-1��=0�
  
  若单变元多项式函数g的系数写成向量形式为(g�0,g�1,…,g���2���n-2�),且分量g�i(1≤i≤2�n-2)取值满足:�
  g�i=s�i, i∈A�0,其他�
  于是有H(g�0,…,g��2���n-2�)��T�=0,当w�2(i)≥「n/2�时�g�i=�0,可知�deg�(g)≤「n/2�-1,从而知布尔函数g具有代数次数小于「n/2�的零化子,这与AI(f)=「n/2�矛盾,即证。这个“#”符号有何作用,是否可以删除,请明确。�
  由推论1可知,已知变元个数n,可以构造出2��n-1�个最优代数免疫布尔函数。这个数与代数免疫最优布尔函数的下界2��2��n-1��相距甚远。事实上,推论1是定理3的一个特殊情况,定理3给出了代数免疫达到最优时的一个必要条件,特别当变元为奇数时,定理4给出了布尔函数达到最优时的一个等价判别条件。下面给出3元布尔函数满足�MAI�的等价判别条件。�
  推论2 设f∈B�3是平衡布尔函数,其支撑集为�Supp(f)=�{α�1,α�2,α�3,α�4},α�i∈F��2�3�,i=1,2,3,4。则AI(f)=2当且仅当α�1+α�2+α�3+α�4≠0。�
  证明 因为n=3,则集合A={0,1,2,4},矩阵:�
  H′=1α�1α�2�1α�4�1�1α�2α�2�2α�4�2�1α�3α�2�3α�4�3�1α�4α�2�4α�4�4�
  由定理3可知AI(f)=2的充要条件是|H′|≠0,为计算�|H′|�,先考虑下面的�Vandermonde�行列式:�
  h(x)=1α�1α�2�1α�3�1α�4�1�1α�2α�2�2α�3�2α�4�2�1α�3α�2�3α�3�3α�4�3�1α�4α�2�4α�3�4α�4�4�1xx�2x�3x�4�
  多项式h(x)中x�3的系数为(-1)��2×4+1�|H′|=-|H′|,因为h(x)=(α�2-α�1)(α�3-α�1)(α�4-α�1)(x-α�1)(α�3-α�2)(α�4-α�2)(x-α�2)(α�4-α�3)(x-α�3)(x-α�4),故x�3的系数为-(α�1+α�2+α�3+α�4)∏1≤i中构造的一类布尔函数进行推广,讨论了单变元多项式函数达到最优代数免疫时的一个必要条件,并得到奇数元布尔函数达到最优代数免疫的充要条件,�同时给出n=3时的例子,�得到56个具有最优代数免疫的布尔函数,其数量远远大于推论1给出的4个具有最优代数免疫的布尔函数。
  
  �参考文献:�
  [1]
  COURTOIS N, MEIER W. Algebraic attacks on stream ciphers with linear feedback [C]// Advance in Cryptology-EUROCRYPT 2003, LNCS 2656. Berlin: Springer�Verlag, 2003: 345-359.
  �[2]
  COURTOIS N. Fast algebraic attacks on stream ciphers with linear feedback [C]// Advance in Cryptology-EUROCRYPT 2003, LNCS 2729. Berlin: Springer�Verlag, 2003: 176-194.
  �[3]
  ARMKNECHT F, KRAUSE M. Algebraic attacks on combiners with memory [C]// Advance in Cryptology-EUROCRYPT 2003, LNCS 2729. Berlin: Springer�Verlag, 2003: 162-175.
  �[4]
  MIHALJEVIE �M,� IMAI �H.� Cryptanalysis of �Toyocrypt�HSI� stream cipher [J]. IEICE Transactions on Fundamentals, 2002, E85�A(1): 66-73.
  �[5]
  MEIER �W,� PASALIC �E,� CARLET �C.� Algebraic attacks and �de��composition of Boolean function [C]// Advances in Cryptology-Eurocrypt 2004, LNCS 3027. Berlin: Springer�Verlag, 2004: 474-491.
  �[6]
  DALAI D K, GUPTA K C, MAITRA S. Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity [C]// FSE 2005: Proceedings of the 12th International Workshop on Fast Software Encryption, LNCS 3557. Berlin: Springer�Verlag, 2005: 98-111.�
  [7]
  LI NA, QI WENFENG. Construction and count of Boolean functions of an odd number of variables with maximum algebraic immunity [J]. Science in China Series F: Information Sciences, 2007, 50(3): 307-317.
  �[8]
  CARLET C, FENG KEQIN. An infinite class of balanced functions with optimal algebraic immunity, good immunity for fast algebraic attacks and good nonlinearity [C]// ASIACRYPT 2008: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, LNCS 5350. Berlin: Springer�Verlag, 2008: 425-440.
  �[9]
  CARLET C, DALAI D K, GUPTA K C, et al. Algebraic immunity for crypotographically significant Boolean functions: Analysis and construction [J]. IEEE Transactions on Information Theory, 2006, 52(7): 3105-3121.
  �[10]
  CARLET C. A method of construction of balanced functions with optimum algebraic immunity [EB/OL]. [2011-04-20]. http://eprint.省略/2006/149.
  �[11]
  CANTEAUT �A,� VIDEAU �M.� Symmetric Boolean �functions [J].� IEEE Transactions on Information Theory, 2005, 51(8): 2791-2811.
  �[12]
  CRAMA Y, HAMMER P. Boolean methods and models [M]. Cambridge, UK: Cambridge University Press, 2006.
  �[13]
  DING C, XIAO G, SHAN W. The stability theory of stream ciphers [M]. Berlin: Springer�Verlag, 1991.
  
   收稿日期:2011-08-03; 修回日期:2011-09-08
   基金项目:国防973项目(6138403005)
   作者简介:王永娟(1982-),女,河南开封人,讲师,博士,主要研究方向:密码学中的逻辑函数、密码编码理论; 张世武(1954-),男,黑龙江双城人,教授,主要研究方向:密码基础理论。

推荐访问:布尔 代数 最优 最优代数免疫布尔函数的完全构造 安全的布尔函数构造 可计算函数与布尔代数