Image sets of perfectly nonlinear maps
This research provides a deeper understanding of the structural properties of APN maps, which are crucial for cryptographic applications, by connecting their image set minimality to their Walsh spectrum.
This paper investigates the image sets of differentially d-uniform maps, particularly focusing on APN maps on binary fields. It establishes a lower bound on image size and shows that APN maps with minimal image size exhibit a very specific preimage distribution, with several well-studied families of APN maps achieving this minimal size for even 'n'.
We consider image sets of differentially $d$-uniform maps of finite fields. We present a lower bound on the image size of such maps and study their preimage distribution, by extending methods used for planar maps. We apply the results to study $d$-uniform Dembowski-Ostrom polynomials. Further, we focus on a particularly interesting case of APN maps on binary fields. We show that APN maps with the minimal image size must have a very special preimage distribution. We prove that for an even $n$ the image sets of several well-studied families of APN maps are minimal. We present results connecting the image sets of special maps with their Walsh spectrum. Especially, we show that the fact that several large classes of APN maps have the classical Walsh spectrum is explained by the minimality of their image sets. Finally, we present upper bounds on the image size of APN maps.