Paper 2022/666

Deciding and reconstructing linear equivalence of uniformly distributed functions

Ivana Ivkovic, University of Bergen
Nikolay Kaleyski, University of Bergen

We describe an efficient algorithm for testing and recovering linear equivalence between a pair of $k$-to-$1$ discrete functions with a specific structure. In particular, for $k = 3$ this applies to many APN functions over fields of even characteristic, and for $k = 2$ this applies to all known planar functions over fields of odd characteristic. Our approach is significantly faster than all known methods for testing equivalence, and allows linear equivalence to be tested in practice for dimensions much higher than what has been possible before (for instance, we can efficiently test equivalence for $n = 12$ or $n = 14$ in the case of 3-to-1 APN functions over $\mathbb{F}_{2^n}$, and for $n = 8$ or $n = 9$ in the case of 2-to-1 planar functions over $\mathbb{F}_{3^n}$ within a few minutes even in the worst case). We also develop supplementary algorithms allowing our approach to be extended to the more general case of EA-equivalence. Classifying 3-to-1 APN functions over $\mathbb{F}_{2^n}$ for dimensions as high as $n = 14$ up to EA-equivalence can be performed in a matter of minutes using the developed framework.

Available format(s)
Publication info
CCZ-equivalence EA-equivalence linear equivalence invariant APN planar
Contact author(s)
Ivana Ivkovic @ student uib no
nikolay kaleyski @ gmail com
2022-05-31: approved
2022-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivana Ivkovic and Nikolay Kaleyski},
      title = {Deciding and reconstructing linear equivalence of uniformly distributed functions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/666},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.