Properties And Applications Of Preimage Distributions Of Perfect Nonlinear Functions Over Finite Fields

Nonlinear functions are widely used in cryptography, coding theory, sequences and Hash func-tions. In order to resist again the differential cryptanalysis and the linear cryptanalysis, the nonlinearfunctions are often used as the filter functions in stream cipher, the S-Boxes in block cipher and thebuilding blocks in Hash functions. In coding theory, they are used to construct good error correctingcodes.As a special type of highly nonlinear functions, perfect nonlinear functions have attracted muchattention. The main points are focus on the construction of new perfect nonlinear functions, the equiv-alence classification and the application of perfect nonlinear functions in coding theory and cryptog-raphy. In order to construct new perfect nonlinear functions, investigating the preimage distributionsof perfect nonlinear functions is very important.In this thesis, we investigate the properties of the preimage distributions of perfect nonlinearfunctions. With the method of elementary number theory, algebraic number theory and theory ofquadratic forms over finite fields, we study the preimage distributions of perfect nonlinear functionsfrom Abelian group of order n to another Abelian group of order m while m = 3, 4. We also discussthe preimage distributions of perfect nonlinear functions tr(aΠ(x)), whileΠ(x) are the known per-fect nonlinear functions over finite fields Fqm. According to the preimage distributions, the weightdistributions of a class of linear codes based on three known perfect nonlinear functions are obtained,which answered the open problem about the weight distributions of linear codes which is presentedby C.Carlet and C.Ding in 2005. A new construction of constant-composition codes based on threeknown perfect nonlinear functions is also presented. The main contents and fruits of this thesis areoutlined as follows:(1)Using the method of algebraic number theory, a necessary condition about the existence ofperfect nonlinear functions is presented firstly. In addition, we study the value of n that when mequals 3,4,5, there does not exist perfect functions from abelian group A of order n to abelian groupB of order m. We also present the preimage distributions of perfect nonlinear functions tr(aΠ(x)),whereΠ(x) is any perfect nonlinear functions over finite field Fpm and p is a prime.(2)Using the method of elementary number theory, we obtained the preimage distributions ofperfect functions over abelian group of order m. When m = 3, solve the equations of the preimagedistributions equals the representation of a positive integer in the binary quadratic form. And while m = 4, solve the equations of the preimage distributions equals solve the equation 4l2 = a2 + b2.(3)Under the theory of quadratic forms over finite fields, the preimage distributions of perfectnonlinear function tr(aΠ(x)) is presented, whereΠ(x) are the three known perfect nonlinear func-tions from Fqm to itself. Using a unified approach, a new construction of constant-composition codesbased on the three known perfect functions from Fqm to itself is presented. It is proved that the newconstant-composition codes are optimal with respect to the Luo-Fu-Vinck-Chen bound, when m isan odd positive integer greater than 1. We point out that the constant-composition codes presented byC.Ding in 2006 are equivalent to two special codes in our construction.(4)Under the conclusion of (2), the weight distributions of the ternary linear codes based on thethree known perfect nonlinear over finite fields are obtained. This lead to the solution of the openproblem about the weight distributions of linear codes from perfect nonlinear functions.