Cryptology ePrint Archive: Report 2020/705

On the minimal value set size of APN functions

Ingo Czerwinski

Abstract: We give a lower bound for the size of the value set of almost perfect nonlinear (APN) functions $F\colon \mathbb{F}_{2^n} \to \mathbb{F}_{2^n}$. For $n$ even it is $\frac{ 2^n + 2 }{3}$ and sharp as the simple example $F(x) = x^3$ shows. The sharp lower bound for $n$ odd has to lie between $\frac{ 2^n + 1 }{3}$ and $2^{n-1}$. Sharp bounds for the cases $n = 3$ and $n = 5$ are explicitly given.

Category / Keywords: foundations / Boolean functions, Cryptographic S-boxes, Almost perfect nonlinear (APN), Value set size