Almost Perfect Nonlinear (APN) Functions
Background and definition
Almost perfect nonlinear (APN) functions are the class of Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function is efficient when fixing some difference and computing the output of for all pairs of inputs whose difference is produces output pairs with a difference distribution that is far away from uniform.
The formal definition of an APN function is usually given through the values
which, for , express the number of input pairs with difference that map to a given . The existence of a pair with a high value of makes the function vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as
which clearly satisfies for any function . The functions meeting this lower bound are called almost perfect nonlinear (APN).