Triprojective almost perfect nonlinear permutations and functions

기술적 요약: 삼사영 거의 완벽한 비선형 치환 및 함수

문제 제기
본 논문은 짝수 차원의 유한 벡터 공간 위에서의 거의 완벽한 비선형 (APN) 치환의 존재성과 구성을 다룹니다. 차분 암호분석의 맥락에서, APN 함수 (차분 균일도 $\Delta_F = 2$를 갖는 함수) 는 치환 - 치환 네트워크에서 안전한 S-Box 를 설계하는 데 필수적입니다. APN 함수는 홀수 차원에서는 존재함이 알려져 있으나, 짝수 차원 $n > 6$에 대한 APN 치환 (전단사 함수) 의 존재 여부는 여전히 주요한 미해결 문제입니다. 구체적으로, 저자들은 $n = 3m$ (여기서 $m$은 홀수) 차원에서 그러한 함수들의 대규모 군을 구성하고, 그 등가류와 이미지 집합의 크기 등을 포함한 특성들을 규명하는 데 초점을 맞춥니다.

방법론
저자들은 "삼사영 (triprojective)" 및 "준 2 차 (semi-quadratic)" 사상에 기반한 구조적 접근법을 사용합니다. 방법론은 다음과 같은 단계를 거칩니다:

1. 사영 구조: 저자들은 $\mathbb{F}_q^3$ (여기서 $q=2^m$) 위의 함수 클래스 $F \in SQH(3, q)$ (준 2 차 동차) 를 정의합니다. 이러한 함수들은 특정 동차 성질을 만족하는 준 2 차 형식에 의해 유도되며, 이를 통해 사영 공간 $\mathbb{P}^2(\mathbb{F}_q)$ 위에서 잘 정의된 사상을 유도할 수 있습니다.
2. 전단사 기준: 이전 연구 (정리 1.2) 에 의존하여, 논문은 특정 단변수 다항식 $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$에 대한 조건을 활용하여 사영 공간 위의 유도된 사상이 전단사임을 보장합니다.
3. 차분 균일도 분석:
   • 경우 $m/d$가 짝수인 경우: 저자들은 도함수 사상이 선형인 부분체 (함수의 "핵") 개념을 활용하여 차분 균일도가 $2d$임을 보여줍니다. 여기서 $d = \gcd(k, m)$입니다.
   • 경우 $m/d$가 홀수인 경우: 저자들은 꼬인 다항식 환 (Ore rings) $\mathbb{F}_q[t; \sigma]$ 이론에서 도구를 도입합니다. 그들은 다항식 $P(X)$의 근과 꼬인 환 내의 선형 우약수 (right divisor) 존재성 사이의 연결고리를 확립합니다. 체를 확장하고 다항식의 최소 공통 좌배수 (lclm) 를 분석함으로써, 더 복잡한 경우에서도 차분 균일도가 $2d$로 유지됨을 증명합니다.
4. 등가성 및 분류: 논문은 새로운 군을 기존 삼변수 APN 함수 (특히 Li-Kaleyski 와 Bartoli-Stanica 의 함수) 와 선형 등가성을 통해 비교합니다. 또한, 선형 자동형 군 ($Aut_L(F)$) 을 분석하고 일반 선형 군 내에서 켤레 (conjugate) 가 될 수 없음을 보여 Gold APN 함수 ($x^{2^i+1}$) 와는 등가하지 않음을 증명합니다.

주요 기여 및 결과

• APN 치환의 구성: 논문은 $m$이 홀수인 $n=3m$ 차원의 유한 벡터 공간에 대한 APN 치환의 대규모 군을 제시합니다. 함수는 다음과 같이 정의됩니다:
  $$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$$
  여기서 $\sigma = 2^k$, $a, b, c \in \mathbb{F}_q$, 그리고 $a \neq 0$입니다.
• 차분 균일도: 저자들은 다항식 방정식 $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$이 $\mathbb{F}_q$에서 해를 갖지 않는다면, $F$의 차분 균일도가 $2d$ (여기서 $d = \gcd(k, m)$) 임을 증명합니다. 결과적으로, $d=1$이고 $m$이 홀수일 때, $F$는 APN 치환이 됩니다.
• 이미지 집합 크기: 논문은 이러한 함수들의 이미지 집합 크기를 규명합니다. $m/d$가 짝수이면, 함수는 $\mathbb{F}_q^3 \setminus \{0\}$ 위에서 $(2d+1)$-to-one 입니다. $m/d$가 홀수이면, 함수는 $\mathbb{F}_q^3$ 위에서 전단사입니다.
• 기존 군의 통합: 저자들은 최근 발견된 여러 삼변수 APN 함수 군 (Li-Kaleyski 와 Bartoli-Stanica) 이 제안된 군의 특정 사례 (특정 매개변수 $a, b, c$를 설정하여 얻은) 와 선형 등가임을 보여줍니다. 이는 이전 증명에서 사용된 복잡한 경우 구분과 컴퓨터 보조 결과 계산 없이, 이러한 구성들을 이해하기 위한 통합적이고 기초적인 설명을 제공합니다.
• Gold 함수와의 비등가성: 논문은 $m > 2$이고 $m \neq 6$인 경우, 구성된 APN 함수들이 Gold APN 함수와 CCZ-비등가임을 증명합니다. 이는 그들의 선형 자동형 군이 $GL(3m, 2)$ 내에서 켤레가 아님을 보여줌으로써 확립됩니다.

의의 및 주장
본 논문은 3 으로 나누어지는 모든 홀수 차원에서 "대규모 군"의 APN 치환을 제공한다고 주장하며, 짝수 차원에 대한 APN 전단사 함수의 미해결 문제를 다루고 있습니다. 그 의의는 다음과 같습니다:

1. 일반성: 이 구성은 다사영 사상의 클래스 내에서 증명 가능한 지수적으로 많은 쌍별 비등가 APN 함수를 산출합니다.
2. 단순화: 증명들은 이전 작업들에 비해 "컴퓨터를 사용하지 않고, 훨씬 짧으며, 순수하게 기초적인" 것으로 묘사되며, 다양한 삼변수 APN 함수를 이해하기 위한 통합된 프레임워크를 제공합니다.
3. 새로운 예시: 이 군은 알려진 APN 함수 (Gold 함수 포함) 와 비등가인 예시들을 포함함이 밝혀져, 암호학적 원시들의 알려진 지평을 확장합니다.

저자들은 $m/d$가 짝수인 경우의 Walsh 스펙트럼은 알려져 있으나, APN 치환 ($m$이 홀수인 경우) 에 대한 Walsh 스펙트럼을 결정하는 것은 여전히 미해결 문제라고 지적합니다. 또한, 사영 전단사로 이어지는 준 2 차 동차 함수들의 분류를 향후 연구의 자연스러운 방향성으로 제시합니다.