Research On Nonlinear Functions Based On Shift Registers

Nonlinear cryptographic functions(nonlinear functions for short)include nonlinear Boolean functions and nonlinear multi-output Boolean functions.Many problems in symmetric cryptography can be transformed into the constructions of nonlinear cryp-tographic functions with good cryptographic properties such as high algebraic degree,high nonlinearity,permutation property and so on.Constructions and research methods of complete permutation polynomials not only play an important role in cryptographic design,but also have an important influence on many branches of mathematics such as number theory and group theory.Therefore,the constructions of nonlinear cryptograph-ic functions,especially complete permutation polynomials,have important theoretical and practical significance.Because shift register systems are closely related to nonlin-ear functions,starting from shift register systems,this paper studies the constructions of nonsingular polynomials and complete permutation polynomials with cryptograph-ic application background by applying the tools of algebra,finite fields,combinatorial designs,etc.The main results are as follows:(1)So far,the cycle structure of nonlinear feedback shift register is mainly studied by combinatorial method.Due to the limitation of vector space,the research results on cycle structure of nonlinear feedback shift register are very few.In order to find new tools to study the cycle structure,we give the univariate expression of permutation polynomials,which are corresponding to the state transition functions of the Fibonacci type of nonsingular feedback shift registers.The definition of nonsingular polynomials is given,which is related to the linear structure of corresponding Boolean function-s.Algebraic degree and nonlinearity of nonsingular polynomials on certain forms are studied.The upper bound on the nonlinearity of nonsingular Boolean functions is in-vestigated.Some nonsingular quadratic Boolean functions with high nonlinearity(the nonlinearity is optimal)are constructed.For odd n,we use quadratic Boolean function-s to construct n-variable nonsingular Boolean functions with optimal algebraic degree and the highest possible nonlinearity.(2)Complete permutation polynomials are rare objects and there are a limited number of known constructions.In order to find a new method to construct complete permutation polynomials,the recurrence relations of the classical Feistel and MISTY structures in shift register systems will be used to construct complete permutation poly-nomials.By combining Feistel and MISTY structures in two and three rounds,many new constructions of complete permutation polynomials over the finite field F22n for a positive integer n are presented from permutation polynomials over F2n.Furthermore,three constructions of complete permutation polynomials over Fpnm for any prime p and positive integer m? 2 are presented.In addition,the upper bounds on the algebraic degree of these complete permutation polynomials are investigated and some examples are given to show that some of these complete permutation polynomials can have nearly optimal algebraic degree.It is hopeful to find excellent S box candidate functions that can effectively resist algebraic and cubic attacks in our constructions.(3)Because the state transition functions of the Galois type of nonsingular feed-back shift registers and permutation polynomials in finite fields are corresponding one by one,in order to use knowledge in finite fields to study the Galois type of feedback shift registers,by the AGW criterion and determining the number of solutions of some equations,we propose several classes of complete permutation polynomials with the form(xpm-x+?)s+axpm+bx over Fpn,which comes from Kloosterman sum i-dentities.Our results also enrich constructions of known permutation polynomials and complete permutation polynomials.