Lower bounds on APN-distance for all known APN functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 1: Line 1:
The following tables list a lower bound on the Hamming distance between all known CCZ-inequivalent APN representatives up to dimension 11 using the methods described used in <ref name="kpoints">Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.</ref>. Note that the lower bound is a CCZ-invariant (unlike the exact minimum distance itself) and it can be calculated via the formula <math>l(F) = \lceil \frac{m_F}{3} \rceil + 1</math>, where <math>l(F)</math> is the lower bound on the Hamming distance between an <math>(n,n)</math>-function <math>F</math> and the closest APN function, and <math>m_F</math> is defined as <math>m_F = \min_{b, \beta \in \mathbb{F}_{2^n}} | \{ a \in \mathbb{F}_{2^n} : (\exists x \in \mathbb{F}_{2^n})( F(x) + F(a+x) + F(a + \beta) = b ) \} |</math>. The values of <math>m_F</math> for the CCZ-inequivalent representatives are provided in the tables for convenience. The representatives for dimensions 7 and 8 are taken from the list of [[Known quadratic APN polynomial functions over GF(2^7)]] and [[Known quadratic APN polynomial functions over GF(2^8)]], respectively, while the rest are taken from the table of [[CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11)]].
The following table lists a lower bound on the Hamming distance between a representative from each known CCZ-equivalence class of APN functions up to dimension 11, and the closes APN function (in terms of Hamming distance). The lower bound <math>l(F)</math> between an (n,n)-function F and the closest APN function is a CCZ-invariant, and is calculated via the formula <math>l(F) = \lceil \frac{m_F}{3} \rceil + 1</math>, where <math>m_F = \min_{b, \beta \in \mathbb{F}_{2^n}} | \{ a \in \mathbb{F}_{2^n} : (\exists x \in \mathbb{F}_{2^n})( F(x) + F(a+x) + F(a + \beta) = b ) \} |</math><ref>L. Budaghyan, C. Carlet, T. Helleseth, N. Kaleyski. On the distance between APN functions. IEEE Trans. Inf. Theory, early access article. https://doi.org/10.1109/TIT.2020.2983684</ref>. The representatives for dimensions 7 and 8 are taken from the list of [[known quadratic APN polynomial functions over GF(2^7)]] and [[Known quadratic APN polynomial functions over GF(2^8)]], respectively, while the rest are taken from the table of [[CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11)]].


The table below shows the lower bounds computed for some of the known APN functions for dimensions between 4 and 11. The functions in dimensions between 5 and 8 are indexed according to the table of [[Known switching classes of APN functions over GF(2^n) for n = 5,6,7,8]]. The ones between 9 and 11 are index according to the table of [[CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11)]]. A separate table listing these results for the (more than 8000) known APN functions in dimension 8 is available as [[Lower bounds on APN-distance for all known APN functions in dimension 8]]. Note that all known APN functions in dimension 7 from [[Known quadratic APN polynomial functions over GF(2^7)]] have the same value of the lower bound as e.g. <math>x^3</math> over <math>\mathbb{F}_{2^7}</math> as given in the table below.
The table below shows the lower bounds computed for some of the known APN functions for dimensions between 4 and 11. The functions in dimensions between 5 and 8 are indexed according to the table of [[known switching classes of APN functions over GF(2^n) for n = 5,6,7,8]]. The ones between 9 and 11 are indexed according to the table of [[CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11)]]. A separate table listing these results for the (more than 8000) known APN functions in dimension 8 is available under [[Lower bounds on APN-distance for all known APN functions in dimension 8]]. Note that all known APN functions in dimension 7 from the [[known quadratic APN polynomial functions over GF(2^7)]] have the same value of the lower bound as e.g. <math>x^3</math> over <math>\mathbb{F}_{2^7}</math>.


<table>
<table>

Latest revision as of 18:55, 10 July 2020

The following table lists a lower bound on the Hamming distance between a representative from each known CCZ-equivalence class of APN functions up to dimension 11, and the closes APN function (in terms of Hamming distance). The lower bound [math]\displaystyle{ l(F) }[/math] between an (n,n)-function F and the closest APN function is a CCZ-invariant, and is calculated via the formula [math]\displaystyle{ l(F) = \lceil \frac{m_F}{3} \rceil + 1 }[/math], where [math]\displaystyle{ m_F = \min_{b, \beta \in \mathbb{F}_{2^n}} | \{ a \in \mathbb{F}_{2^n} : (\exists x \in \mathbb{F}_{2^n})( F(x) + F(a+x) + F(a + \beta) = b ) \} | }[/math][1]. The representatives for dimensions 7 and 8 are taken from the list of known quadratic APN polynomial functions over GF(2^7) and Known quadratic APN polynomial functions over GF(2^8), respectively, while the rest are taken from the table of CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11).

The table below shows the lower bounds computed for some of the known APN functions for dimensions between 4 and 11. The functions in dimensions between 5 and 8 are indexed according to the table of known switching classes of APN functions over GF(2^n) for n = 5,6,7,8. The ones between 9 and 11 are indexed according to the table of CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11). A separate table listing these results for the (more than 8000) known APN functions in dimension 8 is available under Lower bounds on APN-distance for all known APN functions in dimension 8. Note that all known APN functions in dimension 7 from the known quadratic APN polynomial functions over GF(2^7) have the same value of the lower bound as e.g. [math]\displaystyle{ x^3 }[/math] over [math]\displaystyle{ \mathbb{F}_{2^7} }[/math].

Dimension F [math]\displaystyle{ m_F }[/math] Lower bound
4 x3 3 2
5 x3 15 6
5 x5 15 6
5 x15 9 4
6 1.1 27 10
6 1.2 27 10
6 2.1 15 6
6 2.2 27 10
6 2.3 27 10
6 2.4 15 6
6 2.5 15 6
6 2.6 15 6
6 2.7 15 6
6 2.8 15 6
6 2.9 21 8
6 2.10 21 8
6 2.11 15 6
6 2.12 15 6
7 7.1 54 19
7 all others 63 22
8 1.1 - 1.13 111 38
8 1.14 99 34
8 1.15 - 1.17 111 38
8 2.1 111 38
8 3.1 111 38
8 4.1 99 34
8 5.1 105 36
8 6.1 105 36
8 7.1 111 38
9 9.7 231 78
9 all others 255 86
10 10.4 477 160
10 all others 495 166
11 11.12 978 327
11 all others 1023 342
  1. L. Budaghyan, C. Carlet, T. Helleseth, N. Kaleyski. On the distance between APN functions. IEEE Trans. Inf. Theory, early access article. https://doi.org/10.1109/TIT.2020.2983684