Algebraic properties of the maps .

Area of Science:

• Cryptography
• Abstract Algebra
• Number Theory

Background:

• The Boolean map $x \mapsto x^{2^n-2}$ is a core component in several modern cryptographic permutations.
• These permutations include Keccak-f (SHA-3), ASCON (NIST Lightweight competition winner), Xoodoo, Rasta, and Subterranean.
• Understanding the algebraic properties of this map is crucial for cryptanalysis and the design of secure cryptographic systems.

Purpose of the Study:

• To investigate the algebraic characteristics of the Boolean map $x \mapsto x^{2^n-2}$ over finite fields.
• To determine conditions under which this map behaves as a power function and analyze its polynomial representations.
• To examine the properties of the inverse map and its behavior on field extensions.

Main Methods:

• Representing the Boolean map as a univariate polynomial over finite fields.
• Analyzing the conditions for the map to be a power function using vectorial isomorphism.
• Computing bounds on polynomial sparsity, degree, and the number of univariate representations.
• Calculating the number of monomials in the inverse map's polynomial representation.
• Investigating the map's behavior as a polynomial map on field extensions of $\mathbb{F}_{2^n}$.

Main Results:

• The Boolean map $x \mapsto x^{2^n-2}$ is a power function if and only if $n=1$.
• Bounds on the sparsity, degree, and number of univariate representations were computed.
• The number of monomials of a given degree in the inverse map coincides with binomial coefficients.
• The map $x \mapsto x^{2^n-2}$ does not yield a bijection on field extensions of $\mathbb{F}_{2^n}$ when the extension degree is divisible by 2 or 3.

Conclusions:

• The study provides a comprehensive algebraic analysis of a key component in modern symmetric-key cryptography.
• The findings offer insights into the structure and limitations of the Boolean map and its inverse.
• A conjecture is proposed that the rule $x \mapsto x^{2^n-2}$ does not define a bijection on any extension field of $\mathbb{F}_{2^n}$.