Lower bounds on APN-distance for all known APN functions: Difference between revisions
No edit summary |
No edit summary |
||
Line 6: | Line 6: | ||
<tr> | <tr> | ||
<th | <th>Dimension</th> | ||
<th>F</th> | |||
<th> | |||
<th><math>m_F</math></th> | <th><math>m_F</math></th> | ||
<th> | <th>Lower bound</th> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>4</td> | |||
<td>x<sup>3</sup></td> | |||
<td>3</td> | |||
<td>2</td> | <td>2</td> | ||
</tr> | </tr> | ||
<tr> | <tr class="strongDivider"> | ||
<td> | <td>5</td> | ||
<td> | <td>x<sup>3</sup></td> | ||
<td>15</td> | |||
<td>6</td> | |||
<td> | |||
<td> | |||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>5</td> | <td>5</td> | ||
<td> | <td>x<sup>5</sup></td> | ||
<td> | <td>15</td> | ||
<td>6</td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>5</td> | |||
<td>x<sup>15</sup></td> | |||
<td>9</td> | <td>9</td> | ||
<td> | <td>4</td> | ||
</tr> | </tr> | ||
<tr> | <tr class="strongDivider"> | ||
<td>6</td> | |||
<td>1.1</td> | |||
<td>27</td> | |||
<td>10</td> | <td>10</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>1.2</td> | ||
<td> | <td>27</td> | ||
<td> | <td>10</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
< | <td>6</td> | ||
<td>2.1</td> | |||
<td>15</td> | |||
<td>6</td> | |||
</tr> | </tr> | ||
<tr> | <tr> | ||
< | <td>6</td> | ||
< | <td>2.2</td> | ||
< | <td>27</td> | ||
< | <td>10</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.3</td> | ||
<td> | <td>27</td> | ||
<td> | <td>10</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.4</td> | ||
<td> | <td>15</td> | ||
<td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.5</td> | ||
<td> | <td>15</td> | ||
<td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.6</td> | ||
<td> | <td>15</td> | ||
<td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.7</td> | ||
<td> | <td>15</td> | ||
<td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>6</td> | <td>6</td> | ||
<td> | <td>2.8</td> | ||
<td> | <td>15</td> | ||
<td> | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>6</td> | ||
<td> | <td>2.9</td> | ||
<td> | <td>21</td> | ||
<td> | <td>8</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>6</td> | |||
<td>2.10</td> | |||
<td>21</td> | |||
<td>8</td> | <td>8</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
< | <td>6</td> | ||
<td>2.11</td> | |||
<td>15</td> | |||
<td>6</td> | |||
</tr> | </tr> | ||
<tr> | <tr> | ||
< | <td>6</td> | ||
< | <td>2.12</td> | ||
< | <td>15</td> | ||
< | <td>6</td> | ||
</tr> | </tr> | ||
<tr> | <tr class="strongDivider"> | ||
<td> | <td>7</td> | ||
<td> | <td>7.1</td> | ||
<td> | <td>54</td> | ||
<td> | <td>19</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>7</td> | ||
<td> | <td>all others</td> | ||
<td> | <td>63</td> | ||
<td> | <td>22</td> | ||
</tr> | </tr> | ||
<tr> | <tr class="strongDivider"> | ||
<td> | <td>8</td> | ||
<td> | <td>1.1 - 1.13</td> | ||
<td> | <td>111</td> | ||
<td> | <td>38</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>1.14</td> | ||
<td> | <td>99</td> | ||
<td> | <td>34</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>1.15 - 1.17</td> | ||
<td> | <td>111</td> | ||
<td> | <td>38</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>2.1</td> | ||
<td> | <td>111</td> | ||
<td> | <td>38</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>3.1</td> | ||
<td> | <td>111</td> | ||
<td> | <td>38</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>8</td> | <td>8</td> | ||
<td> | <td>4.1</td> | ||
<td> | <td>99</td> | ||
<td> | <td>34</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>5.1</td> | ||
<td> | <td>105</td> | ||
<td> | <td>36</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>6.1</td> | ||
<td> | <td>105</td> | ||
<td> | <td>36</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td> | <td>8</td> | ||
<td> | <td>7.1</td> | ||
<td>111</td> | |||
<td>38</td> | |||
<td> | |||
<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 |
- ↑ Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.