Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers

This paper proves that asymptotically almost all vectorial functions over finite fields possess trivial extended-affine stabilizers, implying that the number of equivalence classes matches the naive estimate and that random sampling is a highly effective strategy for cryptographic primitive design due to the exponential rarity of functions with nontrivial stabilizers.

The Gist

Imagine you are a master chef trying to invent a new, unique spice blend for a secret recipe book. You have a massive pantry with $2^{64}$ (or even more) possible combinations of spices. Your goal is to find the "perfect" blend that makes a dish taste amazing (in cryptography, this means a function that is hard to crack).

However, there's a catch: some spice blends are just the same recipe, but written in a different language or with the ingredients listed in a different order. In the world of math and cryptography, these "same-but-different" recipes are called EA-equivalent.

This paper by Keita Ishizuka answers two big questions about searching for these unique recipes:

1. How many truly unique recipes are there?
2. If I randomly pick two recipes from the pantry, what are the odds they are actually the same recipe in disguise?

Here is the breakdown of the paper's findings using simple analogies.

The Core Concept: The "Mirror" Effect

In this mathematical world, a function (a recipe) has a Stabilizer. Think of a stabilizer as a "magic mirror."

• If you look in the mirror and see a slightly different version of yourself (like wearing a hat or standing on one leg), but you are still you, that's a non-trivial stabilizer.
• If the mirror shows only you, exactly as you are, with no changes possible, that's a trivial stabilizer.

Most people assume that complex recipes might have many "magic mirrors" (symmetries) that make them look the same in different ways. If a recipe has many mirrors, it means there are many ways to write it down that are actually the same thing. This makes counting unique recipes very hard.

The Big Discovery: "Almost Everyone is Unique"

The paper proves a surprising fact: Almost all random recipes have NO magic mirrors.

If you pick a function at random from the massive pantry of possibilities, it is overwhelmingly likely that it has zero symmetries. It is a "one-of-a-kind" item.

• The Analogy: Imagine a library with a billion books. You might think many books are just copies with different fonts or cover colors. This paper says: "No! If you pick a book at random, it is almost certainly a unique original. The chance of finding a book that is just a 'reformatted copy' of another is so small it's practically zero."

Why This Matters: Two Big Wins

1. Counting the Unique Items (The "Naive" Guess is Right)

Before this paper, mathematicians worried that counting unique cryptographic functions was hard because of all the "reformatted copies" (symmetries). They thought the real number of unique classes was much lower than a simple calculation would suggest.

The Paper's Verdict: You can just do the simple math!

• The Formula: Take the total number of functions and divide it by the size of the "group" (the number of ways you can shuffle the ingredients).
• The Result: Because almost every function has no symmetries (no mirrors), this simple division gives you the exact number of unique classes. The "error" in this guess is so tiny it vanishes as the numbers get bigger.

2. The Lottery of Random Sampling (No Need to Worry About Duplicates)

Cryptographers often use computers to randomly generate functions to find ones with special security properties (like being "Almost Perfect Nonlinear" or APN). A major fear was: "If I generate 1,000 random functions, will I accidentally generate the same one 500 times just because it looks different?"

The Paper's Verdict: No, you won't.

• The Odds: The chance that two randomly picked functions are actually the same (EA-equivalent) is super-exponentially small.
• The Analogy: It's like shuffling a deck of cards and asking, "What are the odds I pull the Ace of Spades twice in a row?" But make the deck the size of the universe. The odds are so low that you can safely generate millions of random functions without worrying about hitting the same "class" twice.

The "8-Bit" Reality Check

The paper does a specific calculation for 8-bit S-boxes (the standard size used in modern encryption like AES).

• It calculates that the probability of a random 8-bit function having a "mirror" (non-trivial stabilizer) is roughly 1 in $10^{110}$.
• To put that in perspective: There are only about $10^{80}$ atoms in the observable universe. You are more likely to find a specific atom in the entire universe than to find a random 8-bit function that isn't unique.

Conclusion: Why This is Good News

This paper gives cryptographers a huge green light.

• For Design: You don't need to worry about complex math to avoid duplicates when searching for new ciphers. Random sampling works perfectly.
• For Theory: It confirms that the "messy" part of the math (symmetries) is actually a tiny, rare exception. The "clean" part (everything is unique) is the rule.

In short: If you pick a cryptographic function at random, it is almost certainly a unique masterpiece, not a copycat.

Technical Summary

Here is a detailed technical summary of the paper "Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers" by Keita Ishizuka.

1. Problem Statement

The paper addresses two fundamental questions regarding Extended-Affine (EA) equivalence of vectorial functions over finite fields ($F_q^n \to F_q^m$), which are critical in symmetric cryptography (e.g., as S-boxes):

1. Classification: What is the asymptotic number of distinct EA-equivalence classes? Since EA-equivalent functions share cryptographic properties (differential uniformity, Walsh spectrum, algebraic degree), counting classes determines the diversity of available cryptographic primitives.
2. Random Sampling: Is random generation of functions effective for finding new cryptographic primitives? Specifically, does the risk of sampling two functions that are EA-equivalent (collisions) significantly limit the exploration of the search space?

Both questions depend on the structure of EA-stabilizers. The EA-stabilizer of a function $F$ is the set of affine permutation pairs $(A_{in}, A_{out})$ such that $A_{out} \circ F \circ A_{in} = F$. By the Orbit-Stabilizer theorem, the size of an equivalence class is inversely proportional to the size of its stabilizer. If stabilizers are non-trivial, the number of classes is smaller than the "naive" estimate (Total Functions / Group Size), and collision probabilities are higher.

2. Methodology

The author employs a probabilistic approach combined with group action theory and combinatorial analysis:

• Group Action Framework: The problem is modeled using the action of the EA-group $\Gamma = \text{AGL}(U) \times \text{AGL}(W)$ on the set of all functions $\mathcal{F}$.
• Fixed-Point Analysis: The core of the proof involves bounding the number of functions fixed by a non-trivial element $g \in \Gamma$ (denoted as $|\text{Fix}(g)|$).
  • The author decomposes the domain $U$ into orbits under the input affine permutation $\sigma$.
  • By iterating the fixed-point equation $Q F(\sigma(x)) + b = F(x)$, the author derives constraints on the values of $F$.
  • It is shown that for any non-trivial $g$, the number of fixed functions is bounded by $c \cdot q^{m q^n}$ where $c < 1$ is a constant independent of the dimension.
• Union Bound: Using the Union Bound, the probability that a random function has a non-trivial stabilizer is bounded by the sum of probabilities that it is fixed by any specific non-identity group element.
• Orbit-Stabilizer & Burnside's Lemma: These are used to relate the stabilizer size to the total count of equivalence classes and to derive collision probabilities.

3. Key Contributions

The paper makes three primary contributions:

1. Main Theorem (Trivial Stabilizers): It proves that for a uniformly random vectorial function, the probability of having a non-trivial EA-stabilizer decays super-exponentially as the dimension $n$ increases. Specifically, $P(\text{Stab}(F) \neq \{id\}) \leq q^{-\Omega(m q^n)}$.
2. Asymptotic Counting Formula: It establishes that the number of EA-equivalence classes is asymptotically equal to the naive estimate:
   $$|\mathcal{F}/\Gamma| \sim \frac{|\mathcal{F}|}{|\Gamma|}$$
   The relative error between the true count and this estimate vanishes as $n \to \infty$.
3. Tight Collision Bounds: It derives upper bounds for the probability that two independently sampled functions are EA-equivalent. Crucially, using the trivial-stabilizer result, the author proves this upper bound is asymptotically tight, showing the collision probability is super-exponentially small.

4. Key Results

• Triviality of Stabilizers: For dimensions relevant to modern cryptography (e.g., 8-bit S-boxes, $n=m=8$), the probability of a random function having a non-trivial EA-stabilizer is astronomically small (e.g., $\leq 2^{-368}$).
• Validation of Naive Estimates: The "naive" formula (Total Functions / Group Size) is not just an approximation but an asymptotically exact formula for the number of EA-classes because the "correction factor" (functions with non-trivial stabilizers) is exponentially negligible.
• Collision Probability: For two random functions $F, G$, the probability $P(F \sim_{EA} G)$ is approximately $|\Gamma|/|\mathcal{F}|$. In the binary case ($q=2$), this is $2^{-\Omega(2^n)}$.
• CCZ-Equivalence: While upper bounds for CCZ-equivalence collisions are provided, the paper notes that proving the triviality of CCZ-stabilizers remains an open problem due to the complexity of the graph-based action.

5. Significance and Implications

• Cryptographic Design: The results validate random sampling strategies for designing cryptographic primitives (like APN or Almost Bent functions). Researchers can generate random functions without fear of redundancy; the likelihood of generating two EA-equivalent functions is negligible.
• Structural Insight: The paper resolves a long-standing gap in understanding the "typical" behavior of vectorial functions. While specific classes of functions (like power functions) often have large stabilizers, the paper proves these are exponentially rare in the total function space.
• Theoretical Foundation: It unifies previous work on stabilizers (which focused on Boolean functions or simpler group actions) with the more complex vectorial EA-equivalence setting, providing a rigorous probabilistic proof for asymptotic orbit counts previously derived via complex algebraic methods (e.g., by Hou and Lu et al.).

In conclusion, the paper demonstrates that the space of vectorial functions is "asymptotically free" under EA-equivalence, meaning almost every function belongs to a unique orbit of maximal size, simplifying both the theoretical counting of classes and practical search algorithms.