APN Permutations: Difference between revisions
NikiSpithaki (talk | contribs) No edit summary |
NikiSpithaki (talk | contribs) |
||
| Line 54: | Line 54: | ||
Specifically: | Specifically: | ||
If a power function <math>F(x)=x^d</math> over <math>\mathbb{F}_{2^n}</math> is APN, then for every <math>x\in \mathbb{F}_{2^n}</math> we have <math>x^d=1</math> if and only if <math>x^3=1</math>, that is, <math>F^{-1}(1)=\mathbb{F}_4\cap\mathbb{F}_{2^n}^*.</math> If <math>n</math> is odd, then <math>gcd(d,2^n-1)=1</math> and, if <math>n</math> is even, then <math>gcd(d,2^n-1)=3</math>. Consequently, APN power functions are permutations if <math>n</math> is odd, and are three-to-one over <math>\mathbb{F}_{2^n}^*</math> if <math>n</math> is even.<ref name="Dobbertin"> H. Dobbertin. Private Communication, 1998.</ref> | If a power function <math>F(x)=x^d</math> over <math>\mathbb{F}_{2^n}</math> is APN, then for every <math>x\in \mathbb{F}_{2^n}</math> we have <math>x^d=1</math> if and only if <math>x^3=1</math>, that is, <math>F^{-1}(1)=\mathbb{F}_4\cap\mathbb{F}_{2^n}^*.</math> | ||
If <math>n</math> is odd, then <math>gcd(d,2^n-1)=1</math> and, if <math>n</math> is even, then <math>gcd(d,2^n-1)=3</math>. | |||
Consequently, APN power functions are permutations if <math>n</math> is odd, and are three-to-one over <math>\mathbb{F}_{2^n}^*</math> if <math>n</math> is even.<ref name="Dobbertin"> H. Dobbertin. Private Communication, 1998.</ref> | |||
Revision as of 10:21, 4 October 2024
Characterization of Permutations
Component Functions
An (𝑛,𝑛)-function 𝐹 is a permutation if and only if all of its components 𝐹λ for λ ∈ 𝔽*2𝑛 are balanced.
Autocorrelation Functions of the Directional Derivatives
The characterization in terms of the component functions given above can be equivalently expressed as
for any λ ∈ 𝔽*2𝑛.
Equivalently [1], 𝐹 is a permutation if and only if
for any λ ∈ 𝔽*2𝑛.
Characterization of APN Permutations
[2] Up to CCZ-equivalence, all of the APN permutations known so far belong to a few families, namely:
1. APN monomial functions in odd dimension.
2. One infinite family of quadratic polynomials in dimension [math]\displaystyle{ 3n }[/math], with [math]\displaystyle{ n }[/math] odd and [math]\displaystyle{ gcd(n,3)=1 }[/math].[3]
3. Dillon's permutation in dimension 6.[4]
4. Two sporadic quadratic APN permutations in dimension 9.[5]
On the component functions
Clearly we have that no component function can be of degree 1. (This result is true for general APN maps)
For 𝑛 even we have also that no component can be partially-bent[6]. This implies that, in even dimension, no component can be of degree 2.
Autocorrelation Functions of the Directional Derivatives
An (𝑛,𝑛)-function 𝐹 is an APN permutation if and only if [1]
and
for any 𝑎 ∈ 𝔽*2𝑛.
On APN Power Functions
For [math]\displaystyle{ n }[/math] odd, all power APN functions and the known APN binomials are permutations. When [math]\displaystyle{ n }[/math] is even, no APN function exists in a class of permutations including power permutations.
Specifically:
If a power function [math]\displaystyle{ F(x)=x^d }[/math] over [math]\displaystyle{ \mathbb{F}_{2^n} }[/math] is APN, then for every [math]\displaystyle{ x\in \mathbb{F}_{2^n} }[/math] we have [math]\displaystyle{ x^d=1 }[/math] if and only if [math]\displaystyle{ x^3=1 }[/math], that is, [math]\displaystyle{ F^{-1}(1)=\mathbb{F}_4\cap\mathbb{F}_{2^n}^*. }[/math]
If [math]\displaystyle{ n }[/math] is odd, then [math]\displaystyle{ gcd(d,2^n-1)=1 }[/math] and, if [math]\displaystyle{ n }[/math] is even, then [math]\displaystyle{ gcd(d,2^n-1)=3 }[/math].
Consequently, APN power functions are permutations if [math]\displaystyle{ n }[/math] is odd, and are three-to-one over [math]\displaystyle{ \mathbb{F}_{2^n}^* }[/math] if [math]\displaystyle{ n }[/math] is even.[7]
- ↑ 1.0 1.1 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
- ↑ Bartoli, D., Timpanella, M. On a conjecture on APN permutations. Cryptogr. Commun. 14, 925–931 (2022)
- ↑ Budaghyan, L., Carlet, C., Leander, G.: Two classes of quadratic APN binomials inequivalent to power functions. IEEE Trans. Inf. Theory 54(9), 4218–4229 (2008)
- ↑ Browning, K., Dillon, J.F., McQuistan, M., Wolfe, A.J.: An APN permutation in dimension six. In: Post-proceedings of the 9-th International conference on finite fields and their applications, american mathematical society, vol. 518, pp. 33–42 (2010)
- ↑ Beierle, C., Leander, G.: New instances of quadratic APN functions, arXiv:2009.07204 (2020)
- ↑ Marco Calderini, Massimiliano Sala, Irene Villa, A note on APN permutations in even dimension, Finite Fields and Their Applications, vol. 46, 1-16, 2017
- ↑ H. Dobbertin. Private Communication, 1998.