Algorithms for Computing Affine Equivalence and Self-Equivalence Groups

Joakim Sunde

Paper 2026/2144

Algorithms for Computing Affine Equivalence and Self-Equivalence Groups

Joakim Sunde

Abstract

We study affine and linear equivalence of functions $F,G:\mathbb{F}_q^n\to\mathbb{F}_q^m$. We present practical equivalence algorithms that handle arbitrary functions (any algebraic degree, permutations and non-permutations) and are particularly effective on structured instances with nontrivial self-equivalences, covering most cryptographically relevant cases. We also give a dedicated algorithm for computing generators for the group of self-equivalences $(A_1,A_2)$ satisfying $A_2\circ F = F\circ A_1$, for which no comparably efficient general method was previously available.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Contact author(s): joakim sunde @ uib no
History: 2026-09-22: revised; 2026-09-22: received; See all versions
Short URL: https://ia.cr/2026/2144
License: CC BY

BibTeX

@misc{cryptoeprint:2026/2144,
      author = {Joakim Sunde},
      title = {Algorithms for Computing Affine Equivalence and Self-Equivalence Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2144},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2144}
}