Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

기술 요약: 자기 동치 부분 공간 내 Gröbner 기저 탐색을 통한 차원 8의 이차 APN 함수 연구

문제 정의
$\mathbb{F}_{2^n}$ 상에서의 Almost Perfect Nonlinear (APN) 함수의 CCZ-동치(CCZ-equivalence)에 따른 분류는 암호학, 특히 $n=8$인 경우에 있어 핵심적인 문제이다. $n \leq 6$에 대해서는 분류가 완료되었으나, $n=8$에 대해서는 여전히 부분적이다. 이차 APN 함수의 탐색 공간은 매우 방대하며($2^{224}$개의 가능한 계수 벡터), APN 밀도가 약 $2^{-n}$으로 추정되기 때문에 전역적 무작위 탐색은 불가능하다. BBL2021(Beierle, Brinkmann, Leander, 2021)의 재귀적 트리 탐색과 같은 이전의 체계적 노력은 자기 동치 제약 조건에 의해 정의된 구조적 대수적 부분 공간을 탐색하였다. 구체적으로 BBL2021은 위수 5를 갖는 선형 자기 동형 사상 $A$(클래스 인덱스 22)와 관련된 40차원 자기 동치 부분 공간 $V_A$에서 APN 함수를 발견하지 못했다고 보고했다. 본 논문은 이 부분 공간이 실제로 APN 함수를 포함하지 않는 것인지, 아니면 이전의 탐색 방법이 이를 찾아내는 데 실패한 것인지를 조사한다.

방법론
저자들은 이전의 트리 탐색보다 $V_A$를 더 효과적으로 탐색하기 위해 무작위 샘플링과 대수적 열거를 결합한 2단계 계산 파이프라인을 제안한다.

1. 1단계: RREF 매개변수화를 통한 무작위 샘플링
   저자들은 $V_A = \{F : F \circ A = A \circ F\}$의 명시적인 기약 행 사다리꼴(Reduced Row Echelon Form, RREF) 매개변수화를 구축한다. 이는 탐색 공간을 $2^{224}$에서 $2^{40}$으로 축소한다. 이 부분 공간 내에서 APN 함수의 경험적 밀도는 약 $10^{-4}$로 나타났으며(무작위 샘플 11,000개당 약 1개의 APN 함수), 이는 표적 샘플링을 가능하게 한다. 저자들은 "APN 센터"($V_A$ 내의 APN 함수)를 찾기 위해 무작위 샘플링을 수행한다.

2. 2단계: Gröbner 기저 슬라이스 계산
   1단계에서 발견된 각 APN 센터에 대해, 저자들은 해당 센터를 통과하는 24차원 아핀 초평면("NL=4 슬라이스")을 정의한다. 이는 224개의 대수적 정규형(Algebraic Normal Form, ANF) 계수 중 인덱스 $p \leq 4$에 해당하는 200개의 계수를 센터의 값으로 고정함으로써 달성되며, 나머지 24개의 계수는 미지수로 남는다.
   APN 조건은 불 대수 링(Boolean ring) 상의 다항식 방정식 시스템으로 인코딩된다. 저자들은 이 시스템의 Gröbner 기저를 계산하기 위해 Magma 컴퓨터 대수 시스템을 사용한다.

• 만약 시스템이 불가능(infeasible)하다면, 해당 슬라이스에는 다른 APN 함수가 존재하지 않는다.
• 만약 시스템이 해를 가진다면, Gröbner 기저 열거를 통해 해당 24차원 초평면 내의 모든 APN 함수를 찾아낸다.
  결정적으로, 센터는 $V_A$에 속함이 보장되지만, Gröbner 기저 단계에서 발견된 해들은 $V_A$에 국한되지 않으며 $V_A$ 외부에 존재할 수 있다.

3. 분류 및 검증
   발견된 함수들은 직교 도함수 불변량(ortho-derivative invariant) $\sigma(F)$를 사용하여 분류된다. 이는 Yoshiara의 정리와 Canteaut 등의 결과에 의해 이차 APn 함수에 대한 완전한 CCZ-불변량임이 증명되었다. 저자들은 이 시그니처를 BBL2021 사전 2020 컴파일, Beierle 외 연구진의 2025년 데이터베이스(약 380만 개의 함수 포함), 그리고 고전적인 Gold 함수 데이터베이스와 스트리밍 비교를 수행한다.

주요 결과
저자들은 전체 $2^{16}$개의 가능한 슬라이스 중 0.65%에 해당하는 428개의 서로 다른 24차원 슬라이스에 대해 파이프라인을 실행하였다.

• 새로운 클래스 발견: 탐색 결과 6개의 CCZ-동치 클래스에 속하는 566개의 고유한 이차 APN 함수가 발견되었다.
  • 네 개의 새로운 클래스 (A, B, C, D): 이 500개의 함수(Class A 362개, B 72개, C 36개, D 30개)는 Beierle 2025 데이터베이스, BBL2021 사전 2020 데이터베이스, 또는 고전적인 Gold 패밀리에 존재하지 않는다.
  • 두 개의 알려진 클래스 (E, F): 이는 Gold 함수 $x^3$ 및 $x^9$(및 그 Frobenius 궤도)에 대응하며, 파이프라인 검증을 위한 대조군 역할을 한다.
• 구조적 발견:
  • 부분 공간 멤버십: 멤버십 테스트($F \circ A = A \circ F$) 결과, Class A, E, F는 완전히 $V_A$ 내에 있음이 밝혀졌다. 그러나 Class B, C, D는 완전히 $V_A$ 외부에 존재한다.
  • "게이트웨이(Gateway)" 현상: 외부 클래스(B, C, D)의 138개 함수는 $V_A$ 내에 존재하는 Gold 함수(Class E 및 F)를 중심으로 한 슬라이스에서만 독점적으로 발견되었다. Class A 함수를 중심으로 한 슬라이스는 $V_A$ 외부의 이웃을 생성하지 못했다.
  • 대안적 시드(Seed)의 실패: Beierle 2025 데이터베이스에서 가져온 532개의 APN 함수($V_A$ 외부 함수)를 슬라이스 센터로 사용하는 비교 실험에서는 새로운 APN 이웃이 발견되지 않았다. 이는 새로운 클래스를 발견하는 "게이트웨이" 능력은 모든 APN 함수에 대한 일반적인 속성이 아니라, 자기 동치 부분 공간의 특정 대수적 구조에 의존한다는 것을 시사한다.

의의 및 주장
본 논문은 이차 APN 함수 분류 분야에 다음과 같은 중요한 기여를 한다고 주장한다.

1. 이전 결과의 수정: 저자들은 BBL2021이 APN 함수가 없다고 보고했던 자기 동치 부분 공간 $V_A$(클래스 인덱스 22)가 실제로는 적어도 4개의 이차 APN 함수 CCZ-클래스를 포함하고 있음을 입증한다. BBL2021의 트리 탐색 실패는 유효한 해를 제거했을 수 있는 분기 가지치기(branch-pruning) 전략 때문인 것으로 분석되며, 반면 Gröbner 기저 접근법은 각 슬라이스 내에서 완전한 열거를 수행한다.
2. 새로운 함수 발견: 저자들은 직교 도함수 불변량을 통해 알려진 약 380만 개의 함수와 구별되는 8차원 이차 APN 함수의 네 가지 새로운 CCZ-클래스가 존재함을 엄격하게 증명한다.
3. 방법론적 혁신: 저자들은 "GB-내비게이션(GB-navigation)" 메커니즘을 도입한다. 이는 전역 탐색이 불가능하더라도, APN 밀도가 높은 구조적 부분 공간을 활용하여 "시드(seed)" 함수를 찾을 수 있음을 제안한다. 이후 Gröbner 기저 단계는 로컬 열거 도구로서 작용하여, 부분 공간을 벗어나 새로운 클래스를 찾아낼 수 있게 한다. 저자들은 이 메커니즘이 일반적인 것이 아니라고 강조하는데, 이는 비-부분 공간 함수들이 생산적인 시드로 작용하는 데 실패한 점을 통해 입증된다.
4. 직교 도함수의 완전성: 본 연구는 직교 도함수 시그니처가 이차 함수에 대한 정확한 CCZ-불변량으로서, 전수 쌍별 테스트 없이도 엄격한 분류를 가능하게 한다는 점을 재확인한다.

저자들은 결론적으로, 자신들의 접근 방식이 다른 BBL2021 클래스 인덱스를 탐색하고 Gröbner 기저 슬라이싱 기술을 활용하여 APN 지형을 탐색함으로써 이차 APN 함수 분류를 확장할 수 있는 체계적인 프로그램을 제공한다고 밝히고 있다.