Concatenated Construction And Analysis Of The Linear Structures Of Boolean Functions

Boolean functions have great applications in the design of cryptosystems. From some extend the security of some cryptosystems is due to the cryptographic properties of Boolean functions, such as nonlinearity, algebraic degree, correlation immunity, propagation, linear structure, algebraic immunity and so on. But there exists restrictions between some properties. It is therefore meaningful to study the relationships between these cryptographic properties for constructing Boolean functions with good cryptographic properties. The interrelationship among partial properties of Boolean functions as well as the applications of concatenated construction is investigated in this dissertation. The main results are as follows.Firstly, the linear structures and the fast points of rotation symmetric Boolean functions are studied. Two open problems about the relationship between the linear structure and the algebraic degree of rotation symmetric Boolean functions are discussed. They were proposed by Elsheh that the balanced rotation symmetric Boolean functions on even number of variables with degree n-1and the rotation symmetric Boolean functions on odd number of variables with degree n-2both have no non-zero linear structure for every n>3. The first open problem is completely proved and the second open problem is proved to be correct when3n. A necessary ondition is given if the second open problem is not true when3|n.Secondly, the Walsh spectrum of one class of rotation symmetric Boolean functions proposed by Sarkar and Maitra is analyzed. These functions are on odd numbers of variables and have optimum algebraic immunity. A construction of a class of Boolean functions on even numbers of variables with1st-resilience and optimal algebraic immunity is presented through concatenating this class of Boolean functions. Also a general construction is proposed by modifying the values of pairs of orbits of majority Boolean functions on odd number of variables. The optimum algebraic immune Boolean functions with1st-resilience have greater value in applications.Thirdly, one concatenated construction proposed by Sun Gonghong et al is generalized. A new class of Boolean functions is constructed through adding t variables while congcatenating t+1functions which are called basic functions. General expressions are given which describe the Walsh spectrum and autocorrelation functions between this class of Boolean functions and its basic functions. On the basis of these theories, the correlation immunity and propagation of this class of Boolean functions are discussed in details. By investigation, it is easy to see that the cryptographic properties of this class of Boolean functions are good if the basic functions have good cryptographic properties. This class of Boolean functions can play an important role in constructing Boolean functions with special Walsh spectrum.