Paper 2021/225

Recovering or Testing Extended-Affine Equivalence

Anne Canteaut, Alain Couvreur, and Léo Perrin


Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the tuple $(A,B,C)$ if it exists. In this paper, we present a new efficient algorithm that efficiently solves the EA-recovery problem for quadratic functions. Though its worst-case complexity is obtained when dealing with APN functions, it supersedes all previously known algorithms in terms of performance, even in this case. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. In order to tackle EA-testing efficiently, the best approach in practice relies on class invariants. We provide an overview of the literature on said invariants along with a new one based on the ortho-derivative which is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is both very fast to compute, and highly discriminating.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
SboxesequivalenceAPN functionsquadratic functionsortho-derivative
Contact author(s)
anne canteaut @ inria fr
leo perrin @ inria fr
alain couvreur @ inria fr
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Anne Canteaut and Alain Couvreur and Léo Perrin},
      title = {Recovering or Testing Extended-Affine Equivalence},
      howpublished = {Cryptology ePrint Archive, Paper 2021/225},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.