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 CCZequivalence 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)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Boolean FunctionsAlmost Perfect NonlinearAPNHamming distance
 Contact author(s)
 nikolay kaleyski @ uib no
 History
 20181230: received
 Short URL
 https://ia.cr/2018/1217
 License

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} }