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 91: Line 91:
<td>255</td>
<td>255</td>
<td>86</td>
<td>86</td>
</tr>
</table>
<table>
<tr>
<th colspan="4">DIMENSION 10</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>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>2</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>3</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>4</td>
<td>477<sup>40</sup>, 483<sup>30</sup>, 489<sup>60</sup>, 495<sup>57</sup>, 501<sup>220</sup>, 507<sup>70</sup>, 513<sup>160</sup>, 519<sup>105</sup>, 525<sup>150</sup>, 531<sup>40</sup>, 537<sup>50</sup>, 543<sup>1</sup>, 549<sup>40</sup>, 1024</td>
<td>477</td>
<td>160</td>
</tr>
<tr>
<td>5</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>7</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
<tr>
<td>8</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
</tr>


</table>
</table>

Revision as of 16:22, 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
DIMENSION 10
ID [math]\displaystyle{ \Pi_F^0 }[/math] [math]\displaystyle{ m_F }[/math] lower bound
1 495682, 543341, 1024 495 166
2 495682, 543341, 1024 495 166
3 495682, 543341, 1024 495 166
4 47740, 48330, 48960, 49557, 501220, 50770, 513160, 519105, 525150, 53140, 53750, 5431, 54940, 1024 477 160
5 495682, 543341, 1024 495 166
6 495682, 543341, 1024 495 166
7 495682, 543341, 1024 495 166
8 495682, 543341, 1024 495 166
  1. Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.