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

From Boolean Functions
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
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 table lists a lower bound on the Hamming distance between a representative from each known CCZ-equivalence class of APN functions up to dimension 11, and the closes APN function (in terms of Hamming distance). The lower bound <math>l(F)</math> between an (n,n)-function F and the closest APN function is a CCZ-invariant, and is calculated via the formula <math>l(F) = \lceil \frac{m_F}{3} \rceil + 1</math>, where <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><ref>L. Budaghyan, C. Carlet, T. Helleseth, N. Kaleyski. On the distance between APN functions. IEEE Trans. Inf. Theory, early access article. https://doi.org/10.1109/TIT.2020.2983684</ref>. 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 table below shows the lower bounds computed for some of the known APN functions for dimensions between 4 and 11. The functions in dimensions between 5 and 8 are indexed according to the table of [[known switching classes of APN functions over GF(2^n) for n = 5,6,7,8]]. The ones between 9 and 11 are indexed according to the table of [[CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11)]]. A separate table listing these results for the (more than 8000) known APN functions in dimension 8 is available under [[Lower bounds on APN-distance for all known APN functions in dimension 8]]. Note that all known APN functions in dimension 7 from the [[known quadratic APN polynomial functions over GF(2^7)]] have the same value of the lower bound as e.g. <math>x^3</math> over <math>\mathbb{F}_{2^7}</math>.
  
 
<table>
 
<table>
  
 
<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>
  
 
<tr>
 
<tr>
−
<td>4</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>
+
<td>6</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
 
<td>5</td>
 
<td>5</td>
−
<td>255<sup>511</sup>, 512</td>
+
<td>x<sup>15</sup></td>
−
<td>255</td>
+
<td>9</td>
−
<td>86</td>
+
<td>4</td>
 
</tr>
 
</tr>
  
−
<tr>
+
<tr class="strongDivider">
 
<td>6</td>
 
<td>6</td>
−
<td>255<sup>511</sup>, 512</td>
+
<td>1.1</td>
−
<td>255</td>
+
<td>27</td>
−
<td>86</td>
+
<td>10</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>7</td>
+
<td>6</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>1.2</td>
−
<td>231</td>
+
<td>27</td>
−
<td>78</td>
+
<td>10</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>8</td>
+
<td>6</td>
−
<td>255<sup>511</sup>, 512</td>
+
<td>2.1</td>
−
<td>255</td>
+
<td>15</td>
−
<td>86</td>
+
<td>6</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>9</td>
+
<td>6</td>
−
<td>255<sup>511</sup>, 512</td>
+
<td>2.2</td>
−
<td>255</td>
+
<td>27</td>
−
<td>86</td>
+
<td>10</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
 +
<td>6</td>
 +
<td>2.3</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>2.4</td>
−
<td>255</td>
+
<td>15</td>
−
<td>86</td>
+
<td>6</td>
 
</tr>
 
</tr>
−
 
−
</table>
 
−
 
−
<table>
 
  
 
<tr>
 
<tr>
−
<th colspan="4">DIMENSION 10</th>
+
<td>6</td>
 +
<td>2.5</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.6</td>
−
<th><math>m_F</math></th>
+
<td>15</td>
−
<th>lower bound</th>
+
<td>6</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>1</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>2</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>3</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>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.10</td>
−
<td>477</td>
+
<td>21</td>
−
<td>160</td>
+
<td>8</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>5</td>
+
<td>6</td>
−
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
+
<td>2.11</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.12</td>
−
<td>495</td>
+
<td>15</td>
−
<td>166</td>
+
<td>6</td>
 
</tr>
 
</tr>
  
−
<tr>
+
<tr class="strongDivider">
 
<td>7</td>
 
<td>7</td>
−
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
+
<td>7.1</td>
−
<td>495</td>
+
<td>54</td>
−
<td>166</td>
+
<td>19</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>8</td>
+
<td>7</td>
−
<td>495<sup>682</sup>, 543<sup>341</sup>, 1024</td>
+
<td>all others</td>
−
<td>495</td>
+
<td>63</td>
−
<td>166</td>
+
<td>22</td>
 
</tr>
 
</tr>
  
−
</table>
+
<tr class="strongDivider">
−
 
+
<td>8</td>
−
<table>
+
<td>1.1 - 1.13</td>
−
 
+
<td>111</td>
−
<tr>
+
<td>38</td>
−
<th colspan="4">DIMENSION 11</th>
 
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<th>ID</th>
+
<td>8</td>
−
<th><math>\Pi_F^0</math></th>
+
<td>1.14</td>
−
<th><math>m_F</math></th>
+
<td>99</td>
−
<th>lower bound</th>
+
<td>34</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>1</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>2</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>3</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>4</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>5</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>6</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>7</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>
  
−
<tr>
+
<tr class="strongDivider">
−
<td>8</td>
+
<td>9</td>
−
<td>1023<sup>2047</sup>, 2048</td>
+
<td>9.7</td>
−
<td>255</td>
+
<td>231</td>
−
<td>86</td>
+
<td>78</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
 
<td>9</td>
 
<td>9</td>
−
<td>1023<sup>2047</sup>, 2048</td>
+
<td>all others</td>
 
<td>255</td>
 
<td>255</td>
 
<td>86</td>
 
<td>86</td>
 
</tr>
 
</tr>
  
−
<tr>
+
<tr class="strongDivider">
 
<td>10</td>
 
<td>10</td>
−
<td>1023<sup>2047</sup>, 2048</td>
+
<td>10.4</td>
−
<td>255</td>
+
<td>477</td>
−
<td>86</td>
+
<td>160</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>11</td>
+
<td>10</td>
−
<td>1023<sup>2047</sup>, 2048</td>
+
<td>all others</td>
−
<td>255</td>
+
<td>495</td>
−
<td>86</td>
+
<td>166</td>
 
</tr>
 
</tr>
  
−
<tr>
+
<tr class="strongDivider">
−
<td>12</td>
+
<td>11</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>11.12</td>
 
<td>978</td>
 
<td>978</td>
−
<td>326</td>
+
<td>327</td>
 
</tr>
 
</tr>
  
 
<tr>
 
<tr>
−
<td>13</td>
+
<td>11</td>
−
<td>1023<sup>2047</sup>, 2048</td>
+
<td>all others</td>
−
<td>255</td>
+
<td>1023</td>
−
<td>86</td>
+
<td>342</td>
 
</tr>
 
</tr>
 +
 +
  
 
</table>
 
</table>

Latest revision as of 20:55, 10 July 2020

The following table lists a lower bound on the Hamming distance between a representative from each known CCZ-equivalence class of APN functions up to dimension 11, and the closes APN function (in terms of Hamming distance). The lower bound between an (n,n)-function F and the closest APN function is a CCZ-invariant, and is calculated via the formula , where [1]. 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 table below shows the lower bounds computed for some of the known APN functions for dimensions between 4 and 11. The functions in dimensions between 5 and 8 are indexed according to the table of known switching classes of APN functions over GF(2^n) for n = 5,6,7,8. The ones between 9 and 11 are indexed according to the table of CCZ-inequivalent APN functions from the known APN classes over GF(2^n) (for n between 6 and 11). A separate table listing these results for the (more than 8000) known APN functions in dimension 8 is available under Lower bounds on APN-distance for all known APN functions in dimension 8. Note that all known APN functions in dimension 7 from the known quadratic APN polynomial functions over GF(2^7) have the same value of the lower bound as e.g. over .

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
9 9.7 231 78
9 all others 255 86
10 10.4 477 160
10 all others 495 166
11 11.12 978 327
11 all others 1023 342
  1. ↑ L. Budaghyan, C. Carlet, T. Helleseth, N. Kaleyski. On the distance between APN functions. IEEE Trans. Inf. Theory, early access article. https://doi.org/10.1109/TIT.2020.2983684
Retrieved from "https://boolean.h.uib.no/mediawiki/index.php?title=Lower_bounds_on_APN-distance_for_all_known_APN_functions&oldid=520"