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\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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Boolean functionsCryptographic S-boxesAlmost 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},
note = {\url{https://eprint.iacr.org/2020/705}},
url = {https://eprint.iacr.org/2020/705}
}
