Known infinite families of APN power functions over GF(2^n): Difference between revisions

From Boolean
Jump to navigation Jump to search
mNo edit summary
No edit summary
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
The following table provides a summary of all known infinite families of power APN functions of the form <math>F(x) = x^d</math>.
The following table provides a summary of all known infinite families of power APN functions of the form <span class="htmlMath">F(x) = x<sup>d</sup></span>.


<table>
<table>
Line 6: Line 6:
<th>Exponent</th>
<th>Exponent</th>
<th>Conditions</th>
<th>Conditions</th>
<th><math>\deg(x^d)</math></th>
<th><span class="htmlMath"><span class="latexCommand">deg</span>(x<sup>d</sup>)</span></th>
<th>Reference</th>
<th>Reference</th>
</tr>
</tr>
Line 12: Line 12:
<tr>
<tr>
<td>Gold</td>
<td>Gold</td>
<td><math>2^i + 1</math></td>
<td><span class="htmlMath">2<sup>i</sup> + 1</span></td>
<td><math>\gcd(i,n) = 1</math></td>
<td><span class="htmlMath"><span class="latexCommand">gcd</span>(i,n) = 1</span></td>
<td>2</td>
<td><span class="htmlMath">2</span></td>
<td> <ref>Robert Gold, ''Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.)'', IEEE transactions on Information Theory, 14(1):154-156, 1968</ref><ref name="kaisa_ref">Kaisa Nyberg, ''Differentially uniform mappings for cryptography'', Workshop on the Theory and Application of Cryptographic Techniques, pp. 55-64, Springer, 1993</ref>
<td> <ref>R. Gold. Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Trans. Inf. Theory, 14, pp. 154-156, 1968. https://doi.org/10.1109/TIT.1968.1054106</ref><ref name="kaisa">K. Nyberg. Differentially uniform mappings for cryptography. Advances in Cryptography, EUROCRYPT’93, Lecture Notes in Computer Science 765, pp. 55-64, 1994. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_6</ref>
  </td>
  </td>
</tr>
</tr>
<tr>
<tr>


<tr>
<tr>
<td>Kasami</td>
<td>Kasami</td>
<td><math>2^{2i} - 2^i + 1</math></td>
<td><span class="htmlMath">2<sup>2i</sup> - 2<sup>i</sup> + 1</span></td>
<td><math>\gcd(i,n) = 1</math></td>
<td><span class="htmlMath"><span class="latexCommand">gcd</span>(i,n) = 1</span></td>
<td><math>i + 1</math></td>
<td><span class="htmlMath">i + 1</span></td>
<td><ref>Heeralal Janwa and Richard M Wilson, ''Hyperplane sections of Fermat varieties in <math>P^3</math> in char. 2 and some applications to cyclic codes'', International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pp. 180-194, Springer, 1993</ref><ref>Tadao Kasami, ''The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes'', Information and Control, 18(4):369-394, 1971</ref></td>
<td><ref>H. Janwa, R. M. Wilson. Hyperplane sections of Fermat varieties in P<sup>3</sup> in char. 2 and some applications to cyclic codes. Proceedings of AAECC-10, LNCS, vol. 673, Berlin, Springer-Verlag, pp. 180-194, 1993. https://doi.org/10.1007/3-540-56686-4_43</ref><ref>Kasami T. The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes. Inform. and Control, 18, pp. 369-394, 1971. https://doi.org/10.1016/S0019-9958(71)90473-6</ref></td>
</tr>
</tr>


<tr>
<tr>
<td>Welch</td>
<td>Welch</td>
<td><math>2^t + 3</math></td>
<td><span class="htmlMath">2<sup>t</sup> + 3</span></td>
<td><math>n = 2t + 1</math></td>
<td><span class="htmlMath">n = 2t + 1</span></td>
<td><math>3</math></td>
<td><span class="htmlMath">3</span></td>
<td><ref>Hans Dobbertin, ''Almost perfect nonlinear power functions on <math>GF(2^n)</math>: the Welch case'', IEEE Transactions on Information Theory, 45(4):1271-1275, 1999</ref></td>
<td><ref>H. Dobbertin. Almost perfect nonlinear power functions over GF(2<sup>n</sup>): the Welch case. IEEE Trans. Inform. Theory, 45, pp. 1271-1275, 1999. https://doi.org/10.1109/18.761283</ref></td>
</tr>
</tr>


<tr>
<tr>
<td rowspan="2">Niho</td>
<td rowspan="2">Niho</td>
<td><math>2^t + 2^{t/2} - 1, t</math> even</td>
<td><span class="htmlMath">2<sup>t</sup> + 2<sup>t/2</sup> - 1, t</span> even</td>
<td rowspan="2"><math>n = 2t + 1</math></td>
<td rowspan="2"><span class="htmlMath">n = 2t + 1</span></td>
<td><math>(t+2)/2</math></td>
<td><span class="htmlMath">(t+2)/2</span></td>
<td rowspan="2"><ref>Hans Dobbertin, ''Almost perfect nonlinear power functions on <math>GF(2^n)</math>: the Niho case'', Information and Computation, 151(1-2):57-72, 1999</ref></td>
<td rowspan="2"><ref>H. Dobbertin. Almost perfect nonlinear power functions over GF(2<sup>n</sup>): the Niho case. Inform. and Comput., 151, pp. 57-72, 1999. https://doi.org/10.1006/inco.1998.2764</ref></td>
</tr>
</tr>


<tr>
<tr>
<td><math>2^t + 2^{(3t+1)/2} - 1, t</math> odd</td>
<td><span class="htmlMath">2<sup>t</sup> + 2<sup>(3t+1)/2</sup> - 1, t</span> odd</td>
<td><math>t + 1</math></td>
<td><span class="htmlMath">t + 1</span></td>
</tr>
</tr>


<tr>
<tr>
<td>Inverse</td>
<td>Inverse</td>
<td><math>2^{2t} - 1</math></td>
<td><span class="htmlMath">2<sup>2t</sup> - 1</span></td>
<td><math>n = 2t + 1</math></td>
<td><span class="htmlMath">n = 2t + 1</span></td>
<td><math>n-1</math></td>
<td><span class="htmlMath">n-1</span></td>
<td><ref name="kaisa_ref" /><ref>Thomas Beth and Cunsheng Ding, ''On almost perfect nonlinear permutations'', Workshop on the Theory and Application of Cryptographic Techniques, pp. 65-76, Springer, 1993</ref>
<td><ref name="kaisa" /><ref>T. Beth, C. Ding. On almost perfect nonlinear permutations. Advances in Cryptology-EUROCRYPT’93, Lecture Notes in Computer Science, 765, Springer-Verlag, New York, pp. 65-76, 1993. https://doi.org/10.1007/3-540-48285-7_7</ref>
</tr>
</tr>


<tr>
<tr>
<td>Dobbertin</td>
<td>Dobbertin</td>
<td><math>2^{4i} + 2^{3i} + 2^{2i} + 2^i - 1</math></td>
<td><span class="htmlMath">2<sup>4i</sup> + 2<sup>3i</sup> + 2<sup>2i</sup> + 2<sup>i</sup> - 1</span></td>
<td><math>n = 5i</math></td>
<td><span class="htmlMath">n = 5i</span></td>
<td><math>i + 3</math></td>
<td><span class="htmlMath">i + 3</span></td>
<td><ref>Hans Dobbertin, ''Almost perfect nonlinear power functions over <math>GF(2^n)</math>: a new case for <math>n</math> divisible by 5'', Proceedings of the fifth conference on Finite Fields and Applications FQ5, pp.113-121</ref></td>
<td><ref>H. Dobbertin. Almost perfect nonlinear power functions over GF (2<sup>n</sup>): a new case for n divisible by 5. Proceedings of Finite Fields and Applications FQ5, pp. 113-121, 2000. https://doi.org/10.1007/978-3-642-56755-1_11</ref></td>
</tr>
</tr>


</table>
</table>

Latest revision as of 20:02, 10 July 2020

The following table provides a summary of all known infinite families of power APN functions of the form F(x) = xd.

Family Exponent Conditions deg(xd) Reference
Gold 2i + 1 gcd(i,n) = 1 2 [1][2]
Kasami 22i - 2i + 1 gcd(i,n) = 1 i + 1 [3][4]
Welch 2t + 3 n = 2t + 1 3 [5]
Niho 2t + 2t/2 - 1, t even n = 2t + 1 (t+2)/2 [6]
2t + 2(3t+1)/2 - 1, t odd t + 1
Inverse 22t - 1 n = 2t + 1 n-1 [2][7]
Dobbertin 24i + 23i + 22i + 2i - 1 n = 5i i + 3 [8]
  1. R. Gold. Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Trans. Inf. Theory, 14, pp. 154-156, 1968. https://doi.org/10.1109/TIT.1968.1054106
  2. 2.0 2.1 K. Nyberg. Differentially uniform mappings for cryptography. Advances in Cryptography, EUROCRYPT’93, Lecture Notes in Computer Science 765, pp. 55-64, 1994. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_6
  3. H. Janwa, R. M. Wilson. Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes. Proceedings of AAECC-10, LNCS, vol. 673, Berlin, Springer-Verlag, pp. 180-194, 1993. https://doi.org/10.1007/3-540-56686-4_43
  4. Kasami T. The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes. Inform. and Control, 18, pp. 369-394, 1971. https://doi.org/10.1016/S0019-9958(71)90473-6
  5. H. Dobbertin. Almost perfect nonlinear power functions over GF(2n): the Welch case. IEEE Trans. Inform. Theory, 45, pp. 1271-1275, 1999. https://doi.org/10.1109/18.761283
  6. H. Dobbertin. Almost perfect nonlinear power functions over GF(2n): the Niho case. Inform. and Comput., 151, pp. 57-72, 1999. https://doi.org/10.1006/inco.1998.2764
  7. T. Beth, C. Ding. On almost perfect nonlinear permutations. Advances in Cryptology-EUROCRYPT’93, Lecture Notes in Computer Science, 765, Springer-Verlag, New York, pp. 65-76, 1993. https://doi.org/10.1007/3-540-48285-7_7
  8. H. Dobbertin. Almost perfect nonlinear power functions over GF (2n): a new case for n divisible by 5. Proceedings of Finite Fields and Applications FQ5, pp. 113-121, 2000. https://doi.org/10.1007/978-3-642-56755-1_11