Almost Perfect Nonlinear (APN) Functions: Difference between revisions
No edit summary |
No edit summary |
||
Line 53: | Line 53: | ||
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. | ||
= Characterization of Plateaued Functions = | |||
== Characterization by the Derivatives <ref name="carletPlateaued">Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.</ref> == | |||
=== First characterization === | |||
Using the fact that two integer-valued functions over <math>\mathbb{F}_2^m</math> are equal precisely when their Fourier transforms are equal, one can obtain the following characterization. | |||
Let <math>F</math> be an <math>(n,m)</math>-function. Then: | |||
- <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set | |||
<div><math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math></div> | |||
does not depend on <math>x</math>; | |||
- <math>F</math> is plateaued with single amplitude if and only if the size of the above set depends neither on <math>x</math> nor on <math>v</math> when <math>v \ne 0</math>. | |||
Moreover: | |||
- for any <math>(n,m)</math>-function <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals the value distribution of <math>D_aF(b) + D_aF(x)</math> as <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>; | |||
- if two plateuaed functions have the same distribution, then for every <math>u</math>, their component functions at <math>u</math> have the same amplitude. | |||
=== Characterization in the Case of Unbalanced Components === | |||
Let <math>F</math> be an <math>(n,m)</math>-function. Then <math>F</math> is plateuaed with all components unbalanced if and only if, for every <math>v,x \in \mathbb{F}_2^n</math>, we have | |||
<div><math> | \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} | = | \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \} |.</math></div> | |||
Moreover, <math>F</math> is plateuaed with single amplitude if and only if, in addition, this value does not depend on <math>v</math> for <math>v \ne 0</math>. |
Revision as of 13:21, 7 February 2019
Background and definition
Almost perfect nonlinear (APN) functions are the class of [math]\displaystyle{ (n,n) }[/math] Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function [math]\displaystyle{ F }[/math] is efficient when fixing some difference [math]\displaystyle{ \delta }[/math] and computing the output of [math]\displaystyle{ F }[/math] for all pairs of inputs [math]\displaystyle{ (x_1,x_2) }[/math] whose difference is [math]\displaystyle{ \delta }[/math] produces output pairs with a difference distribution that is far away from uniform.
The formal definition of an APN function [math]\displaystyle{ F : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} }[/math] is usually given through the values
which, for [math]\displaystyle{ a \ne 0 }[/math], express the number of input pairs with difference [math]\displaystyle{ a }[/math] that map to a given [math]\displaystyle{ b }[/math]. The existence of a pair [math]\displaystyle{ (a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n} }[/math] with a high value of [math]\displaystyle{ \Delta_F(a,b) }[/math] makes the function [math]\displaystyle{ F }[/math] vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as
which clearly satisfies [math]\displaystyle{ \Delta_F \ge 2 }[/math] for any function [math]\displaystyle{ F }[/math]. The functions meeting this lower bound are called almost perfect nonlinear (APN).
Characterizations
Walsh transform[1]
Any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] satisfies
with equality characterizing APN functions.
In particular, for [math]\displaystyle{ (n,n) }[/math]-functions we have
with equality characterizing APN functions.
Sometimes, it is more convenient to sum through all [math]\displaystyle{ b \in \mathbb{F}_{2^m} }[/math] instead of just the nonzero ones. In this case, the inequality for [math]\displaystyle{ (n,m) }[/math]-functions becomes
and the particular case for [math]\displaystyle{ (n,n) }[/math]-functions becomes
with equality characterizing APN functions in both cases.
Autocorrelation functions of the directional derivatives [2]
Given a Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math], the autocorrelation function of [math]\displaystyle{ f }[/math] is defined as
Any [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] satisfies
for any [math]\displaystyle{ a \in \mathbb{F}_{2^n}^* }[/math]. Equality occurs if and only if [math]\displaystyle{ F }[/math] is APN.
This allows APN functions to be characterized in terms of the sum-of-square-indicator [math]\displaystyle{ \nu(f) }[/math] defined as
for [math]\displaystyle{ \varphi_a(x) = {\rm Tr}(ax) }[/math].
Then any [math]\displaystyle{ (n,n) }[/math] function [math]\displaystyle{ F }[/math] satisfies
and equality occurs if and only if [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ \mathbb{F}_2^m }[/math] are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.
Let [math]\displaystyle{ F }[/math] be an [math]\displaystyle{ (n,m) }[/math]-function. Then:
- [math]\displaystyle{ F }[/math] is plateaued if and only if, for every [math]\displaystyle{ v \in \mathbb{F}_2^m }[/math], the size of the set
does not depend on [math]\displaystyle{ x }[/math];
- [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if the size of the above set depends neither on [math]\displaystyle{ x }[/math] nor on [math]\displaystyle{ v }[/math] when [math]\displaystyle{ v \ne 0 }[/math].
Moreover:
- for any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math], the value distribution of [math]\displaystyle{ D_aD_bF(x) }[/math] equals the value distribution of [math]\displaystyle{ D_aF(b) + D_aF(x) }[/math] as [math]\displaystyle{ (a,b) }[/math] ranges over [math]\displaystyle{ (\mathbb{F}_2^n)^2 }[/math];
- if two plateuaed functions have the same distribution, then for every [math]\displaystyle{ u }[/math], their component functions at [math]\displaystyle{ u }[/math] have the same amplitude.
Characterization in the Case of Unbalanced Components
Let [math]\displaystyle{ F }[/math] be an [math]\displaystyle{ (n,m) }[/math]-function. Then [math]\displaystyle{ F }[/math] is plateuaed with all components unbalanced if and only if, for every [math]\displaystyle{ v,x \in \mathbb{F}_2^n }[/math], we have
Moreover, [math]\displaystyle{ F }[/math] is plateuaed with single amplitude if and only if, in addition, this value does not depend on [math]\displaystyle{ v }[/math] for [math]\displaystyle{ v \ne 0 }[/math].
- ↑ 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
- ↑ Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.