Analysis of affinely equivalent Boolean functions

Science in China Series F: Information Sciences◎2007Science in China Press包SingrVeragAnalysis of affinely equivalent BooleanfunctionsMENG QingShu1*, ZHANG HuanGuo'2, YANG Min3 & WANG ZhangYi'1 Computer School, Wuhan University, Wuhan 430074, China;2 State Key Laboratory of Software Engineeing, Wuhan University, Wuhan 430074, China;3 Intemational School of Sotware, Wuhan University, Wuhan 430074, ChinaBy some basic transforms and invariant theory, we give two results: 1) an algorithm,which can be used to judge if two Boolean functions are affinely equivalent and toobtain the equivalence relationship if they are equivalent. This is useful in studyingBoolean functions and in engineering. For example, we classify all 8-variable ho-mogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codesR(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.Boolean functions, Reed-Muller code, affinely equivalent, invariant1 IntroductionBoolean functions are widely used in science and engineering, like in circuit design, cryptographyand error-correction coding. The affine classification of Boolean functions is meaningful. In thedesign of combinational circuit, if one circuit is well designed, all Boolean functions that are af-finely equivalent to the circuit can be implemented through this circuit. Out of the need of circuitdesign, many scholars discussed the classification of Boolean functionsl-s in the 1960s of the20th century. In cryptography, as Boolean functions are widely used in block ciphers and streamciphers, many scholars'ts discussed the cryptographic properties of affinely equivalent Booleanfunctions. All affinely equivalent Boolean functions have similar cryptographic properties. Inerror-correction coding area, the classification of Boolean functions was discussed too'. In short,studying the classification of Boolean functions is very necessary.There are two main research problems in the analysis of affinely equivalent Boolean functions.The first one is the classification of Reed-Muller codes and the second is deciding whether twoBoolean functions are affinely equivalent and getting the equivalence relationship when they areequivalent. There are a lot of results about the first problem. All 5-variable Boolean functions wereclassified into 48 equivalence classes by Berlekamp and Welch!S!. By decomposing 6 variableReceived July 14, 2006; acepted March 27, 2007中国煤化工doi: 10.1007s11432007 0030-9Corresponding author (email: mqseagle@sohu.com)出CNMHGSupported by the National Natural Science Foundation of China (Grant Nos. 699730.+. wisuor,wus1)www.scichina.com www.springerlink.comSci China Ser F-Inf Scil June 2007 Ivol. 50 I no. 3 I 299-306Boolean functions into 5-variable Boolean functions and using AGL(5,2) on 5-variable Booleanfunctions, Maioranall classified all 6-variable Boolean functions into 150357 equivalence classes.Another good result is that the formula for calculating the number of orbits of R(r,m)/ R(s,m)under the action of the general afine group was given by Houl89. For m= 6 and 7, the numberwas calculated out in ref. [9], which makes it possible to classify the R(6,6)/R(1,6) andR(7,7)/R(1,7) using invariant theory. For example, using invariant theory, Houl8l classifiedR(3,7)/R(2,7), R(3,8)/ R(2,8) and Brier and Langevin10] classified R(3,9)/ R(2,9). However,the classification of R(r,m)1R(s,m) for r-s>1 is seldom discussed. On the second researchproblem, we can only find two papersh”. However, both methods fail in the case of bent functions.Using basic transforms and invariant theory, we give two results: 1) an algorithm, which can beused to judge if two Boolean functions are affinely equivalent and to obtain the equivalence rela-tionship when they are equivalent. This is useful in studying Boolean functions and in engineer-ng. For example, we classify all 8-variable homogeneous bent functions of degree 3 into twoclasses; 2) Reed-Muller codes R(4,6)/ R(1,6),R(3,7)/R(1,7) are classified efficiently. Recentlyand independently, also using invariant Braeken, Borisov, Nikova, et al."13] classfiedR(4,6)/ R(1,6), R(3,7)/R(1,7).2 PremilinariesThe Galois field with two elements is denoted by F2 and the vector space of dimension n overF2 is denoted by F2". For each subset sC {L,2,.",n}, there exists a corresponding vector(<,S2,",sn) by letting s;=1 if element i isin s else letting s; = 0. And the binary vector(s,2..",sn) can be denoted by an integer s whose 2-adic expansion is just the vector(5.52.,.',sn). Obviously, the set, the vector and the integer are isomorphic. In this paper, if con-fusion is not caused, we will use the three notations for description convenience.The set of all Boolean functions in n variables is denoted by pn. For each subsets∈{,2.,.,n}，we have x° =] xq∈ pr. The algebraic normal form of a Boolean function canESbe witten as f(x)=a,x"，where ag∈F. The degree of f(x) is defined as deg(f)=s=s.01,--.2" -1}.x0maxH(s)，where H(s) is the Hamming weight of s. Let R(r,n)={f(x)∈Pn |deg(f)≤r} be the rth order Reed-Muller code. For 0≤s(<).>The following two propositions are already known, for example, see ref. [14]. And the fact thatthe distribution of absolute Walsh spectra and autocorrelation function are invariants is known dueto Preneel's workl5I.Proposition 114. Let n,r be two positive integers such that 1≤r≤n. Let f(x)∈ R(r,n)and 8(x)= f(xA+b)+l.x+c, where c∈F，x,b,l∈F2"， A∈GL(n,2). For any w∈ F",we haves(()=()40bN+os