On the Distance Between APN Functions

Abstract

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 ⊆ F 2n . We introduce a value Π F associated 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 Π F can be computed efficiently for F quadratic. We compute Π F for all known APN functions over F 2n . 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) = x 3 , 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.