Welcome to the resource topic for 2022/666
Title:
Deciding and reconstructing linear equivalence of uniformly distributed functions
Authors: Ivana Ivkovic and Nikolay Kaleyski
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.
ePrint: https://eprint.iacr.org/2022/666
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .