Abstract We study combinatorial properties of plateaued functions $$F :\mathbb {F}_p^n \rightarrow \mathbb {F}_p^m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>:</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> <mml:mo>→</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mi>m</mml:mi> </mml:msubsup> </mml:mrow> </mml:math> . 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.

APN functions provide optimal resistance to differential attacks when used as building blocks in block ciphers and are thus of great theoretical interest. One of the most important properties of APN functions is their linearity, which is directly related to the Walsh spectrum of the function. In this paper, we establish two novel connections that allow us to derive strong conditions on the Walsh spectra of quadratic APN functions. We prove that the Walsh transform of a quadratic APN functionFoperating onn= 2kbits is uniquely associated with a vector space partition of Fn2and a specific blocking set in the corresponding projective space PG(n−1, 2). These connections allow us to prove a variety of results on the Walsh spectrum ofF. We prove for instance thatFcan have at most one component function of amplitude larger than 23n/4. We also find the first nontrivial upper bound on the number of bent component functions of a quadratic APN function, and provide conditions for a function to be CCZ-equivalent to a permutation based on its number of bent components.

Abstract We observe that on the binary finite fields the classification of 2-to-1 binomials is equivalent to the classification of o-monomials, which is a well-studied and elusive problem in finite geometry. This connection implies a complete classification of 2-to-1 binomials $$b=x^d+ux^e$$ b = x d + u x e for a large set of values of ( d , e ). Further, we show that a number of the known infinite families of 2-to-1 maps can be traced back to o-polynomials or to difference maps of APN maps. We also provide some connections between 2-to-1 maps and hyperovals in non-desarguesian planes.

Abstract Brawley and Carlitz introduced diamond products of elements of finite fields and associated composed products of polynomials in 1987. Composed products yield a method to construct irreducible polynomials of large composite degrees from irreducible polynomials of lower degrees. We show that the composed product of two irreducible polynomials of degrees m and n is again irreducible if and only if m and n are coprime and the involved diamond product satisfies a special cancellation property, the so-called conjugate cancellation. This completes the characterization of irreducible composed products, considered in several previous papers. More generally, we give precise criteria when a diamond product satisfies conjugate cancellation. For diamond products defined via bivariate polynomials, we prove simple criteria that characterize when conjugate cancellation holds. We also provide efficient algorithms to check these criteria. We achieve stronger results as well as more efficient algorithms in the case that the polynomials are bilinear. Lastly, we consider possible constructions of normal elements using composed products and the methods we developed.

Almost perfect nonlinear (APN) functions yield the best possible resistance to differential attacks when used as a substitution box in the design of a block cipher. Constructing APN functions is a non-trivial problem and so far there is only one sporadic example that is not equivalent to either a monomial or a quadratic function. This is the Brinkmann-Leander-Edel-Pott function that is defined in 6 variables. In this paper, we consider in detail an original construction approach of this function suggested by Suder, which is based on the application of antiderivatives in conjunction with fast point spaces. We generalize this approach to higher dimensions and show that it does not yield any cubic APN function in 7 variables.

Abstract 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. Further, we focus on a particularly interesting case of APN maps on binary fields $$\mathbb {F}_{2^n}$$ F 2 n . We show that APN maps with the minimal image size are very close to being 3-to-1. We prove that for n even the image sets of several important families of APN maps are minimal, and as a consequence they have the classical Walsh spectrum. Finally, we present upper bounds on the image size of APN maps. For a non-bijective almost bent map f , these results imply $$\frac{2^n+1}{3}+1 \le |{\text {Im}}(f)| \le 2^n-2^{(n-1)/2}$$ 2 n + 1 3 + 1 ≤ | Im ( f ) | ≤ 2 n - 2 ( n - 1 ) / 2 .

The inverse function x → x-1on \mathbb F2nis one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x-1)+L2(x) over \mathbb F2nif n ≥ 5, where L1,L2are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics.

Abstract We explicitly determine the binary representation of the inverse of all Kasami exponents $$K_r=2^{2r}-2^r+1$$ K r = 2 2 r - 2 r + 1 modulo $$2^n-1$$ 2 n - 1 for all possible values of n and r. This includes as an important special case the APN Kasami exponents with $$\gcd (r,n)=1$$ gcd ( r , n ) = 1 . As a corollary, we determine the algebraic degree of the inverses of the Kasami functions. In particular, we show that the inverse of an APN Kasami function on $${\mathbb {F}}_{2^n}$$ F 2 n always has algebraic degree $$\frac{n+1}{2}$$ n + 1 2 if $$n\equiv 0 \pmod 3$$ n ≡ 0 ( mod 3 ) . For $$n\not \equiv 0 \pmod 3$$ n ≢ 0 ( mod 3 ) we prove that the algebraic degree is bounded from below by $$\frac{n}{3}$$ n 3 . We consider Kasami exponents whose inverses are quadratic exponents or Kasami exponents. We also determine the binary representation of the inverse of the Bracken–Leander exponent $$BL_r=2^{2r}+2^r+1$$ B L r = 2 2 r + 2 r + 1 modulo $$2^n-1$$ 2 n - 1 where $$n=4r$$ n = 4 r and r odd. We show that the algebraic degree of the inverse of the Bracken–Leander function is $$\frac{n+2}{2}$$ n + 2 2 .