Almost Perfect Nonlinear (APN) Functions

From Boolean Functions
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 𝐹 : 𝔽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 π‘₯.


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.

  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