# Difference between revisions of "Almost Perfect Nonlinear (APN) Functions"

Line 55: | Line 55: | ||

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

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Revision as of 19:58, 7 February 2019

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

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

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