# Almost Perfect Nonlinear (APN) Functions

## Contents

# 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 πΉ : π½_{2π} β π½_{2π} is usually given through the values

which, for πβ 0, 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 Ξ_{πΉ} β₯ 2 for any function πΉ. The functions meeting this lower bound are called *almost perfect nonlinear (APN)*.

The characterization by means of the derivatives below suggests the following definition: a v.B.f. πΉ is said to be *strongly-plateuaed* if, for every π and every π£, the size of the set does not depend on π₯, or, equivalently, the size of the set does not depend on π₯.

# 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 π β π½_{2π} 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 π : π½_{2π} β π½_{2}, the *autocorrelation function* of π is defined as

Any (π,π)-function πΉ satisfies

for any π β π½*_{2π} . 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.

- β 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 - β 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