Construction And Enumeration Of MAI Functions And Resilient Functions

Boolean functions and S-boxes are important components of block ciphers, streamciphers and Hash functions. The cryptographic criteria of Boolean functions or S-boxes iscrucialtothesecurityofcryptographicalgorithms. Theimmunityofacryptographicalgo-rithm to the known cryptographic analysis can be evaluated by the cryptographic criteriaof Boolean functions or S-boxes used in the algorithm. The study of the cryptographiccriteria of Boolean functions is important in the design and analysis of cryptographic al-gorithms.Some topics of Boolean functions are studied in this thesis, including constructionsand the counts of Boolean functions with maximum algebraic immunity (MAI), construc-tions of the rotation symmetric Boolean functions with MAI, constructions of degree opti-mized resilient function, constructions of highly nonlinear resilient S-Boxes, enumerationof rotation symmetric Boolean functions, enumeration of rotation symmetric functionsand symmetric functions over finite fields etc. Main contributions of this thesis are asfollows:(1)Two new methods of constructing Boolean functions with MAI are presented.The first one is a recursive construction of odd-variable Boolean function with MAI. Inthe second construction, we can obtain Boolean function with MAI by partitioning theinput vectors into special intervals.(2) We improve the enumeration results of even-variable Boolean functions withMAI. The even-variable Boolean functions with MAI are divided into 3 classes. By usingthe "basis interchange" method, we can obtain the lower bound of the first class and thesecond class. And we give a construction which provides a large number of Boolean func-tions with MAI belonging to the third class. As a result, the lower bound on the numberof even-variable Boolean functions with MAI as well as the lower bound on the numberof balanced even-variable Boolean functions with MAI is improved.(3) Construction of n-variable (n is even)rotation symmetric Boolean functions withMAI are studied. Based on n-variable majority function, we obtain two groups of orbitssuch that the support of one group are included in another group. Then its outputs aretoggledatthesetwogroupsoforbits. Asaresult,wecanconstructhighlynonlinearRSBFs with MAI.(4)Whenthenumberofvariablesnisequalto2m or2p, wecanprovethatthevectorswith weight n/2 satisfy some special properties and then we can use these properties toconstruct balanced RSBFs with MAI. This is the first time to obtain balanced RSBFs withMAI.(5) By generalizing the Maiorana MacFarland construction, we provide a construc-tion of n-variable (n odd) degree-optimized resilient Boolean functions, and it is shownthat the resultant functions achieve the currently best known nonlinearity.(6) By using linear codes together with highly nonlinear S-Boxes, we improve thenonlinearity of the previous constructions of S-Boxes. Then a construction of highly non-linear resilient S-boxes with given degree is provided, the construction provides the bestknown nonlinearity. We also provide a method to construct highly nonlinear S-Boxeswhich do not have linear structure.(7) We present an accurate enumeration formula for n-variable balanced RSBFsand n-variable 1st order correlation-immune RSBFs. As a result, we obtain the accu-rate number of 11-variable 1st order correlation-immune RSBFs and 13-variable 1st ordercorrelation-immune RSBFs.(8) A formula to count homogeneous rotation symmetric functions with degree≥3is given at first . Then we improve the results on the number of balanced rotation sym-metric functions over Fp. Furthermore, we proved that the construction and enumerationof balanced symmetric functions over Fp are equivalent to solving an equation system andenumerating the solutions.