Vectorial Bent Functions: Deciphering the Geometry of Trace Mappings

TL;DR

This research establishes the necessary and sufficient conditions for a specific class of multiple-term trace functions to achieve vectorial bentness. By analyzing the evaluation of these functions on the cyclic group of $(2^k+1)$-th primitive roots of unity ($U$), the authors transition from abstract Walsh spectra to concrete algebraic properties involving symmetric polynomials and image distributions.

Problem & Motivation

In symmetric cryptography, bent functions are the gold standard for nonlinearity. However, moving from a single Boolean output to a vectorial output (multiple bits) while maintaining the "flat" Walsh spectrum is mathematically non-trivial.

Prior work often focused on "linear" Niho exponents where the exponents behave predictably within subfields. The authors of this paper aim to break this limitation by exploring nonlinear Niho exponents and multiple trace terms, seeking a definitive answer to the question: When does a complex trace sum result in a perfectly nonlinear mapping?

Methodology: The Three Pillars of Bentness

The core contribution is Theorem 2, which provides three equivalent identities for a function $F(x)$ to be vectorial bent. The most intuitive "physical" insight among these is the Image Distribution Condition.

1. The Image Distribution (Intuition)

The paper proves that $F$ is vectorial bent if and only if, when evaluated over the group $U$ (roots of unity), it hits every non-zero element of the subfield $GF(2^k)$ exactly once, and hits zero exactly twice.

2. The Symmetric Polynomial Connection

Using Newton's identities, the authors connect the sum of powers of function values ($s_{\ell }$) to elementary symmetric polynomials (${\sigma }_e$).

This algebraic bridge allows them to state that $F$ is vectorial bent if and only if nearly all symmetric polynomials ${\sigma }_e$ vanish, except for a specific index.

Key Results and Structural Proofs

The Binomial Case

For binomial trace functions $F(x)=T{r}_k^n(x+\gamma z{x}^{r(2^k-1)})$, the authors derive strict constraints:

• The Exponent Constraint: $r$ must be odd.
• The r=3 rule: If $r$ divides $2^k+1$, then $r$ must be 3 for the function to even stand a chance of being vectorial bent.

The Monomial "Never-Bent" Proof

A significant result is the proof that monomial trace functions of Dillon's type—functions previously thought to be strong candidates—can never be vectorial bent of maximum dimension $k$.

Note: The paper primarily utilizes mathematical proofs; the figure above would represent the mapping distribution of F from the cyclic group U to the subfield K.

Experiments: Validation through Simulation

The authors validated their theoretical constraints using computer simulations across various field sizes ($n=6,8,10$). For instance:

• Success: For $n=6$, $T{r}_3^6(x^7+{\alpha }^{21}{x}^{21})$ was confirmed as vectorial bent.
• Failure: For $n=10$, they proved no function of the form $T{r}_5^{10}(x^{31}+\gamma x^{3\cdot 31})$ can be vectorial bent, confirming their "Lemma 4" exclusion criteria.

Critical Analysis & Conclusion

Takeaway

The research successfully shifts the burden of proving bentness from the Walsh-Hadamard Transform (which is computationally expensive to check for all $\lambda$) to the study of Symmetric Polynomials and Newton Sums.

Limitations

The primary bottleneck remains the complexity of calculating higher-order symmetric polynomials. While the paper provides a clear path for binomials, the "combinatorial explosion" makes analyzing functions with more than two trace terms significantly more difficult.

Future Outlook

This work opens the door to automating the search for optimal cryptographic S-boxes by targeting the specific coefficient constraints ($z$ and $\gamma$) identified here. The proposed Conjecture 1 suggests a structural impossibility for certain field dimensions ($n\equiv 0(\mathrm{mod}4)$), which, if proven, would significantly simplify the search space for future cryptographers.