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^{n1}\). Sharp bounds for the cases \(n = 3\) and \(n = 5\) are explicitly given.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 Boolean functionsCryptographic SboxesAlmost perfect nonlinear (APN)Value set size
 Contact author(s)
 ingo @ czerwinski eu
 History
 20210505: revised
 20200614: 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} }