**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\)
in explicit form and proof it with methods of linear programming.
It coincides with the bound given in [CHP17].
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

**Date: **received 12 Jun 2020, last revised 5 May 2021

**Contact author: **ingo at czerwinski eu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210505:214423 (All versions of this report)

**Short URL: **ia.cr/2020/705

[ Cryptology ePrint archive ]