The Combinatorial Structure and Value Distributions of Plateaued Functions

Abstract We study combinatorial properties of plateaued functions $$F :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^m$$ F : F p n → F p m . All quadratic functions, bent functions and most known APN functions are plateaued, so many cryptographic primitives rely on plateaued functions as building blocks. The main focus of our study is the interplay of the Walsh transform and linearity of a plateaued function, its differential properties, and their value distributions, i.e., the sizes of image and preimage sets. In particular, we study the special case of “almost balanced” plateaued functions, which only have two nonzero preimage set sizes, generalising, for instance, all monomial functions. We achieve several direct connections and (non)existence conditions for these functions, showing in particular that plateaued d -to-1 functions (and thus plateaued monomials) only exist for a very select choice of d , and we derive for all these functions their linearity as well as bounds on their differential uniformity. We also specifically study the Walsh transform of plateaued APN functions and their relation to their value distribution.