Paper 2018/1217

Changing Points in APN Functions

Lilya Budaghyan, Claude Carlet, Tor Helleseth, and Nikolay Kaleyski

Abstract

We investigate the differential properties of a construction in which a given function $F : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}$ is modified at $K \in \mathbb{N}$ points in order to obtain a new function $G$. This is motivated by the question of determining the minimum Hamming distance between two APN functions and can be seen as a generalization of a previously studied construction in which a given function is modified at a single point. We derive necessary and sufficient conditions which the derivatives of $F$ must satisfy for $G$ to be APN, and use these conditions as the basis for an efficient filtering procedure for searching for APN functions whose value differs from that of a given APN function $F$ at a given set of points. We define a quantity $m_F$ related to $F$ counting the number of derivatives of a given type, and derive a lower bound on the distance between an APN function $F$ and its closest APN neighbor in terms of $m_F$. Furthermore, the value $m_F$ is shown to be invariant under CCZ-equivalence and easier to compute in the case of quadratic functions. We give a formula for $m_F$ in the case of $F(x) = x^3$ which allows us to express a lower bound on the distance between $F(x)$ and the closest APN function in terms of the dimension $n$ of the underlying field. We observe that this distance tends to infinity with $n$. We also compute $m_F$ and the distance to the closest APN function for a representative $F$ from each of the switching classes over $\mathbb{F}_{2^n}$ for $4 \le n \le 8$. For a given function $F$ and value $v$, we describe an efficient method for finding all sets of points $\{ u_1, u_2, \dots, u_K \}$ such that setting $G(u_i) = F(u_i) + v$ and $G(x) = F(x)$ for $x \ne u_i$ is APN.

Note: It was pointed out that the abstract in the submission form contained some erroneously contained some Latex commands which should not have been there. These have been removed, with the rest of the submission being left unchanged. As before, we point out that the contents of the paper was presented at BFA 2018 (the Workshop on Boolean Functions and Their Applications) in Norway, and that only a presentation and an abstract were presented at the conference, with the actual paper not having been published anywhere else.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Boolean FunctionsAlmost Perfect NonlinearAPNHamming distance
Contact author(s)
nikolay kaleyski @ uib no
History
2018-12-30: received
Short URL
https://ia.cr/2018/1217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1217,
      author = {Lilya Budaghyan and Claude Carlet and Tor Helleseth and Nikolay Kaleyski},
      title = {Changing Points in APN Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1217},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1217}},
      url = {https://eprint.iacr.org/2018/1217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.