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

From Boolean
Jump to navigation Jump to search
(Created page with "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 <...")
 
No edit summary
Line 2: Line 2:


The tables for dimensions 7 and 8 can be found under [[Lower bounds on APN-distance for all known APN functions in dimension 7]] and [[Lower bounds on APN-distance for all known APN functions in dimension 8]], respectively, due to their large size.
The tables for dimensions 7 and 8 can be found under [[Lower bounds on APN-distance for all known APN functions in dimension 7]] and [[Lower bounds on APN-distance for all known APN functions in dimension 8]], respectively, due to their large size.
<table>
<tr>
<th colspan="4">DIMENSION 9</th>
</tr>
<tr>
<th>ID</th>
<th><math>\Pi_F^0</math></th>
<th><math>m_F</math></th>
<th>lower bound</th>
</tr>
<tr>
<td>1</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>2</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>3</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>4</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>5</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>6</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>7</td>
<td>231<sup>3</sup>, 237<sup>45</sup>, 240<sup>27</sup>, 243<sup>36</sup>, 246<sup>54</sup>, 249<sup>36</sup>, 252<sup>36</sup>, 255<sup>37</sup>, 258<sup>27</sup>, 261<sup>45</sup>, 264<sup>54</sup>, 267<sup>45</sup>, 270<sup>36</sup>, 273<sup>9</sup>, 276<sup>18</sup>, 279<sup>3</sup>, 512</td>
<td>231</td>
<td>78</td>
</tr>
<tr>
<td>8</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>9</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>10</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
<tr>
<td>11</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
</table>

Revision as of 16:18, 19 August 2019

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 ofKnown 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 tables for dimensions 7 and 8 can be found under Lower bounds on APN-distance for all known APN functions in dimension 7 and Lower bounds on APN-distance for all known APN functions in dimension 8, respectively, due to their large size.

DIMENSION 9
ID [math]\displaystyle{ \Pi_F^0 }[/math] [math]\displaystyle{ m_F }[/math] lower bound
1 255511, 512 255 86
2 255511, 512 255 86
3 255511, 512 255 86
4 255511, 512 255 86
5 255511, 512 255 86
6 255511, 512 255 86
7 2313, 23745, 24027, 24336, 24654, 24936, 25236, 25537, 25827, 26145, 26454, 26745, 27036, 2739, 27618, 2793, 512 231 78
8 255511, 512 255 86
9 255511, 512 255 86
10 255511, 512 255 86
11 255511, 512 255 86
  1. Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.