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

From Boolean Functions
Jump to: navigation, search
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 18: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 , where is the lower bound on the Hamming distance between an -function and the closest APN function, and is defined as . The values of 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 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 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 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
  1. Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.