Abstract:We prove that asymptotically almost all vectorial functions over finite fields have trivial extended-affine stabilizers. As a consequence, the number of EA-equivalence classes is asymptotically equal to the naive estimate, namely the total number of functions divided by the size of the EA-group, with vanishing relative error. Furthermore, we derive upper bounds on collision probabilities for both extended-affine and CCZ equivalences. For EA-equivalence, we leverage the trivial-stabilizer result to establish a matching lower bound, yielding a tight asymptotic formula that shows two independently sampled functions are EA-equivalent with super-exponentially small probability. The results validate random sampling strategies for cryptographic primitive design and show that functions with nontrivial EA-stabilizers form an exponentially rare subset.
| Comments: | minor revision; changed Introduction section |
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2602.06668 [math.CO] |
| (or arXiv:2602.06668v3 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2602.06668 arXiv-issued DOI via DataCite |
From: Keita Ishizuka [view email]
[v1]
Fri, 6 Feb 2026 12:53:38 UTC (10 KB)
[v2]
Tue, 10 Mar 2026 14:27:13 UTC (11 KB)
[v3]
Fri, 22 May 2026 00:37:25 UTC (11 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。