[Resource Topic] 2018/1217: Changing Points in APN Functions

Welcome to the resource topic for 2018/1217

Title:
Changing Points in APN Functions

Authors: Lilya Budaghyan, Claude Carlet, Tor Helleseth, 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.