The combinatorial structure and value distributions of plateaued functions
This work addresses foundational problems in cryptography by analyzing plateaued functions, which are crucial building blocks for cryptographic primitives, but it is incremental as it builds on known properties and functions.
The paper tackles the combinatorial properties of plateaued functions in cryptography, establishing connections between their Walsh transform, linearity, differential properties, and value distributions, with results including existence conditions and bounds on differential uniformity for specific cases like plateaued d-to-1 functions.
We study combinatorial properties of plateaued functions $F \colon \mathbb{F}_p^n \rightarrow \mathbb{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, generalizing for instance all monomial functions. We achieve several direct connections and (non)existence conditions for these functions, showing for instance 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.