高次非正规布尔函数的存在性
|
摘要
基于布尔函数代数正规型及正规性的定义和性质,通过计数的方法,研究了非正规且具有较高代数次数的布尔函数的存在性。结论表明,随着变元个数的不断增大,高次非正规布尔函数在整个函数空间中的比率越来越大,当变元个数趋于无穷时比率趋近于1。该结论为对称密码中密码函数的选取提供了支持。特别地,指出了四次非正规布尔函数变元个数的下界。
Based on the definition and properties of the algebraic normal form and normality of Boolean functions,the existence of nonnormal Boolean functions with high algebraic degrees was proved.By counting,it was shown that the ration of the nonnormal Boolean functions with high degress grows with the number of variables,and tends to 1 when it becomes infinite.Especially,the minimum bound of the number of variables of nonnormal Boolean functions with algebraic degree 4 was provided.
Based on the definition and properties of the algebraic normal form and normality of Boolean functions,the existence of nonnormal Boolean functions with high algebraic degrees was proved.By counting,it was shown that the ration of the nonnormal Boolean functions with high degress grows with the number of variables,and tends to 1 when it becomes infinite.Especially,the minimum bound of the number of variables of nonnormal Boolean functions with algebraic degree 4 was provided.
引文
[1]LUPANOV O B.On circuit of functional elements with delay[J].Probl Kibern,1970,23:43-81.
[2]OLEJAR D,STANEK M.On cryptographic properties of random Boolean functions[J].Journal of Universal Computer Science,1998(4):705-717.
[3]CARTET C.On the degree,nonlinearity,algebraic thickness,and nonnormality of Boolean functions,with developments on symmetric functions[J].IEEE Transactions on Information Theory,2004,50(9):2178-2185.
[4]DOBBERTIN H.Constructions of bent functions and balanced Boolean functions with high nonlinearity[J].Fast Software Encryption,Lecture Notes in Computer Science,Springer-Verlag,1994,1008:61-74.
[5]CARLET C.On the Complexity of Cryptographic Boolean Functions.Proc.6th Conf.Finite Fields With Applications to Coding Theory[M].Berlin:Springer,2002:53-69.
[6]MAC WILLIAMS F J,SLOANE N J.The Theory of Error-Correcting Codes[M].Amsterdam:Publishing Company,1977.
[2]OLEJAR D,STANEK M.On cryptographic properties of random Boolean functions[J].Journal of Universal Computer Science,1998(4):705-717.
[3]CARTET C.On the degree,nonlinearity,algebraic thickness,and nonnormality of Boolean functions,with developments on symmetric functions[J].IEEE Transactions on Information Theory,2004,50(9):2178-2185.
[4]DOBBERTIN H.Constructions of bent functions and balanced Boolean functions with high nonlinearity[J].Fast Software Encryption,Lecture Notes in Computer Science,Springer-Verlag,1994,1008:61-74.
[5]CARLET C.On the Complexity of Cryptographic Boolean Functions.Proc.6th Conf.Finite Fields With Applications to Coding Theory[M].Berlin:Springer,2002:53-69.
[6]MAC WILLIAMS F J,SLOANE N J.The Theory of Error-Correcting Codes[M].Amsterdam:Publishing Company,1977.