Skip to Main content Skip to Navigation
Journal articles

On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting

Abstract : Two vectorial Boolean functions are "CCZ-equivalent" if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a CCZ-equivalence class into its Extended-Affine (EA) equivalence classes; EA-equivalence being a simple particular case of CCZ-equivalence. In this paper, we characterize CCZ-equivalence as a property of the zeroes in the Walsh spectrum of a function $F:\mathbb{F}_2^n \to \mathbb{F}_2^m$ or, equivalently, of the zeroes in its Difference Distribution Table. We use this framework to show how to efficiently upper bound the number of distinct EA-equivalence classes in a given CCZ-equivalence class. More importantly, we prove that it is possible to go from a specific member of any EA-equivalence class to a specific member of another EA-equivalence class in the same CCZ-equivalence class using an operation called twisting; so that CCZ-equivalence can be reduced to the association of EA-equivalence and twisting. Twisting a function is a simple process and its possibility is equivalent to the existence of a particular decomposition of the function considered. Using this knowledge, we revisit several results from the literature on CCZ-equivalence and show how they can be interpreted in light of our new framework. Our results rely on a new concept, the "thickness" of a space (or linear permutation), which can be of independent interest.
Complete list of metadata
Contributor : Léo Perrin Connect in order to contact the contributor
Submitted on : Wednesday, December 12, 2018 - 7:22:27 PM
Last modification on : Wednesday, February 17, 2021 - 10:26:08 AM
Long-term archiving on: : Wednesday, March 13, 2019 - 4:01:25 PM


Files produced by the author(s)




Anne Canteaut, Léo Perrin. On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting. Finite Fields and Their Applications, Elsevier, 2019, 56, pp.209-246. ⟨10.1016/j.ffa.2018.11.008⟩. ⟨hal-01953353⟩



Record views


Files downloads