Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic

"Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic" 논문에 대한 상세한 기술적 요약입니다.

1. 문제 제기

이 논문은 유한체 $\mathbb{F}_q$ (여기서 $q = p^n$ 는 홀수 소수 거듭제곱) 위에서 정의된 특정 함수 클래스의 암호학적 성질을 다룹니다. 초점은 다음과 같은 형태의 함수에 맞춰져 있습니다:
$$F_r(x) = x^r(1 + \chi(x)) = x^r + x^{r + \frac{q-1}{2}}$$
여기서 $\chi(x) = x^{\frac{q-1}{2}}$ 는 2 차 지수입니다.

이 연구는 이러한 함수에 대한 두 가지 중요한 보안 지표를 결정하는 것을 목표로 합니다:

1. 미분 균일성 ($\delta_F$): 미분 암호분석에 대한 저항성을 측정합니다. 함수가 $\delta_F = 2$ 일 때 *거의 완벽한 비선형 (APN)*이라고 합니다. 이러한 함수들은 많은 매개변수에서 엄격한 전역적 의미에서 APN 이 아니므로, 저자들은 이들이 **국소적 APN (Locally-APN)**인지, 즉 모든 $b \in \mathbb{F}_q \setminus \mathbb{F}_p$ 에 대해 $\delta_F(1, b) \le 2$ 를 만족하는지 조사합니다.
2. 부메랑 균일성 ($\beta_F$): 부메랑 공격에 대한 저항성을 측정합니다. 논문은 $\beta_F \le 2$ 인지를 규명하고, 완전한 부메랑 스펙트럼 (부메랑 연결 테이블의 해 개수 분포) 을 결정하고자 합니다.

구체적으로, 논문은 단항식 $x^r$ 이 낮은 미분 균일성 (종종 완벽한 비선형 또는 APN) 을 가지며 $\gcd(r, q-1) \mid 2$ 인 지수 $r$ 의 하위 클래스에 대해 이러한 성질이 성립하는지 조사합니다.

2. 방법론

저자들은 유한체 위의 대수적 정수론, 지수합 분석, 그리고 조합론적 계산을 결합하여 사용합니다.

• 해 집합의 분해: 저자들은 $x$ 와 $x+1$ 의 2 차 지수에 기반하여 $\mathbb{F}_q$ 를 분할합니다. $i, j \in \{0, 1\}$ 에 대해 $S_{ij} = \{x \in \mathbb{F}_q : \chi(x) = (-1)^i, \chi(x+1) = (-1)^j\}$ 집합을 정의합니다.
• 미분 분석: $F_r(x+a) - F_r(x) = b$ 의 해를 세기 위해, 특정 집합 $S_{ij}$ 내에서 방정식 $(x+1)^r - x^r = b$ 를 분석하는 문제로 환원합니다. 만약 이 방정식이 $S_{00}$ (여기서 $x$ 와 $x+1$ 모두 2 차 잉여) 에서 최대 하나의 해를 가진다면, 함수가 국소적 APN 임을 증명합니다.
• 부메랑 분석: 부메랑 연결 테이블 (BCT) 을 정의하는 방정식 시스템을 분석합니다. 해 공간 $(x, y)$ 를 집합들의 곱 $S_{ij} \times S_{kl}$ 로 분해함으로써 해의 개수를 상한으로 제한합니다.
• 지수합: 저자들은 해의 개수를 추정하고 특정 경우에 대한 정확한 미분 및 부메랑 스펙트럼을 유도하기 위해 Weil 경계와 2 차 지수의 특정 성질 (예: $\sum \chi(f(x))$) 을 활용합니다.
• 선형 동치: Lemma 2.8 을 활용하여 특정 지수들 (예: $3^{k+1}/2$) 이 다른 지수들과 선형 동치임을 보여, 결과를 일반화합니다.

3. 주요 기여

A. 일반적 이론적 프레임워크

이 논문은 이항식 $F_r$ 이 낮은 부메랑 균일성을 가진 국소적 APN 이 되기 위한 충분 조건을 확립합니다:

• 조건: $\gcd(r, q-1) \mid 2$ 이고, 모든 $b \in \mathbb{F}_q^*$ 에 대해 방정식 $(x+1)^r - x^r = b$ 가 $S_{00}$ 에서 최대 하나의 해를 가진다면, 다음이 성립합니다:
  • $\delta_{F_r} = \frac{q+1}{4}$ (국소적 APN).
  • $\beta_{F_r} \le 2$.

B. 특정 지수에 대한 검증

저자들은 위 조건이 논문 표 3 에 요약된 지수 $r$ 목록에 대해 성립함을 검증합니다. 여기에는 다음이 포함됩니다:

• $r = p^k + 1$ (홀수 $n$ 인 경우).
• $r = \frac{3^{k+1}}{2}$ (일반화된 Coulter-Matthews 지수).
• $r = 3$ 및 $r = \frac{2q-1}{3}$ ($q \equiv 11 \pmod{12}$ 인 경우).
• $r = \frac{3^{n+1}-1}{2}$ 및 $r = \frac{3^{n+1}-1}{8}$ ($p=3$ 인 경우).

C. 정확한 스펙트럼 결정

• 미분 스펙트럼: 논문은 $q \equiv 11 \pmod{12}$ 일 때 $F_3$ 및 $F_{\frac{2q-1}{3}}$ 에 대한 정확한 미분 스펙트럼을 유도합니다.
  • $F_3$ 의 경우, 스펙트럼은 지수합 $\Gamma$ 에 의존합니다.
  • $F_{\frac{2q-1}{3}}$ 의 경우, 스펙트럼은 명시적으로 $\{\omega_0 = \frac{q-3}{2}, \omega_1 = \frac{q+5}{4}, \omega_2 = \frac{q-3}{4}, \omega_{\frac{q+1}{4}} = 1\}$ 로 계산됩니다.
• $F_2$ ($p=3$) 의 부메랑 스펙트럼: 논문은 $p=3$ 이고 $n$ 이 홀수일 때 $F_2$ 에 대한 최초의 완전한 부메랑 스펙트럼을 제공합니다.

4. 주요 결과

1. 국소적 APN 성질: 표 3 에 나열된 모든 지수에 대해 함수 $F_r$ 이 미분 균일성 $\frac{q+1}{4}$ 를 가진 국소적 APN 임이 증명되었습니다.
2. 부메랑 균일성 상한: 동일한 지수 클래스에 대해 부메랑 균일성이 최대 2 임이 증명되었습니다.
3. 이전 문헌의 수정 (중요한 발견):
   • 이전 연구 (Mesnager 와 Wu, [14]) 는 큰 $q$ 에 대해 $F_2$ 의 부메랑 균일성이 2 라는 것을 추측하고 증명했습니다.
   • 이 논문은 특성 3 에서는 이를 반증합니다. 저자들은 $p=3$ 이고 $n$ 이 홀수일 때 $F_2$ 의 부메랑 균일성이 정확히 1임을 증명합니다.
   • 이유: 특성 3 에서 $1 = -2$ 라는 항등식이 이전 증명에서 고려된 특정 경우들을 양립 불가능하거나 퇴화되게 만들어, 더 낮은 균일성을 초래합니다.
4. $F_2$ ($p=3$) 에 대한 명시적 부메랑 스펙트럼:
   스펙트럼은 $\nu_0 = \frac{3q-5+2\Lambda}{4}$ 및 $\nu_1 = \frac{q+1-2\Lambda}{4}$ 로 주어지며, 여기서 $\Lambda = \sum_{x \in \mathbb{F}_q} \chi(x+1)\chi(x^2+1)$ 입니다.

5. 의의

• 암호학적 설계: 이 결과는 홀수 특성 유한체에서 작동하는 블록 암호의 S-박스 후보를 제공합니다. 낮은 미분 및 부메랑 균일성을 가진 함수는 현대 암호분석 공격에 저항하는 데 필수적입니다.
• 이론적 발전: 논문은 잘 연구된 짝수 특성 사례를 넘어 "국소적 APN" 함수에 대한 이해를 확장합니다. 특정 지수 구조를 가진 이항식을 분석하기 위한 통합된 프레임워크를 제공합니다.
• 경계 정교화: 부메랑 균일성이 2 에서 1 로 떨어지는 특정 경우 ($p=3$) 를 식별함으로써, 논문은 유한체 암호학에서 특성별 분석의 중요성을 강조하고 일반 특성 연구에서 이루어진 가정을 수정합니다.
• 스펙트럼 특성화: 균일성 경계뿐만 아니라 정확한 미분 및 부메랑 스펙트럼을 제공함으로써 이러한 함수의 보안 마진을 더 정확하게 평가할 수 있습니다.

결론적으로, 이 논문은 홀수 특성에서 광범위한 이항식 클래스로 국소적 APN 성질을 성공적으로 일반화하고, 그들의 낮은 부메랑 균일성을 증명하며, 특성 3 에서의 $F_2$ 이해에 대한 중요한 수정을 제시합니다.