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

m |
|||

(6 intermediate revisions by one other user not shown) | |||

Line 1: | Line 1: | ||

= Background and definition = | = Background and definition = | ||

β | Almost perfect nonlinear (APN) functions are the class of | + | 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 < | + | The formal definition of an APN function πΉ : π½<sub>2<sup>π</sup></sub> β π½<sub>2<sup>π</sup></sub> is usually given through the values |

<div><math>\Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|</math></div> | <div><math>\Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|</math></div> | ||

β | which, for | + | which, for πβ 0, express the number of input pairs with difference π that map to a given π. The existence of a pair <math>(a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}</math> with a high value of Ξ<sub>πΉ(π,π)</sub> makes the function πΉ vulnerable to differential cryptanalysis. This motivates the definition of ''differential uniformity'' as |

<div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div> | <div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div> | ||

β | which clearly satisfies < | + | which clearly satisfies Ξ<sub>πΉ</sub> β₯ 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 <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on π₯, or, equivalently, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}</math> does not depend on π₯. | ||

= Characterizations = | = Characterizations = | ||

β | == Autocorrelation functions of the directional derivatives == | + | == Walsh transform<ref name="chavau1994">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</ref> == |

+ | |||

+ | Any (π,π)-function πΉ satisfies | ||

+ | |||

+ | <div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n})</math></div> | ||

+ | |||

+ | with equality characterizing APN functions. | ||

+ | |||

+ | In particular, for (π,π)-functions we have | ||

+ | |||

+ | <div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)</math></div> | ||

+ | |||

+ | with equality characterizing APN functions. | ||

+ | |||

+ | Sometimes, it is more convenient to sum through all π β π½<sub>2<sup>π</sup></sub> instead of just the nonzero ones. In this case, the inequality for (π,π)-functions becomes | ||

+ | |||

+ | <div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)</math></div> | ||

+ | |||

+ | and the particular case for (π,π)-functions becomes | ||

+ | |||

+ | <div><math>\sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)</math></div> | ||

+ | |||

+ | with equality characterizing APN functions in both cases. | ||

+ | |||

+ | == Autocorrelation functions of the directional derivatives <ref name="bercanchalai2006"> 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</ref> == | ||

β | Given a Boolean function < | + | Given a Boolean function π : π½<sub>2<sup>π</sup></sub> β π½<sub>2</sub>, the ''autocorrelation function'' of π is defined as |

<div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div> | <div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div> | ||

β | Any | + | Any (π,π)-function πΉ satisfies |

<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div> | <div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div> | ||

β | for any <math>a \in \mathbb{F}_{2^n}^ | + | for any π β π½*<sub>2<sup>π</sup></sub> . Equality occurs if and only if <math>F</math> is APN. |

+ | |||

+ | This allows APN functions to be characterized in terms of the ''sum-of-square-indicator'' <math>\nu(f)</math> defined as | ||

+ | <div><math>\nu(f) = \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^2(D_aF) = 2^{-n} \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^4(f + \varphi_a)</math></div> | ||

+ | for <math>\varphi_a(x) = {\rm Tr}(ax)</math>. | ||

+ | |||

+ | Then any (π,π) function πΉ satisfies | ||

+ | <div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}</math></div> | ||

+ | and equality occurs if and only if πΉ is APN. | ||

+ | |||

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

## Latest revision as of 13:54, 11 October 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 πΉ : π½_{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