On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

이 논문은 부울 벤트 함수 (Boolean bent functions) 의 두 가지 고전적인 1 차 구성법인 마리오라나-맥팔랜드 (Maiorana–McFarland, MM) 클래스와 데사르그 (Desarguesian) 부분 스프레드 (PSap) 클래스의 일반화에 대한 연구를 다룹니다. 특히, 기존에 알려진 MM# (완결된 MM) 클래스나 PSap# 클래스에 속하지 않는 새로운 벤트 함수들의 구성과 그 성질을 규명하는 데 중점을 둡니다.

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

1. 문제 제기 (Problem Statement)

• 배경: 벤트 함수는 암호학 (특히 블록 암호 설계) 에서 매우 중요한 역할을 하며, 비선형성이 최대가 되는 함수입니다. 벤트 함수를 생성하는 두 가지 주요 방법은 '1 차 구성 (Primary construction)'과 '2 차 구성 (Secondary construction)'입니다.
• 현황:
  • 차수가 6 이하인 모든 벤트 함수는 완결된 MM 클래스 ($MM^\#$) 에 속하는 것으로 알려져 있습니다.
  • 8 차원 이상의 벤트 함수 중 $MM^\#$에 속하지 않는 예시 (Dillon 에 의해 발견됨) 가 존재하지만, $MM^\#$ 클래스는 전체 벤트 함수 집합에서 매우 작은 비율을 차지합니다.
  • 기존 연구들은 주로 $MM^\#$ 클래스를 벗어난 함수를 찾거나, 2 차 구성 (연결, concatenation) 을 통해 새로운 함수를 만드는 데 집중해 왔습니다.
• 연구 목적:
  1. 고전적인 MM 클래스나 PSap 클래스와 동치 (equivalent) 가 아닌 새로운 일반화된 MM (GMM) 함수들을 구성하여 $MM^\#$ 클래스 밖으로 배치하는 것.
  2. 일반화된 PSap 함수의 분해 (decomposition) 성질을 분석하여, 이들이 벤트 또는 세미벤트 함수들의 연결 (concatenation) 로부터 유도될 수 없는 경우를 규명하는 것.
  3. 벡터 일반화 PSap 함수의 성분을 연결하여 새로운 2 차 구성법을 제시하는 것.

2. 방법론 (Methodology)

논문은 다음과 같은 수학적 도구와 기법을 활용합니다:

• 이계 도함수 (Second-order derivatives) 와 Dillon 의 기준:
  • 벤트 함수가 $MM^\#$ 클래스에 속하는지 판별하는 Dillon 의 기준을 사용합니다. 이는 함수의 이계 도함수가 특정 부분 공간 (M-서브스페이스) 에서 0 이 되는지 여부에 기반합니다.
  • 확장 아핀 동치 (EA-equivalence) 하에서 이계 도함수의 성질이 불변임을 증명하고 이를 활용합니다.
• 대수적 곡선 (Algebraic Curves) 및 함수체 이론:
  • 함수의 이계 도함수가 상수인지 여부를 판별하기 위해 유한체 위에서 정의된 아틴 - 슈라이어 (Artin–Schreier) 곡선의 유리점 (rational points) 수를 추정합니다.
  • Hasse–Weil 경계 (Hasse–Weil bound) 와 Hurwitz 종형 공식 (genus formula) 을 사용하여 곡선에 유한체 유리점이 존재함을 증명함으로써, 해당 함수가 분해 불가능함을 보입니다.
• 연결 (Concatenation) 기법:
  • 4 개의 벤트 함수를 연결하여 새로운 벤트 함수를 생성하는 2 차 구성법을 연구합니다.

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

3.1. $MM^\#$ 클래스 밖의 일반화된 MM (GMM) 함수 구성 (제 3 장)

• 문제: 기존 MM 함수들을 조합하여 GMM 함수를 만들 때, 만약 구성에 사용된 MM 함수들이 공통의 M-서브스페이스를 공유하면 결과 함수도 $MM^\#$ 클래스에 속하게 됩니다.
• 해결책: 저자들은 공통 M-서브스페이스를 공유하지 않는 (또는 자명한 M-서브스페이스만 공유하는) MM 함수들을 조합하는 새로운 구성법을 제시합니다.
• 구체적 구성:
  • $h(x_1, x_2) = Tr(x_1 \pi(x_2))$ 형태의 MM 함수를 기반으로 합니다.
  • $\pi$가 특정 성질 (Property P) 을 만족하는 치환 (permutation) 일 때, $h$는 유일한 M-서브스페이스를 가집니다.
  • $\pi$로 역함수 ($x^{2^m-2}$) 또는 골드 함수 ($x^{2^k+1}$) 를 선택하여 Property P 를 만족시킵니다.
  • 이를 바탕으로 $f(x, y, z) = f^{(z)}(x) + Tr(yz)$ 형태의 함수를 정의합니다. 여기서 $f^{(z)}$는 $z$의 값에 따라 서로 다른 MM 함수 (또는 그 변형) 를 사용합니다.
• 결과: $n > 2k + 4$ 조건 하에서, 이렇게 구성된 GMM 함수는 $MM^\#$ 클래스에 속하지 않음을 증명했습니다. 이는 Dillon 의 기준 (M-서브스페이스의 차원) 을 통해 검증되었습니다.

3.2. 일반화된 PSap 함수의 분해 불가능성 (제 4 장)

• 문제: 벤트 함수가 2 차 구성 (연결) 으로 얻어지려면, 그 함수가 특정 부분 공간에 대해 벤트 또는 세미벤트 분해 (decomposition) 를 허용해야 합니다. 이는 함수의 쌍대 (dual) 함수가 비자명한 M-서브스페이스를 가지는 것과 동치입니다.
• 분석 대상: 일반화된 PSap 함수 $g(x, y) = P(Tr(x y^{-\eta}))$ 및 그 쌍대 함수.
• 주요 결과 (Proposition 12, Theorem 2):
  • 함수의 차수가 유한체의 크기에 비해 충분히 작을 때 (예: $deg(Q) \le \frac{2^m/4 - 1}{3e}$), 이러한 일반화된 PSap 함수는 벤트 분해나 세미벤트 분해를 허용하지 않습니다.
  • 이는 해당 함수들이 알려진 2 차 연결 구성법 (concatenation of bent/semibent functions) 으로 얻어질 수 없음을 의미합니다.
  • 증명 과정에서 아틴 - 슈라이어 곡선의 유리점 존재성을 이용하여 이계 도함수가 상수가 아님을 보였습니다.
• 의미: 이는 PSap 클래스의 함수들이 MM 클래스나 2 차 구성법과 구별되는 고유한 구조를 가짐을 보여줍니다.

3.3. 벡터 일반화 PSap 함수를 이용한 새로운 2 차 구성 (제 5 장)

• 아이디어: 벡터 벤트 함수 $F: V_n \to V_m$의 성분 함수들 (component functions) 의 연결을 통해 새로운 벤트 함수를 생성합니다.
• 핵심 성질: 벡터 일반화 PSap 함수의 성분 함수들의 쌍대 함수들은 특정 선형 관계를 만족합니다 ($(F_\alpha)^* + (F_\beta)^* = (F_{\alpha+\beta})^*$).
• 구성: 이 성질을 이용하여 4 개의 성분 함수를 연결 ($F_\alpha \parallel F_\beta \parallel F_\gamma \parallel F_{\alpha+\beta+\gamma+1}$) 하면 새로운 벤트 함수가 생성됨을 증명했습니다 (Theorem 3, Theorem 4).
• 결과: 이 구성법은 PSap 구조의 특성을 활용하여 $MM^\#$ 클래스 밖의 벤트 함수를 생성하는 새로운 2 차 구성법을 제공합니다.

4. 의의 및 결론 (Significance)

1. 클래스 확장: 기존에 알려진 $MM^\#$ 및 $PSap^\#$ 클래스에 속하지 않는 새로운 벤트 함수들의 무한한 계열을 구성함으로써, 벤트 함수의 다양성과 구조적 복잡성을 확장했습니다.
2. 구분 가능성: 일반화된 PSap 함수들이 2 차 구성 (연결) 으로 얻어질 수 없음을 증명함으로써, 이 함수들이 1 차 구성법의 고유한 특성을 유지하고 있음을 보여주었습니다. 이는 벤트 함수의 분류와 암호학적 성질 분석에 중요한 통찰을 제공합니다.
3. 새로운 2 차 구성법: 벡터 함수의 성분을 연결하는 새로운 방법을 제시하여, 향후 더 많은 벤트 함수를 생성하는 데 활용할 수 있는 도구를 마련했습니다.
4. 수학적 기법의 융합: 대수적 곡선 이론과 함수체 이론을 암호학 (벤트 함수) 문제에 적용하여, 이계 도함수의 성질을 분석하는 강력한 방법론을 제시했습니다.

요약하자면, 이 논문은 벤트 함수의 이론적 경계를 넓히고, 기존 구성법으로는 설명할 수 없는 새로운 함수들의 존재와 성질을 엄밀하게 증명하여 암호학 및 부울 함수 이론 분야에 중요한 기여를 했습니다.