Lower bounds on APN-distance for all known APN functions

From Boolean
Revision as of 19:47, 21 August 2019 by Nikolay (talk | contribs)
Jump to navigation Jump to search

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 [1]. Note that the lower bound is a CCZ-invariant (unlike the exact minimum distance itself) and it can be calculated via the formula [math]\displaystyle{ l(F) = \lceil \frac{m_F}{3} \rceil + 1 }[/math], where [math]\displaystyle{ l(F) }[/math] is the lower bound on the Hamming distance between an [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] and the closest APN function, and [math]\displaystyle{ m_F }[/math] is defined as [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]. The values of [math]\displaystyle{ 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 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]\displaystyle{ x^3 }[/math] over [math]\displaystyle{ \mathbb{F}_{2^7} }[/math] as given in the table below.

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. Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.