APN Permutations: Difference between revisions
mNo edit summary |
NikiSpithaki (talk | contribs) No edit summary |
||
| Line 20: | Line 20: | ||
= Characterization of APN Permutations = | = Characterization of APN Permutations = | ||
<ref name="BT"> Bartoli, D., Timpanella, M. On a conjecture on APN permutations. Cryptogr. Commun. 14, 925–931 (2022)</ref> 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>3n</math>, with <math>n</math> odd and <math>gcd(n,3)=1</math>.<ref name="BCL"> 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)</ref> | |||
3. Dillon's permutation in dimension 6.<ref name="Dillon">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)</ref> | |||
4. Two sporadic quadratic APN permutations in dimension 9.<ref name="BL">Beierle, C., Leander, G.: New instances of quadratic APN functions, arXiv:2009.07204 (2020)</ref> | |||
==On the component functions== | ==On the component functions== | ||
Clearly we have that no component function can be of degree 1. (This result is true for general APN maps) | Clearly we have that no component function can be of degree 1. (This result is true for general APN maps) | ||
| Line 34: | Line 47: | ||
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}^2(D_af_\lambda) = 2^{2n}</math></div> | <div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}^2(D_af_\lambda) = 2^{2n}</math></div> | ||
for any 𝑎 ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>. | for any 𝑎 ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>. | ||
==On APN Power Functions== | |||
For <math>n</math> odd, all power APN functions and the known APN binomials are permutations. When <math>n</math> is even, no APN function exists in a class of permutations including power permutations. | |||
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> | |||
Revision as of 10:20, 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.