Construction of Boolean functions with maximum algebraic immunity and count of their annihilators at lowest degree  

作　　者：DU YuSong PEI DingYi 

机构地区：[1]School of Mathematics and Information Sciences,Guangzhou University,Guangzhou 510006,China

出　　处：《Science China(Information Sciences)》2010年第4期780-787,共8页中国科学(信息科学)(英文版)

基　　金：supported by the National Natural Science Foundation of China (Grant No. 90604034)

摘　　要：Boolean functions used in stream ciphers against algebraic attacks are required to have a necessary cryptographic property-high algebraic immunity (AI). In this paper, Boolean functions of even variables with the maximum AI are investigated. The number of independent annihilators at the lowest degree of Boolean functions of even variables with the maximum AI is determined. It is shown that when n is even, one can get an (n + 1)-variable Boolean function with the maximum AI from two n-variable Boolean functions with the maximum AI only if the Hamming weights of the two functions satisfy the given conditions. The nonlinearity of the Boolean functions obtained in this way is computed. Similarly, one can get an (n + 2)-variable Boolean function with the maximum AI from four n-variable Boolean functions with the maximum AI. The nonlinearity of a class of Boolean functions with the maximum AI is determined such that their Hamming weights are either the maximum or the minimum.Boolean functions used in stream ciphers against algebraic attacks are required to have a necessary cryptographic property-high algebraic immunity (AI). In this paper, Boolean functions of even variables with the maximum AI are investigated. The number of independent annihilators at the lowest degree of Boolean functions of even variables with the maximum AI is determined. It is shown that when n is even, one can get an (n + 1)-variable Boolean function with the maximum AI from two n-variable Boolean functions with the maximum AI only if the Hamming weights of the two functions satisfy the given conditions. The nonlinearity of the Boolean functions obtained in this way is computed. Similarly, one can get an (n + 2)-variable Boolean function with the maximum AI from four n-variable Boolean functions with the maximum AI. The nonlinearity of a class of Boolean functions with the maximum AI is determined such that their Hamming weights are either the maximum or the minimum.

关 键 词：Boolean function algebraic attack algebraic immunity ANNIHILATOR NONLINEARITY 

分 类 号：TN918.1[电子电信—通信与信息系统]