Paper 2020/1359

On two fundamental problems on APN power functions

Lilya Budaghyan, Marco Calderini, Claude Carlet, Diana Davidova, and Nikolay Kaleyski

Abstract

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, for which it still remains unknown. We derive alternative representations for theinfinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^i \circ x^{1/j}$ of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can produce the same composition. We investigate compositions $x^i \circ L \circ x^{1/j}$ for a linear polynomial $L$, and compute all APN functions of this form for $n \le 9$ and for $L$ with binary coefficients, thereby confirming that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent $\sum_{i = 1}^{k-1} 2^{2ni} - 1$ which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for $n \le 35$, and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for $n \le 21$ show that these points cover about 2/3 of the field.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Boolean functionAPNdifferential uniformity
Contact author(s)
nikolay kaleyski @ uib no
nikolay kaleyski @ gmail com
History
2021-12-10: revised
2020-10-29: received
See all versions
Short URL
https://ia.cr/2020/1359
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1359,
      author = {Lilya Budaghyan and Marco Calderini and Claude Carlet and Diana Davidova and Nikolay Kaleyski},
      title = {On two fundamental problems on {APN} power functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1359},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1359}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.