Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
Provides theoretical justification for random sampling strategies in cryptographic primitive design by showing that functions with nontrivial stabilizers are exponentially rare.
Proved that almost all vectorial functions over finite fields have trivial extended-affine stabilizers, leading to the number of EA-equivalence classes matching the naive estimate with vanishing relative error. Also established tight asymptotic bounds showing two random functions are EA-equivalent with super-exponentially small probability.
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.