Codes, graphs, and schemes from nonlinear functions (Q1869033)

The main object of the paper are functions which in some sense are far from being linear, in particular the hierarchy CR (crooked functions) -- AB (almost bent functions) -- APN (almost perfect nonlinear functions) defined on binary vector spaces (CR implies AB, which implies APN). These functions have applications in cryptography because of their resistance to certain types of attacks. They can be described combinatorially, algebraically (in terms of the number of solutions of certain equations) and in terms of the Fourier coefficients. These characterizations are reviewed or proved in the present paper. A gap remains: no combinatorial characterization of AB functions is known. In the final section the known functions belonging to these families are described. They all map \(x\) to \(x^t\) for a suitable exponent \(t.\) The names attached to these functions are Gold, Kasami, Welch, Niho, Dobbertin. In the bulk of the paper it is described how other combinatorial objects can be constructed from functions of those families. This includes semi-biplanes, linear codes with minimum distance \(5,\) distance-regular graphs, nonlinear codes with the same parameters as the Preparata codes, Hadamard difference sets and certain association schemes.