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 metadatas

https://hal.inria.fr/hal-01953353
Contributor : Léo Perrin <>
Submitted on : Wednesday, December 12, 2018 - 7:22:27 PM
Last modification on : Friday, December 28, 2018 - 2:40:59 PM
Long-term archiving on: Wednesday, March 13, 2019 - 4:01:25 PM

File

2018-713.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

123

Files downloads

231