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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.