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 6: Line 6:


<tr>
<tr>
<th colspan="4">DIMENSION 9</th>
<th>Dimension</th>
</tr>
<th>F</th>
 
<tr>
<th>ID</th>
<th><math>\Pi_F^0</math></th>
<th><math>m_F</math></th>
<th><math>m_F</math></th>
<th>lower bound</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>


<tr>
<tr>
<td>4</td>
<td>x<sup>3</sup></td>
<td>3</td>
<td>2</td>
<td>2</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
</tr>


<tr>
<tr class="strongDivider">
<td>3</td>
<td>5</td>
<td>255<sup>511</sup>, 512</td>
<td>x<sup>3</sup></td>
<td>255</td>
<td>15</td>
<td>86</td>
<td>6</td>
</tr>
 
<tr>
<td>4</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
</tr>


<tr>
<tr>
<td>5</td>
<td>5</td>
<td>255<sup>511</sup>, 512</td>
<td>x<sup>5</sup></td>
<td>255</td>
<td>15</td>
<td>86</td>
</tr>
 
<tr>
<td>6</td>
<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>


<tr>
<tr>
<td>5</td>
<td>x<sup>15</sup></td>
<td>9</td>
<td>9</td>
<td>255<sup>511</sup>, 512</td>
<td>4</td>
<td>255</td>
<td>86</td>
</tr>
</tr>


<tr>
<tr class="strongDivider">
<td>6</td>
<td>1.1</td>
<td>27</td>
<td>10</td>
<td>10</td>
<td>255<sup>511</sup>, 512</td>
<td>255</td>
<td>86</td>
</tr>
</tr>


<tr>
<tr>
<td>11</td>
<td>6</td>
<td>255<sup>511</sup>, 512</td>
<td>1.2</td>
<td>255</td>
<td>27</td>
<td>86</td>
<td>10</td>
</tr>
</tr>
</table>
<table>


<tr>
<tr>
<th colspan="4">DIMENSION 10</th>
<td>6</td>
<td>2.1</td>
<td>15</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<th>ID</th>
<td>6</td>
<th><math>\Pi_F^0</math></th>
<td>2.2</td>
<th><math>m_F</math></th>
<td>27</td>
<th>lower bound</th>
<td>10</td>
</tr>
</tr>


<tr>
<tr>
<td>1</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.3</td>
<td>495</td>
<td>27</td>
<td>166</td>
<td>10</td>
</tr>
</tr>


<tr>
<tr>
<td>2</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.4</td>
<td>495</td>
<td>15</td>
<td>166</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<td>3</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.5</td>
<td>495</td>
<td>15</td>
<td>166</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<td>4</td>
<td>6</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>2.6</td>
<td>477</td>
<td>15</td>
<td>160</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<td>5</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.7</td>
<td>495</td>
<td>15</td>
<td>166</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<td>6</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.8</td>
<td>495</td>
<td>15</td>
<td>166</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<td>7</td>
<td>6</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>2.9</td>
<td>495</td>
<td>21</td>
<td>166</td>
<td>8</td>
</tr>
</tr>


<tr>
<tr>
<td>6</td>
<td>2.10</td>
<td>21</td>
<td>8</td>
<td>8</td>
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
<td>495</td>
<td>166</td>
</tr>
</tr>
</table>
<table>


<tr>
<tr>
<th colspan="4">DIMENSION 11</th>
<td>6</td>
<td>2.11</td>
<td>15</td>
<td>6</td>
</tr>
</tr>


<tr>
<tr>
<th>ID</th>
<td>6</td>
<th><math>\Pi_F^0</math></th>
<td>2.12</td>
<th><math>m_F</math></th>
<td>15</td>
<th>lower bound</th>
<td>6</td>
</tr>
</tr>


<tr>
<tr class="strongDivider">
<td>1</td>
<td>7</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>7.1</td>
<td>255</td>
<td>54</td>
<td>86</td>
<td>19</td>
</tr>
</tr>


<tr>
<tr>
<td>2</td>
<td>7</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>all others</td>
<td>255</td>
<td>63</td>
<td>86</td>
<td>22</td>
</tr>
</tr>


<tr>
<tr class="strongDivider">
<td>3</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>1.1 - 1.13</td>
<td>255</td>
<td>111</td>
<td>86</td>
<td>38</td>
</tr>
</tr>


<tr>
<tr>
<td>4</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>1.14</td>
<td>255</td>
<td>99</td>
<td>86</td>
<td>34</td>
</tr>
</tr>


<tr>
<tr>
<td>5</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>1.15 - 1.17</td>
<td>255</td>
<td>111</td>
<td>86</td>
<td>38</td>
</tr>
</tr>


<tr>
<tr>
<td>6</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>2.1</td>
<td>255</td>
<td>111</td>
<td>86</td>
<td>38</td>
</tr>
</tr>


<tr>
<tr>
<td>7</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>3.1</td>
<td>255</td>
<td>111</td>
<td>86</td>
<td>38</td>
</tr>
</tr>


<tr>
<tr>
<td>8</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>4.1</td>
<td>255</td>
<td>99</td>
<td>86</td>
<td>34</td>
</tr>
</tr>


<tr>
<tr>
<td>9</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>5.1</td>
<td>255</td>
<td>105</td>
<td>86</td>
<td>36</td>
</tr>
</tr>


<tr>
<tr>
<td>10</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>6.1</td>
<td>255</td>
<td>105</td>
<td>86</td>
<td>36</td>
</tr>
</tr>


<tr>
<tr>
<td>11</td>
<td>8</td>
<td>1023<sup>2047</sup>, 2048</td>
<td>7.1</td>
<td>255</td>
<td>111</td>
<td>86</td>
<td>38</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 19:16, 21 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 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
  1. Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.