Near perfect nonlinear functions

Abstract

Functions with high nonlinearity have been an instrumental tool not only in algebra and finite geometries but also in combinatorics,coding theory and cryptography as well. In recent years,the study of perfect nonlinear functions(PNFs) and their variants have been very hot. Specially,functions over finite fields have been extensively investigated. It is known that a PNF f from an Abelian group(A,+) of order n to another one(B,+) of order m can exist only if m | n. This paper makes an investigation into the nonlinearity of a function f: A → B in the case |A| is not divisible by |B|. The notion of a near perfect nonlinear function(NPNF) is then proposed. By our definition,an NPNF is optimal in the sense of its nonlinearity,which can be viewed as an extension of a PNF. A number of constructions of NPNFs are developed in this paper. A few infinite families of NPNFs are thus obtained.