On the Distance Between APN Functions
Lilya Budaghyan, Claude Carlet, Tor Helleseth, Nikolay Kaleyski · IEEE Transactions on Information Theory · 2020
We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of G via the derivatives of F, and deduce an algorithm for searching for APN functions whose values differ from those of F only on a given set U ⊆ F2n. We introduce a value ΠFassociated with any F, which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function F and the closest APN function in terms of ΠF. We show how ΠFcan be computed efficiently for F quadratic. We compute ΠFfor all known APN functions over F2n. up to n ≤ 8. his is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function F (x) = x3, and observe that it tends to infinity with n. Finally, we describe how to efficiently find all sets U such that, taking G(x) = F (x) + v for x ∈ U and G(x) = F (x) for x ∉ U,G(x) is APN.