On the Walsh spectra of quadratic APN functions

기술적 요약: 2 차 APN 함수의 월시 스펙트럼에 관하여

문제 제기
거의 완벽한 비선형 (APN) 함수는 대칭 암호 시스템의 핵심 구성 요소로, 차분 공격에 대한 최적의 저항력을 제공합니다. 이러한 함수의 근본적인 속성은 그 선형성이며, 이는 월시 스펙트럼에 의해 결정됩니다. 2 차 APN 함수의 진폭 분포 (따라서 월시 스펙트럼) 는 홀수 차원 $n$ 에 대해서는 완전히 규명되었으나, 짝수 $n$ 의 경우는 여전히 대부분 미해결 상태입니다. 짝수 $n$ 에 대해 알려진 유일한 일반적 제약 조건은 월시 변환의 4 번째 모멘트에서 유도됩니다. 본 논문은 $n$ 이 짝수인 2 차 APN 함수 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ 의 가능한 월시 스펙트럼에 대한 이해의 공백을 메우며, 특히 그 진폭 분포에 대한 더 강력한 조건을 도출하는 것을 목표로 합니다.

방법론
저자들은 2 차 APN 함수와 유한 기하학 사이에 두 가지 새로운 기하학적 연결을 확립했습니다:

1. 벡터 공간 분할: 본 논문은 2 차 APN 함수의 진폭 분포가 주변 공간 $\mathbb{F}_2^n$ 의 벡터 공간 분할과 유일하게 대응됨을 보여줍니다. 구체적으로, $F$ 의 비자명하고 비-벤텐 (non-bent) 인 성분 함수들은 분할 내의 부분공간들과 연관되며, 각 부분공간의 차원은 해당 성분 함수의 진폭과 직접적으로 연결됩니다.
2. 차단 집합: 비자명하고 비-벤텐인 성분들의 집합 $N_F$ 는 사영 공간 $PG(n-1, 2)$에서 특정 유형의 차단 집합을 형성함이 입증되었습니다. 특히, 저자들은$N_F$와 임의의$n/2$ 차원 부분공간의 교집합이 홀수 개의 점을 포함해야 함을 증명했습니다.

벡터 공간 분할과 차단 집합에 대한 확립된 정리들 (특히 분할의 "꼬리"와 최소 차단 집합에 관한 결과) 을 활용함으로써, 저자들은 이러한 기하학적 제약을 2 차 APN 함수의 진폭 분포에 대한 대수적 경계로 변환했습니다.

주요 기여 및 결과

• 벡터 공간 분할과의 연결 (제 II 절):

  • 정리 II.4 는 성분 함수 $F_b$ 가 진폭 $2^{(n+k)/2}$ 를 가질 경우, 이는 $\mathbb{F}_2^n$ 의 벡터 공간 분할 내의 $k$ 차원 부분공간에 대응됨을 확립합니다.
  • 이 연결을 통해 분할 이론의 패킹 조건과 차원 경계를 적용할 수 있게 됩니다.
  • 정리 II.10: 2 차 APN 함수는 $2^{3n/4}$ 보다 큰 진폭을 가진 성분 함수를 최대 하나만 가질 수 있습니다. 그러한 성분이 존재할 경우, 나머지 모든 성분은 진폭이 최대 $2^{(2n-l)/2}$ 이어야 하며, 여기서 $l$ 은 최대 진폭의 지수입니다.
  • 명제 II.14–II.16: 선형성과 특정 진폭의 존재에 기반하여 비-벤텐 성분의 수 ($|N_F|$) 에 대한 새로운 하한이 유도되었습니다.

• 차단 집합과의 연결 (제 III 절):

  • 계 III.3: 집합 $N_F$ 는 $(n/2)$-공간에 관해 $PG(n-1, 2)$에서 차단 집합이며, 추가적으로 모든 그러한 공간이$N_F$ 와 홀수 개의 점에서 교차한다는 속성을 가집니다.
  • 정리 III.9: 이는 2 차 APN 함수에 대한 벤텐 성분 함수의 수에 대한 첫 번째 비자명하고 일반적인 상한입니다. 구체적으로, $n \ge 6$ 인 경우, 비-벤텐 성분의 수는 $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ 을 만족합니다. 등호는 $n=8$ 일 때만 가능합니다. 결과적으로, 벤텐 성분의 수는 최대 $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$ 입니다.

• 종합 및 차원 분석 (제 IV 절):

  • 분할 및 차단 집합 제약을 결합함으로써, 저자들은 여러 이론적으로 가능한 진폭 분포들을 배제했습니다.
  • 정리 IV.1: $[(n/2)^{2^{n/2+1}}]$ 유형의 벡터 공간 분할 (즉, $(n/2)$-스프레드) 은 어떤 2 차 APN 함수에도 대응되지 않습니다.
  • 정리 IV.5: $n=8$ 의 경우, 논문은 가능한 진폭 분포를 특정 목록으로 좁혔으며 (자명한 분할과 4-스프레드를 제외), 잠재적인 확장된 월시 스펙트럼의 수를 최대 18 개의 서로 다른 유형으로 줄였습니다.
  • 명제 IV.4: 논문은 서로 다른 매개변수 범위에서 $|N_F|$ 에 대한 유도된 하한들의 강도를 비교하여, 함수의 선형성에 따라 어떤 하한이 지배적인지 식별했습니다.

• 동치 및 치환 (제 V 절):

  • 논문은 이러한 구조들이 EA-동치와 CCZ-동치 하에서 어떻게 작용하는지 분석했습니다.
  • 계 V.6: 2 차 APN 함수가 치환과 CCZ-동치라면, 적은 수의 비-벤텐 성분을 가질 수 없습니다. 구체적으로, $|N_F| \ge 3(2^{n/2}-1)$ 이며, $N_F$ 는 3-겹 차단 집합이어야 합니다.

의의 및 주장
본 논문은 잘 알려진 4 번째 모멘트 경계를 넘어 2 차 APN 함수의 월시 스펙트럼에 대한 첫 번째 일반적 조건을 제공한다고 주장합니다. 이러한 함수들의 대수적 속성을 벡터 공간 분할과 차단 집합의 조합론적 구조와 연결함으로써, 저자들은 가능한 진폭 분포에 대한 강력한 제약을 도출했습니다.

저자들은 명시적으로 그들의 결과가 다음과 같다고 밝히고 있습니다:

1. 2 차 APN 함수는 $2^{3n/4}$ 보다 큰 진폭을 가진 성분을 최대 하나만 가질 수 있음을 증명합니다.
2. 벤텐 성분의 수에 대한 첫 번째 비자명한 상한을 제공합니다.
3. 벤텐 성분의 수에 기반하여 함수가 치환과 CCZ-동치인지 여부를 결정하는 조건을 제시합니다.
4. 작은 짝수 차원 (특히 $n=6, 8, 10$) 에 대한 모든 가능한 진폭 분포를 체계적으로 나열하여, 실현된 것과 여전히 미해결 문제인 것을 강조합니다.

논문은 8 차원에서 특정 진폭 분포를 가진 APN 함수의 존재 여부와 비고전적 월시 스펙트럼을 가진 2 차 APN 함수의 무한한 계열에 대한 탐색을 포함한 미해결 문제들을 나열하며 마무리합니다. 저자들은 많은 가능성을 배제했지만, 2 차 APN 함수에 대한 월시 스펙트럼의 완전한 분류는 여전히 미해결 과제임을 지적하며 겸손한 어조를 유지했습니다.