Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$

이 논문은 유한체 $\mathbb{F}_{2^m}$ 위의 3 변수 다항식 클래스에 대한 **거의 완벽한 비선형성 (APN, Almost Perfect Nonlinear)**을 갖는 **치환 다항식 (Permutation Polynomials)**의 무한한 가족을 구성하고 분석하는 내용을 다룹니다. 특히, Li 와 Kaleyski (2024) 가 제안한 2 개의 희귀한 (sporadic) 2 차 APN 치환을 일반화하여, 스칼라 계수가 $\mathbb{F}_2$가 아닌 전체 $\mathbb{F}_{2^m}^*$에서 자유롭게 변할 수 있도록 확장한 것이 핵심입니다.

다음은 논문의 문제 제기, 방법론, 주요 기여, 결과 및 의의에 대한 상세한 기술적 요약입니다.

1. 문제 제기 (Problem Statement)

• 배경: 암호학 (특히 차분 암호분석) 과 부호 이론에서 APN 함수는 최적의 차분 균일성 (differential uniformity) 을 가지며, 이를 동시에 치환 (permutation) 으로 만드는 것은 이상적인 S-box 구성 요소입니다. 그러나 APN 치환을 구성하는 것은 매우 어렵고, 알려진 무한한 가족은 극히 드뭅니다.
• 기존 연구: Beierle 와 Leander (2021) 가 $\mathbb{F}_{2^9}$에서 두 개의 희귀한 2 차 APN 치환을 발견했습니다. Li 와 Kaleyski (2024) 는 이를 일반화하여 $\mathbb{F}_{2^{3m}}$ 위의 두 가지 무한한 APN 치환 가족 ($G_1, H_1$) 을 제시했으나, 이때 계수는 $\mathbb{F}_2$ (즉, 1) 로 고정되어 있었습니다.
• 연구 목표: Li-Kaleyski 가족의 스칼라 계수를 $\mathbb{F}_{2^m}^*$ 전체로 확장하여, 새로운 계수 $a$에 대해 APN 치환이 존재하는지, 그리고 이러한 함수들이 기존 가족과 동치 (equivalent) 인지 여부를 규명하는 것입니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 대수기하학적 및 대수적 도구를 활용했습니다:

1. 대수적 곡선과 다항식 분석:
   • 제안된 3 변수 함수 $G_a(x,y,z)$와 $H_a(x,y,z)$의 치환 (permutation) 성질과 APN 성질이 단일 변수 다항식 $Q_a(T) = T^{q^2+q+1} + aT + 1$의 근 (root) 존재 여부에 의해 결정됨을 증명했습니다.
   • 여기서 $q=2^i$, $\gcd(i, m)=1$, $m$은 홀수입니다.
2. Hasse-Weil 경계 (Hasse-Weil Bound):
   • "나쁜" 매개변수 $a$ (즉, $Q_a$가 근을 가지는 경우) 의 집합을 유리 함수 $g(u) = \frac{u^{d}+1}{u}$의 이미지로 표현했습니다.
   • 대수적 곡선 $\Gamma$의 절대 기약성 (absolute irreducibility) 을 증명하고 Hasse-Weil 정리를 적용하여, 좋은 매개변수 $a$의 하한 (lower bound) 을 유도했습니다.
3. 동치성 분석 (Equivalence Analysis):
   • 대각 동치 (Diagonal Equivalence): 두 함수가 대각 선형 변환을 통해 서로 변환 가능한지 분석했습니다.
   • CCZ 동치 (CCZ-equivalence): 2 차 APN 함수의 경우, CCZ 동치, EA 동치, EL 동치가 일치한다는 사실 (Shi et al., 2025 등) 을 활용하여, 대각 동치가 성립하지 않으면 CCZ 동치도 성립하지 않음을 보였습니다.
   • 단항식 제한 정리 (Monomial Restriction Theorem): 특정 조건 ($m>4, m \neq 6, 7 \nmid m$) 하에서 CCZ 동치 사상이 단항식 (coordinate permutation, diagonal scaling, Frobenius twist) 이어야 함을 이용하여 두 가족 간의 동치성을 배제했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. APN 치환의 특성화 (Characterization)

• 주요 정리 (Theorem 2.7): 함수 $G_a$가 치환일 필요충분조건은 다항식 $Q_a(T)$가 $\mathbb{F}_{2^m}$에서 근을 갖지 않는 것이며, 이는 $G_a$가 APN 인 것과 동치입니다.
• 동일한 조건: 두 번째 가족 $H_a$에 대해서도 유사한 다항식 조건이 성립하며, $G_a$와 $H_a$의 조건은 근-동치 (root-equivalent) 입니다. 즉, 동일한 매개변수 $a$가 두 가족 모두에서 APN 치환을 생성합니다.

B. 좋은 매개변수의 존재성 및 하한 (Existence and Lower Bound)

• 정량적 하한 (Theorem 2.12): $d = q^2+q+1$일 때, 좋은 매개변수 $a$의 개수는 다음과 같은 하한을 가집니다:
  $$|B_{m,q}| \geq 2^m + 1 - \frac{(d-1)(d-2)2^{m/2} - d}{d}$$
  이는 모든 홀수 $m$에 대해 APN 치환이 무한히 존재함을 보장합니다.
• 이진 경우 (Binary Case, $q=2$): $7 \nmid m$인 경우, $a=1$이 항상 좋은 매개변수임을 증명하여 Li-Kaleyski 가족을 회복했습니다. 또한 $a \neq 1$인 다른 좋은 매개변수들도 존재함을 보였습니다.

C. 새로운 가족의 동치성 부재 (Non-equivalence Results)

1. Li-Kaleyski 대표와의 비동치성 (Theorem 4.2):
   • $G_a$ (또는 $H_a$) 가 Li-Kaleyski 대표 $G_1$ (또는 $H_1$) 과 대각 동치일 필요충분조건은 $a^{q^2+q+1} = 1$입니다.
   • $m > 4, m \neq 6, 7 \nmid m$일 때, $a=1$이 아닌 모든 좋은 매개변수는 Li-Kaleyski 가족과 CCZ 비동치인 새로운 APN 치환을 제공합니다.
2. 두 가족 간의 비동치성 (Theorem 4.5):
   • 동일한 $q$에 대해, $G_a$ 가족의 어떤 원소도 $H_b$ 가족의 어떤 원소와도 CCZ 동치가 아님을 증명했습니다.
   • 이는 두 가족이 서로 다른 CCZ 동치 클래스에 속하는 완전히 새로운 무한한 APN 치환의 원천임을 의미합니다.

4. 의의 (Significance)

1. APN 치환의 무한한 가족 확장: 기존에 알려진 APN 치환의 수가 매우 제한적이라는 점을 고려할 때, 이 논문은 $\mathbb{F}_{2^{3m}}$ 위에서 두 개의 새로운 무한한 APN 치환 가족을 제시함으로써 해당 분야의 지평을 넓혔습니다.
2. 계수 확장 및 일반화: Li-Kaleyski의 결과를 $\mathbb{F}_2$ 계수에서 $\mathbb{F}_{2^m}$ 전체로 확장하여, 매개변수 공간이 훨씬 풍부해졌음을 보였습니다.
3. 동치성 분류의 명확화: 대수기하학적 도구를 활용하여 새로운 함수들이 기존에 알려진 함수들과 본질적으로 다르다는 것을 엄밀하게 증명했습니다. 이는 암호학적 S-box 설계 시 더 다양한 후보를 제공할 수 있음을 시사합니다.
4. 수학적 기법의 적용: APN 성질과 치환 성질을 단일 변수 다항식의 근 문제로 환원시키고, Hasse-Weil 정리를 적용하여 존재성을 증명하는 접근법은 향후 유사한 문제 해결에 중요한 방법론적 기여를 합니다.

5. 결론 및 향후 과제

이 논문은 3 변수 클래스에서 APN 치환의 존재성을 완전히 특성화하고, 그 수가 충분하며 기존 가족과 동치가 아님을 증명했습니다. 향후 과제로는 짝수 차원 ($m$이 짝수인 경우) 에 대한 확장, $n > 3$ 변수로 일반화, 그리고 $7|m$인 경우의 명시적인 좋은 매개변수 $a$의 대수적 특성화 등이 제시되었습니다.