Affine Equivalence Of Boolean Functions And Its Properties

Boolean functions are widely used in complexity theory,circuit synthesis,errorcorrecting codes,and cryptography,such as Boolean satisfiability problems,circuit design,Reed-Muller codes,and S-boxes.The affine transformation of Boolean functions corresponds to the role of XOR gates and NOT gates in logic circuits,and the affine equivalence of Boolean functions is of great significance to the equivalence classes of logic circuits and the synthesis methods of circuits.Many cryptographic properties of Boolean functions(such as nonlinearity,algebraic degree,algebraic immunity,etc.)remain unchanged under affine transformation,so the study of affine equivalence of Boolean functions plays an important role in studying the cryptographic properties of Boolean functions.However,due to the double exponential growth of Boolean functions and the complex structure of the affine group,it is very difficult to study the affine equivalence of Boolean functions.Aiming at the above problems,this dissertation studies the classification and checking problem of generalized affine equivalence of Boolean functions.Combined with the reachability analysis method of finite state machines,the applications of generalized affine equivalence of Boolean functions in circuit synthesis are studied.Finally,the affine equivalence method is applied to search for Boolean functions with excellent cryptographic properties.Specifically,the research results of this dissertation mainly include the following four parts:(1)The first work is computing the number of generalized affine equivalence classes of Boolean functions on R(s,n)/R(k,n).This dissertation studies the linear representation of the affine group on the quotient space of Boolean functions,and the isomorphism between affine group and the matrix group on the quotient space.The formula for calculating the number of generalized affine equivalent classes of Boolean functions is obtained by using the counting method of group theory.A permutation group is constructed to be isomorphic to the affine group and the matrix group,and the conjugate equivalence class of the matrix group is obtained by computing the conjugate equivalence class of the permutation group,which reduces the complexity of directly computing the conjugate class of the matrix group.In this way,this dissertation obtains the number of generalized affine equivalence classes of Boolean functions up to ten variables.(2)The second work is the affine equivalence checking problem of Boolean functions and circuit conversion.That is,for two given Boolean functions,determine whether the two functions can be transformed into each other through the affine transformation of the variables,and for the given affine transformation,design a circuit to realize this transformation.In this dissertation,a matrix transformation is designed for the function,so that the function values of the transformed function on the orthonormal basis are all equal,which reduces the number of possible pairs of the connecting functions,which reduces the search space of affine transformations.This dissertation demonstrates both theoretically and experimentally that the method reduces the size of the search space exponentially on average compared with previous methods when the truth table of the Boolean function is sparse.After finding the mathematical form of the affine transformation,this dissertation designs a greedy algorithm to synthesize circuits for the linear reversible transformations using the XOR gates.The proposed method presents for the first time a method for transforming a circuit into its affine-equivalent equivalent ones by synthesizing a linear reversible circuit and inserting it in front of the original circuit.This method automatically synthesizes an affine equivalent circuit for any given circuit by combining reversible and nonreversible circuits.(3)The third work is the generalized affine equivalence problem of Boolean functions,including the classification problem and the checking problem.Specifically,it includes the following three problems:according to the generalized affine equivalence of Boolean function,designing a strategy of circuit synthesis;for two given Boolean functions in R(s,n)/R(k,n),determining whether they can be transformed to each other through the affine transformation of the variables;classfifying R(s,n)/R(k,n)up to affine equivalence.This dissertation discusses the significant advantages of the circuit synthesis strategy based on generalized affine equivalence of Boolean functions over Boolean matching in terms of the size of circuit library.According to the theory of affine group acting on R(s,n)/R(k,n),Boolean functions are transformed into state vectors,and the affine transformation is transformed into the state transition relations,so that the generalized affine equivalence checking problem of Boolean functions is transformed into a reachability problem of finite state machines.Then,based on binary decision diagrams,bounded model checking and property directed reachability,three methods are proposed to solve the reachability problem.The advantages and disadvantages of these three methods on different problems are discussed experimentally.The checking method proposed in this dissertation not only successfully solves some checking problems of affine equivalence of Bent functions that cannot be solved by previous methods,but also proposes a method based on reachability analysis for the generalized affine equivalence checking problem of Boolean functions for the first time.Finally,this dissertation proposes a BDD-based method for affine equivalent classification of R(s,n)/R(k,n),and the classifications of R(7,7)/R(4,7)and R(6,6)/R(3,6)are obtained.(4)The last work is searching highly nonlinear resilient Boolean functions.By transforming the nonlinearity condition into linear inequality constraints on the truth table vector and the resilient order into linear equality constraints,this dissertation transforms the searching problem of the highly nonlinear resilient Boolean function into feasible problem of integer linear programming problems.Since there are too many variables when n≥ 8,this dissertation further proposes a searching method in the affine invariant subspace of Boolean functions,and demonstrates the effectiveness of searching in the affine invariant subspace,and obtains much richer subspaces than permutation invariant subspace.When the number of variables is less than or equal to 12,this method finds resilient functions with optimal nonlinearity in many cases,and also finds all resilient Boolean functions with the best known nonlinearity in the literature.The method is fast,and the functions obtained by searching are random,so it can provide a large number of resilient Boolean functions with excellent properties,and also provide a good method for searching functions that meet the requirements of various cryptographic properties.