Paper 2022/666
Deciding and reconstructing linear equivalence of uniformly distributed functions
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)
- 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
-
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} }