Inverses of six classes of permutation polynomials of the form $x+\gamma\operatorname{Tr}_q^{q^2}(h(x))$ over finite fields of even characteristic

1. Problem Statement

The paper addresses the problem of finding explicit compositional inverses for specific classes of Permutation Polynomials (PPs) over finite fields of even characteristic ($\mathbb{F}_{q^2}$ where $q=2^m$).

• Context: While the existence of an inverse for a permutation polynomial is guaranteed by its bijective nature, determining its explicit algebraic form is a notoriously difficult problem. Standard methods like Lagrange interpolation yield polynomials with too many terms to be computationally useful or structurally insightful.
• Target Class: The authors focus on polynomials of the form:
  $$f(x) = x + \gamma \text{Tr}_{q^2}^q(h(x))$$
  where $\text{Tr}_{q^2}^q$ is the trace function from $\mathbb{F}_{q^2}$ to $\mathbb{F}_q$, $\gamma \in \mathbb{F}_{q^2}$, and $h(x)$ is a specific polynomial.
• Specific Goal: To derive closed-form expressions for the compositional inverses of six specific classes of such polynomials recently identified by Jiang et al. [21] as permutation polynomials.

2. Methodology

The authors employ a linearized polynomial transformation method combined with matrix algebra over finite fields. The core strategy involves the following steps:

1. Auxiliary Transformation: They introduce a linearized polynomial $T(x)$ (or $U(x)$) defined as:
   $$T(x) = \text{Tr}_{q^2}^q(\beta x) + \alpha \text{Tr}_{q^2}^q(\delta x)$$
   where $\alpha \in \mathbb{F}_{q^2} \setminus \mathbb{F}_q$ with $\text{Tr}_{q^2}^q(\alpha)=1$, and $\beta, \delta$ are chosen such that they are linearly independent over $\mathbb{F}_q$.
2. Basis Decomposition: Since $\{1, \alpha\}$ forms a basis for $\mathbb{F}_{q^2}$ over $\mathbb{F}_q$, any element $y \in \mathbb{F}_{q^2}$ can be uniquely represented. The authors analyze the composition $f(T(x))$.
3. System of Equations: By equating $f(T(x)) = T(y)$, they decompose the problem into a system of linear equations involving the trace terms. This system is represented in matrix form:
   $$\begin{pmatrix} \beta & \beta^q \\ \delta & \delta^q \end{pmatrix} \begin{pmatrix} x \\ x^q \end{pmatrix} = \begin{pmatrix} \text{RHS}_1 \\ \text{RHS}_2 \end{pmatrix}$$
4. Matrix Inversion: Using elementary row operations, they invert the coefficient matrix (noting that the determinant $\beta\delta^q + \delta\beta^q \neq 0$ under their conditions) to solve for $x$ in terms of $y$.
5. Substitution and Simplification: They substitute $y = T^{-1}(x)$ back into the solution and utilize properties of the trace function and specific lemmas (e.g., Lemma 2.1 regarding the inverse of $x^3$ in odd characteristic extensions) to simplify the expression into a closed-form polynomial.

3. Key Contributions and Results

The paper provides explicit compositional inverses for six classes of PPs defined in Theorems 1.1 through 1.6. The results are categorized by the conditions on the parameter $\gamma$ and the parity of $m$.

Class 1: $f_1(x) = x + \gamma \text{Tr}_{q^2}^q(x^3 + x^{q+2})$

• Condition: $\gamma \in \mathbb{F}_q$.
• Inverse: $f_1^{-1}(x) = x + \gamma (\text{Tr}_{q^2}^q(x))^3$.

Class 2: $f_2(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^2 + x^3 + x^{q+2})$

• Condition: $\gamma \in \mathbb{F}_q$.
• Inverse: $f_2^{-1}(x) = x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$.

Class 3: $f_3(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^3 + x^{q+2})$

• Case A ($\gamma \in \mathbb{F}_q$):
  $f_3^{-1}(x) = x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^3$.
• Case B ($\text{Tr}_{q^2}^q(\gamma)=1$, $m$ is odd):
  $f_3^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma (\text{Tr}_{q^2}^q(x))^t$, where $3t \equiv 1 \pmod{2^m-1}$.

Class 4: $f_4(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^3 + x^{q+2})$

• Case A ($\gamma \in \mathbb{F}_q$):
  $f_4^{-1}(x) = x + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$.
• Case B ($\text{Tr}_{q^2}^q(\gamma)=1$, $m$ is odd):
  $f_4^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [(\text{Tr}_{q^2}^q(x) + 1)^t + 1]$.

Class 5: $f_5(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^{q+2})$

• Condition: $m$ is odd, $\gamma \in \mathbb{F}_{2^2} \setminus \{1\}$.
• Inverse: A complex expression involving the trace of $(1+\gamma)x$ and a power $t$ (where $3t \equiv 1 \pmod{2^m-1}$) of a polynomial combination of traces.
  $$f_5^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma \left[ \left( \text{Tr}_{q^2}^q(x) + (\text{Tr}_{q^2}^q((1+\gamma)x))^3 + (\text{Tr}_{q^2}^q((1+\gamma)x))^2 + \text{Tr}_{q^2}^q((1+\gamma)x) + 1 \right)^t + \text{Tr}_{q^2}^q((1+\gamma)x) + 1 \right]$$

Class 6: $f_6(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^{q+2})$

• Condition: $m$ is odd, $\gamma \in \mathbb{F}_{2^2} \setminus \{1\}$.
• Inverse:
  $$f_6^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma \left[ \text{Tr}_{q^2}^q((1+\gamma)x) + \left( \text{Tr}_{q^2}^q(x) + (\text{Tr}_{q^2}^q((1+\gamma)x))^3 \right)^t \right]$$

4. Significance and Applications

• Cryptographic Relevance: The paper highlights that PPs and their inverses are critical components in block ciphers (e.g., AES) and public key cryptography. In these systems, the S-box (Substitution box) often relies on permutation polynomials. Efficiently computing the inverse is necessary for decryption and key scheduling.
• Coding Theory: PPs are used in the construction of error-correcting codes. Knowing the inverse allows for efficient decoding algorithms.
• Theoretical Advancement: The paper resolves a specific open problem regarding the inverses of the classes identified by Jiang et al. [21]. By providing explicit, low-degree (relative to $q$) formulas, it avoids the computational explosion associated with generic interpolation methods.
• Methodological Utility: The technique of using a linearized auxiliary polynomial to decompose the problem into a solvable linear system over the base field $\mathbb{F}_q$ serves as a robust template for finding inverses of other "trace-form" permutation polynomials.

Conclusion

Singh et al. successfully extend the theory of permutation polynomials over finite fields of even characteristic. By leveraging the structure of the trace function and linear algebra over $\mathbb{F}_q$, they provide explicit, computationally efficient formulas for the compositional inverses of six distinct classes of PPs. These results directly support the implementation of secure cryptographic primitives and coding schemes that rely on these specific polynomial structures.