Paper 2022/666

Deciding and reconstructing linear equivalence of uniformly distributed functions

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

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
CCZ-equivalence EA-equivalence linear equivalence invariant APN planar
Contact author(s)
Ivana Ivkovic @ student uib no
nikolay kaleyski @ gmail com
History
2022-05-31: approved
2022-05-28: received
See all versions
Short URL
https://ia.cr/2022/666
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/666,
      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},
      url = {https://eprint.iacr.org/2022/666}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.