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

From Boolean Functions
Jump to: navigation, search
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 21: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 , 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 F 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.