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)

• 배경: 유한체 (Finite Fields) 위의 순열 다항식 (Permutation Polynomials, PP) 은 암호학 (블록 암호, 공개키 암호), 코딩 이론 등 다양한 분야에서 핵심적인 역할을 합니다. 특히 AES(Advanced Encryption Standard) 와 같은 블록 암호 시스템에서는 순열 다항식과 그 역함수 (Compositional Inverse) 가 모두 필수적입니다.
• 문제: 순열 다항식 $f(x)$가 주어졌을 때, $f(g(x)) = g(f(x)) = x$를 만족하는 다항식 $g(x)$를 명시적으로 (explicitly) 구하는 것은 이론적으로는 가능하지만 (라그랑주 보간법 등), 계산 복잡도가 매우 높고 대수적 구조에 대한 통찰을 제공하지 못합니다.
• 구체적 목표: 최근 Jiang et al. [21] 이 유한체 $\mathbb{F}_{q^2}$ ($q=2^m$) 위에서 $x + \gamma \text{Tr}_{q^2}^q(h(x))$ 형태의 6 가지 새로운 순열 다항식 클래스를 제안했습니다. 본 논문은 이 6 가지 클래스에 대한 합성 역함수 (Compositional Inverse) 를 명시적인 다항식 형태로 도출하는 것을 목표로 합니다.

2. 방법론 (Methodology)

논문은 다음과 같은 체계적인 수학적 기법을 사용하여 역함수를 구했습니다.

1. 보조 보조정리 (Auxiliary Lemmas) 활용:

   • 선형화된 다항식 (Linearized Polynomial) 성질: $\text{Tr}_{q^2}^q(\alpha x) = \alpha x + \alpha^q x^q$ 형태의 선형 사상을 활용합니다.
   • 기저 (Basis) 활용: $\mathbb{F}_{q^2}$를 $\mathbb{F}_q$ 위의 벡터 공간으로 간주하여 $\{1, \alpha\}$를 기저로 사용합니다.
   • 행렬 연산: 역함수를 구하는 과정에서 발생하는 연립방정식을 행렬 형태로 표현하고, 기본 행 연산 (Elementary Row Operations) 을 통해 변수를 소거하여 해를 구합니다.
   • 특수 다항식의 역함수: $m$이 홀수일 때 $x^3$이 $\mathbb{F}_{2^m}$ 위에서 순열 다항식이 되며, 그 역함수가 $x^t$ ($3t \equiv 1 \pmod{2^m-1}$) 임을 이용합니다.

2. 변환 기법 (Transformation Method):

   • 주어진 순열 다항식 $f(x)$에 대해 보조함수 $T(x)$ (또는 $U(x)$) 를 도입합니다.
   • $f(T(x))$를 계산하여 $T(y)$와 비교함으로써 $x$와 $y$ 사이의 관계를 유도합니다.
   • 이를 통해 $T^{-1} \circ f^{-1} \circ T$의 형태를 먼저 구한 후, 다시 $T$를 합성하여 최종 역함수 $f^{-1}(x)$를 얻습니다.

3. 주요 결과 (Key Results)

저자들은 Jiang et al. [21] 에서 제안한 6 가지 클래스에 대해 다음과 같은 명시적인 역함수를 도출했습니다. 여기서 $q=2^m$입니다.

• Theorem 3.1 ($f_1$):

  • $f_1(x) = x + \gamma \text{Tr}_{q^2}^q(x^3 + x^{q+2})$
  • 조건: $\gamma \in \mathbb{F}_q$
  • 역함수: $f_1^{-1}(x) = x + \gamma (\text{Tr}_{q^2}^q(x))^3$

• Theorem 3.2 ($f_2$):

  • $f_2(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^2 + x^3 + x^{q+2})$
  • 조건: $\gamma \in \mathbb{F}_q$
  • 역함수: $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$

• Theorem 3.3 ($f_3$):

  • $f_3(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^3 + x^{q+2})$
  • 조건: (a) $\gamma \in \mathbb{F}_q$ 또는 (b) $m$이 홀수이고 $\text{Tr}_{q^2}^q(\gamma + \gamma^2) = 0$ (즉, $\text{Tr}(\gamma)=1$)
  • 역함수:
    • $\gamma \in \mathbb{F}_q$인 경우: $x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^3$
    • $\text{Tr}(\gamma)=1$인 경우: $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma (\text{Tr}_{q^2}^q(x))^t$ ($3t \equiv 1 \pmod{2^m-1}$)

• Theorem 3.4 ($f_4$):

  • $f_4(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^3 + x^{q+2})$
  • 조건: 위 $f_3$와 동일
  • 역함수:
    • $\gamma \in \mathbb{F}_q$인 경우: $x + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$
    • $\text{Tr}(\gamma)=1$인 경우: $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [(\text{Tr}_{q^2}^q(x) + 1)^t + 1]$

• Theorem 3.5 ($f_5$) 및 Theorem 3.6 ($f_6$):

  • $m$이 홀수이고 $\gamma \in \mathbb{F}_{2^2} \setminus \{1\}$인 경우의 역함수를 도출했습니다.
  • 이 경우 $\gamma^2 + \gamma + 1 = 0$을 만족하며, 역함수 표현식에 $t$ ($3t \equiv 1 \pmod{2^m-1}$) 가 포함된 복잡한 다항식 형태가 나옵니다.
  • 특히 $f_6(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^{q+2})$의 역함수는 $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [\text{Tr}_{q^2}^q((1+\gamma)x) + \{\text{Tr}_{q^2}^q(x) + (\text{Tr}_{q^2}^q((1+\gamma)x))^3\}^t]$ 형태로 주어집니다.

4. 의의 및 기여 (Significance)

• 계산 효율성: 기존에 존재하던 역함수 계산법 (라그랑주 보간 등) 은 모든 항을 포함하여 계산량이 $O(q)$에 비례하여 매우 큽니다. 본 논문은 역함수를 간단한 트레이스 (Trace) 함수와 멱함수의 합성 형태로 명시적으로 제시함으로써, 암호 시스템 구현 시 역변환 연산의 계산 복잡도를 획기적으로 낮췄습니다.
• 암호학적 응용: AES 와 같은 블록 암호의 S-box 설계나 공개키 암호 시스템에서 순열 다항식과 그 역함수의 효율적인 구현은 보안성과 성능을 동시에 확보하는 데 필수적입니다. 본 연구는 이차 특성 (Even characteristic) 유한체에서 이러한 연산을 가능하게 하는 구체적인 수학적 도구를 제공합니다.
• 이론적 확장: Jiang et al. 의 기존 결과를 바탕으로, 다양한 조건 ($\gamma$의 위치, $m$의 홀짝성) 하에서 역함수의 구조를 체계적으로 분류하고 증명함으로써, 순열 다항식 이론의 지평을 넓혔습니다.

5. 결론

본 논문은 이차 특성 유한체 $\mathbb{F}_{q^2}$ 위에서 정의된 6 가지 특정 형태의 순열 다항식들에 대해, 명시적이고 계산 효율적인 합성 역함수를 성공적으로 도출했습니다. 이를 통해 암호학 및 코딩 이론 분야에서 이러한 다항식들의 실용적 적용 가능성을 높였으며, 향후 유사한 형태의 다항식 역함수 연구에 대한 중요한 기초 자료로 작용할 것으로 기대됩니다.