Paper 2016/887

A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size $2^{4k+2}$

Anne Canteaut, Sébastien Duval, and Léo Perrin

Abstract

The existence of Almost Perfect Nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in~2009. However it is still unknown whether this example can be generalised to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on (4k+2) variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalise this family, and we completely solve the two open problems raised by Perrin et al. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four.

Note: Minor modifications compared to the previous submission. This version is the same as the paper to appear in the IEEE Transactions on Information Theory.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. IEEE Transactions on Information Theory
Keywords
Boolean functionSboxAPNdifferential uniformitynonlinearity
Contact author(s)
Anne Canteaut @ inria fr
History
2017-02-28: revised
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/887
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/887,
      author = {Anne Canteaut and Sébastien Duval and Léo Perrin},
      title = {A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size $2^{4k+2}$},
      howpublished = {Cryptology ePrint Archive, Paper 2016/887},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/887}},
      url = {https://eprint.iacr.org/2016/887}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.