Constructions And Applications Of Nonlinear Components Of Block Ciphers

This dissertation is oriented to the strategic requirements of national and military cybersecurity,focuses on the independent innovation design theory and method of non-linear components of block ciphers,mainly aims at a series of difficult questions and conjectures,such as“the big APN problem”,“Carlet’s open problem”,“Hollmann-Xiang conjecture”,uses mathematical theories such as finite fields,algebraic curves,algebra-ic function fields,finite geometry,and some mathematical methods such as“commuta-tive graph”,“double-variable representations”,“polar decomposition”and“multivariate”,and systematically studies the constructions and applications of low differential functions,permutation polynomials and 2-to-1 mappings over finite fields with even characteristic,providing theoretical guidance for the design and analysis of symmetric cryptographic algorithm nonlinear components.The main work of this paper is summarized as follows.（1）In the research of APN functions:firstly,“the big APN problem”,one of the most important problems in the field of cryptographic functions,has been open for almost 30years.The generalized Kim function is a generalized form of one function which is CCZ equivalent to the currently unique APN permutation.Aiming at the important question of“whether a new APN permutation can be found from the generalized Kim function”,the algebraic curve theory is used to determine the APN properties of the generalized Kim function,partially solving an open problem raised by C.Carlet in 2014,promoting the study of“the big APN problem”.Next,it is very difficult to construct a new infinite class of APN functions.Based on fully studying the construction approaches of the existing APN functions,the methods of“adding special terms”and“based on linearized permu-tations”are proposed,and then two new infinite classes of APN functions are obtained,including an APN function example obtained by Y.Edel and A.Pott in 2009 using the“Switching method”.This result provides new ideas and methods for the constructions of APN functions.（2）In the study of the boomerang uniformity:aiming at“the computing complexity of the initial definition of the boomerang uniformity”,an equivalent definition for calcu-lating the boomerang uniformity is first proposed.Compared with the original definition,the new one has two advantages:it is not necessary to know the expression of the com-positional inverse;the concept can be extended to non-permutation situations.This new definition facilitates the in-depth exploration of the boomerang uniformity and is used in most of subsequent researches.Secondly,H.Niederreiter,an academician of the Austrian Academy of Sciences,pointed out that the conditions for polynomials to be permutations are often very complicated.In EUROCRYPT2018,C.Cid et al.emphasized that it is very difficult to construct a permutation with boomerang uniformity 4.Therefore,construct-ing permutations with a simple structure and boomerang uniformity 4 is a more difficult task.Combining the properties of Dickson polynomials,the theory of double-variable element representation,the theory of equations over finite fields,etc.,the boomerang uni-formity of the cryptographic functions generated by the cipher structure is studied,and the internal connection between the double-variable permutation corresponding to the butter-fly structure and the single-variable quadrinomial is established.A class of permutation binomials with boomerang uniformity 4 which is of simple form and a type of permu-tations with boomerang uniformity 4 which is convenient to implement are successfully constructed（up to now,there are only 7 classes）,providing theoretical guidance for effi-ciently generating nonlinear components of block ciphers.（3）In the research of permutation polynomials:permutations of Niho and Kloost-erman types have been the research hotspots in the past ten years and widely concerned by many domestic and international scholars.Although there are many research results on these two types of permutations,they have always been studied separately.Using the“AGW criterion”,“the polar decomposition”,the relation between the unit circle and the projective plane,etc.,an equivalent relationship between the permutations of Niho and Kloosterman types is given.A bridge between these two types of permutations is built and to some extent,these two types of permutation polynomials are unified.Secondly,aiming at a conjecture about Kloosterman polynomials proposed by H.Hollmann and Q.Xiang in 2004,using an equivalent relationship between the permutation polynomial of Niho types and Kloosterman polynomials,as well as the knowledge of algebraic function fields,the necessity of the existence of Kloosterman polynomials is described,and the asymptotic result of the Hollmann-Xiang conjecture is given,to some extent promoting the research of Kloosterman sums.Finally,in 2019,Z.Tu et al.proposed a sufficien-t condition for the permutation properties of the generalized Kim function.According to the experimental data,they conjectured that the sufficient condition is also necessary.For this conjecture,using the knowledge of algebraic curves,by characterizing the abso-lutely irreducibility of some quartic curve,the necessary conditions for the permutation properties of the generalized Kim function are given,which solves this conjecture.（4）In the research on 2-to-1 mappings:firstly,aiming at that there is no classification result about 2-to-1 polynomials with degree more than 4,using the algebraic curve theory,together with the theory of equations with low degrees over finite fields and the method of undetermined coefficients,the 2-to-1 properties of the polynomials of degree 5 over finite fields with even characteristic are completely described,enriching the classification results of 2-to-1 polynomials with low degrees.Secondly,considering that there are not many 2-to-1 polynomials with exact forms,combining equations and the resultant theory over finite fields,as well as the method of“multivariate”,two classes of 2-to-1 trinomials and more than ten types of 2-to-1 quadrinomials over finite fields with even characteristic are constructed,enriching the existing results.Finally,the applications of 2-to-1 map-pings in the construction of linear codes was systematically studied for the first time.By applying generalized quadratic 2-to-1 mappings and that of the form(x^2t+x)^eover F₂ninto the spectral construction method and definition set construction method of linear codes,a large number of linear codes with few nonzero weights are obtained,some of which have known optimal parameters.This result provides a new idea for the construction of linear codes.