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

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 | + | 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 index 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 as [[Lower bounds on APN-distance for all known APN functions in dimension 8]]. |

<table> | <table> | ||

Line 214: | Line 214: | ||

<td>38</td> | <td>38</td> | ||

</tr> | </tr> | ||

+ | |||

+ | <tr class="strongDivider"> | ||

+ | <td>9</td> | ||

+ | <td>9.7</td> | ||

+ | <td>231</td> | ||

+ | <td>78</td> | ||

+ | </tr> | ||

+ | |||

+ | <tr> | ||

+ | <td>9</td> | ||

+ | <td>all others</td> | ||

+ | <td>255</td> | ||

+ | <td>86</td> | ||

+ | </tr> | ||

+ | |||

+ | <tr class="strongDivider"> | ||

+ | <td>10</td> | ||

+ | <td>10.4</td> | ||

+ | <td>477</td> | ||

+ | <td>160</td> | ||

+ | </tr> | ||

+ | |||

+ | <tr> | ||

+ | <td>10</td> | ||

+ | <td>all others</td> | ||

+ | <td>495</td> | ||

+ | <td>166</td> | ||

+ | </tr> | ||

+ | |||

+ | <tr class="strongDivider"> | ||

+ | <td>11</td> | ||

+ | <td>11.12</td> | ||

+ | <td>978</td> | ||

+ | <td>327</td> | ||

+ | </tr> | ||

+ | |||

+ | <tr> | ||

+ | <td>11</td> | ||

+ | <td>all others</td> | ||

+ | <td>1023</td> | ||

+ | <td>342</td> | ||

+ | </tr> | ||

+ | |||

+ | |||

</table> | </table> |

## Revision as of 21:46, 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 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 index 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 as Lower bounds on APN-distance for all known APN functions in dimension 8.

Dimension | F | Lower bound | |
---|---|---|---|

4 | x^{3} |
3 | 2 |

5 | x^{3} |
15 | 6 |

5 | x^{5} |
15 | 6 |

5 | x^{15} |
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 |

- ↑ Budaghyan L, Carlet C, Helleseth T, Kaleyski N. Changing Points in APN Functions. IACR Cryptology ePrint Archive. 2018;2018:1217.