Lower bounds on APN-distance for all known APN functions

From Boolean
Revision as of 18:55, 10 July 2020 by Nikolay (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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