On the minimal value set size of APN functions

Ingo Czerwinski

Paper 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 : F_{2}^{n} \to 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 odd has to lie between and . Sharp bounds for the cases and are explicitly given.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Boolean functions Cryptographic S-boxes Almost perfect nonlinear (APN)Value set size
Contact author(s): ingo @ czerwinski eu
History: 2021-05-05: revised; 2020-06-14: received; See all versions
Short URL: https://ia.cr/2020/705
License: CC BY

BibTeX

@misc{cryptoeprint:2020/705,
      author = {Ingo Czerwinski},
      title = {On the minimal value set size of {APN} functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/705},
      year = {2020},
      url = {https://eprint.iacr.org/2020/705}
}