Lower bounds on APN-distance for all known APN functions: Difference between revisions
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 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 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. | ||
Line 162: | Line 162: | ||
<td>495</td> | <td>495</td> | ||
<td>166</td> | <td>166</td> | ||
</tr> | |||
</table> | |||
<table> | |||
<tr> | |||
<th colspan="4">DIMENSION 11</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>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>2</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>3</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>4</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>5</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>6</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>7</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>8</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>9</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>10</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>11</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | |||
<tr> | |||
<td>12</td> | |||
<td>978<sup>11</sup>, 981<sup>33</sup>, 984<sup>22</sup>, 987<sup>66</sup>, 990<sup>66</sup>, 993<sup>55</sup>, 996<sup>77</sup>, 999<sup>77</sup>, 1002<sup>110</sup>, 1005<sup>55</sup>, 1008<sup>66</sup>, 1011<sup>55</sup>, 1014<sup>121</sup>, 1017<sup>55</sup>, 1020<sup>121</sup>, 1023<sup>78</sup>, 1026<sup>88</sup>, 1029<sup>88</sup>, 1032<sup>66</sup>, 1035<sup>110</sup>, 1038<sup>55</sup>, 1041<sup>99</sup>, 1044<sup>77</sup>, 1047<sup>88</sup>, 1050<sup>44</sup>, 1053<sup>66</sup>, 1056<sup>55</sup>, 1059<sup>44</sup>, 1062<sup>66</sup>, 1065<sup>22</sup>, 1068<sup>11</sup>, 2048</td> | |||
<td>978</td> | |||
<td>326</td> | |||
</tr> | |||
<tr> | |||
<td>13</td> | |||
<td>1023<sup>2047</sup>, 2048</td> | |||
<td>255</td> | |||
<td>86</td> | |||
</tr> | </tr> | ||
</table> | </table> |
Revision as of 16:27, 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 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 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 |
DIMENSION 11 | |||
---|---|---|---|
ID | [math]\displaystyle{ \Pi_F^0 }[/math] | [math]\displaystyle{ m_F }[/math] | lower bound |
1 | 10232047, 2048 | 255 | 86 |
2 | 10232047, 2048 | 255 | 86 |
3 | 10232047, 2048 | 255 | 86 |
4 | 10232047, 2048 | 255 | 86 |
5 | 10232047, 2048 | 255 | 86 |
6 | 10232047, 2048 | 255 | 86 |
7 | 10232047, 2048 | 255 | 86 |
8 | 10232047, 2048 | 255 | 86 |
9 | 10232047, 2048 | 255 | 86 |
10 | 10232047, 2048 | 255 | 86 |
11 | 10232047, 2048 | 255 | 86 |
12 | 97811, 98133, 98422, 98766, 99066, 99355, 99677, 99977, 1002110, 100555, 100866, 101155, 1014121, 101755, 1020121, 102378, 102688, 102988, 103266, 1035110, 103855, 104199, 104477, 104788, 105044, 105366, 105655, 105944, 106266, 106522, 106811, 2048 | 978 | 326 |
13 | 10232047, 2048 | 255 | 86 |
- ↑ Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.