Nonlinear Functions And Their Related Applications

Nonlinear functions are one of the most important topics in combinatorics. Func-tions with high nonlinearity have important applications in cryptography, sequences,coding theory and other research objects in combinatorics. In cryptography, functionswith high nonlinearity are necessary for achieving confusion. They can be used to con-struct keystream generators for stream ciphers, S-boxes for block ciphers. In codingtheory, functions with high nonlinearity can be used to construct good error correctingcodes. In sequences theory, the sequences with good autocorrelation or crosscorrelationproperties can be constructed via functions with high nonlinearity. In other researchobjects in combinatorics, functions with high nonlinearity can be used to constructnew skew Hadamard di?erence set, association schemes and so on.There are five chapters in this thesis. In the first Chapter, we introduce thebackground of the results here, and give necessary definitions and results.In chapter 2, we make an investigation into the nonlinearity of a function f : Aâ†'Bin the case |A| is not divisible by |B|, where |A| and |B| are finite, commutative inwhich the typical additive notation is used for their operations. The notion of a nearperfect nonlinear function is then proposed. By our definition, a near perfect nonlinearfunction is optimal in the sense of its nonlinearity. Both algebraic and combinatorialconstructions of near perfect nonlinear functions are developed. A few infinite familiesof near perfect nonlinear functions are thus obtained.In chapter 3, we generalize the construction of a?ne polar graphs in two di?erentways to obtain partial di?erence sets and amorphic association schemes. In the firstgeneralization we replace the quadratic form in the a?ne polar graph construction byhigher degree homogeneous functions that are p-ary weakly regular bent. The secondgeneralization uses a combination of quadratic forms and uniform cyclotomy. Thenegative Latin square type partial di?erence sets arising from the second generalization seem to be new.In chapter 4, a construction of optimal sets of frequency hopping sequences ispresented through near perfect nonlinear functions. The construction is based on thecorrespondence between sets of frequency hopping sequences and partition type cyclicdi?ernce packing family. In the final chapter, we present some open problems forfurther study.