Almost Perfect Nonlinear (APN) Functions

From Boolean Functions
Revision as of 14:21, 7 February 2019 by Nikolay (talk | contribs)
Jump to: navigation, search

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).

Characterizations

Walsh transform[1]

Any -function satisfies

with equality characterizing APN functions.

In particular, for -functions we have

with equality characterizing APN functions.

Sometimes, it is more convenient to sum through all instead of just the nonzero ones. In this case, the inequality for -functions becomes

and the particular case for -functions becomes

with equality characterizing APN functions in both cases.

Autocorrelation functions of the directional derivatives [2]

Given a Boolean function , the autocorrelation function of is defined as

Any -function satisfies

for any . Equality occurs if and only if is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator defined as

for .

Then any function satisfies

and equality occurs if and only if is APN.

Similar techniques can be used to characterize permutations and APN functions with plateaued components.

Characterization of Plateaued Functions

Characterization by the Derivatives [3]

First characterization

Using the fact that two integer-valued functions over are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.

Let be an -function. Then:

- is plateaued if and only if, for every , the size of the set

does not depend on ;

- is plateaued with single amplitude if and only if the size of the above set depends neither on nor on when .

Moreover:

- for any -function , the value distribution of equals the value distribution of as ranges over ;

- if two plateuaed functions have the same distribution, then for every , their component functions at have the same amplitude.

Characterization in the Case of Unbalanced Components

Let be an -function. Then is plateuaed with all components unbalanced if and only if, for every , we have

Moreover, is plateuaed with single amplitude if and only if, in addition, this value does not depend on for .

  1. Florent Chabaud, Serge Vaudenay, Links between differential and linear cryptanalysis, Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg
  2. Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, On Almost Perfect Nonlinear Functions Over GF(2^n), IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70
  3. Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.