Paper 2020/1359

On two fundamental problems on APN power functions

Lilya Budaghyan and Marco Calderini and Claude Carlet and 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, which is the only one among the six families for which it remains unknown. In this paper, we derive alternative representations for functions from the infinite APN monomial families, with the hope that this will pave the way for further progress in this area. More concretely, 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 the simplest possible in the sense that no two power functions of lesser algebraic degree can produce the same composition. We also investigate compositions of the form $x^i \circ L \circ x^{1/j}$ for a linear polynomial $L$, and computationally determine all APN functions of this form for $n \le 9$ and for $L$ with coefficients in $\mathbb{F}_2$ in order to confirm that our theoretical constructions exhaust all possible cases. We present some observations and computational data on power functions with exponent of the form $\sum_{i = 1}^{k-1} 2^{2ni} - 1$, which can be seen as generalizations of both the inverse and the Dobbertin APN families. Finally, we present our computational data on the Walsh coefficients of the Dobbertin function over $\F$ for $n \le 35$, and conjecture the exact form of its Walsh spectrum.