기술 요약: 로컬 크루키드 순열의 D-클래스를 통한 완전 순열의 구성

문제 정의

본 논문은 유한체 $\mathbb{F}_{2^n}$ 상의 완전 순열(Complete Permutations, CPs) 구성을 다룬다. 순열 $f$가 CP라는 것은 $f$와 사상 $x \mapsto f(x) + x$가 모두 순열일 때를 의미한다. CP는 라이-마시(Lai–Massey) 프레임워크를 위한 S-box 구축 및 직교 라틴 방진 생성을 위해 암호학에서 매우 중요하다.

CP는 슈아이-리(Shuai–Li) 대응 관계를 통해 $\mathbb{F}_{2^{n+1}}$ 상의 **로컬 크루키드 순열(Locally Crooked Permutations, LCPs)**과 연결되어 있으나, 기존 방식은 "크루키드 함수 $\to$ LCP $\to$ CP" 경로에 의존했다. 이러한 접근법은 제한적이었는데, 그 이유는 LCP 클래스 내부에서 새로운 LCP를 자유롭게 생성하거나 이동하는 것을 허용하지 않았기 때문이다. 본 논문은 LCP 클래스 내부에서 직접적인 내부 군 작용(group actions)을 통해 새로운 CP를 생성함으로써 이 문제를 해결하고자 한다.

방법론

1. D-클래스와 불변성

저자는 고정된 방향 $q_1 = 2^n$에 대한 미분이 고정된 하이퍼플레인 $H = \{x : x_n = 0\}$의 여집합을 상으로 갖는 $\mathbb{F}_{2^{n+1}}$ 상의 순열 $f$의 집합인 D-클래스를 도입한다.
$$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$$
여기서 $K = \mathbb{F}_{2^{n+1}} \setminus H$이다.

본 논문은 $D$가 다음 세 가지 특정 군 작용에 대해 닫혀 있음을 증명한다:

1. 좌측 평행 이동(Left Translation): 임의의 $a \in \mathbb{F}_q$에 대한 $t_a \circ f$.
2. 좌측 곱셈(Left Multiplication): $H$를 보존하는 일반 선형군 $GL_H$의 임의의 $g$에 대한 $g \circ f$.
3. 우측 곱셈(Right Multiplication): $H$와 $K$를 교환하는 인볼루션(involution)의 중심화 소자(centralizer) $C$에 속하는 $f \circ h$.

또한, 이 클래스는 $X$가 평행 이동과 공액 인볼루션에 의해 생성되는 특정 이면체 군(dihedral group)의 궤도(orbit)들의 합집합인 경우, 특정 국소 평행 이동(subset $X$로 제한된 $t_{a,X}$)에 대해서도 닫혀 있다.

2. 경직성(Rigidity)과 구성 체인

저자는 $K$의 보집합 위에서 항등 함수로 작용하는 $D$ 내의 순열 $f$들로 구성된 리프티드 CP 부클래스(lifted CP subclass) $D^\uparrow \subset D$를 정의한다.

• 경직성: 본 논문은 $D^\uparrow$가 위의 폐쇄 성질 중 단일 연산(평행 이동, 선형 곱셈, 또는 중심화 소자 곱셈) 하에서 "경직되어 있음"을 증명한다. 즉, 단일 연산은 항등 함수가 아닌 한 리프티드 CP를 다른 리프티드 CP로 매핑할 수 없다.
• 구성 체인: 새로운 CP를 생성하기 위해, 저자는 다음과 같은 연산의 곱을 포함하는 체인을 구성한다:
  $$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$$
  이 체인은 국소 평행 이동에 의해 도입된 결함을 "수정(repair)"하여 결과가 $D^\uparrow$에 머물도록 하기 위해 국소 중심화 소자($g_{a,X_1}$ 및 $g_{a,X_2}$)를 활용한다.

3. 국소 공액(Local Conjugations)

이 구성은 기초 체 $\mathbb{F}_{2^n}$ 상에서 정의된 두 가지 특정 국소 공액 $f_1$과 $f_2$를 산출한다:

• $f_1$: $X_1 \subset H$에서 $f$를 수정하며, 여기서 $X_1$은 이면체 군에 대해 불변이다.
• $f_2$: $X_2$에서 $f$의 역원을 포함하여 수정하며, 여기서 $X_2$는 순환 군(cyclic group)에 대해 불변이다.
  본 논문은 이 수정된 사상들이 여전히 CP로 남기 위한 필요충분조건을 제공한다.

4. 알고리즘

이론을 구현하기 위해 두 가지 알고리즘이 제시된다:

1. 무작위 백트래킹 탐색(Random Backtracking Search): $f(x)$와 $f(x)+x$에 대한 제약 조건을 유지하면서 무에서부터 무작위 CP를 생성한다.
2. 탐욕적 국소 탐색(Greedy Local Search): 시드(seed) CP에 국소 공액($f_1, f_2$)을 반복적으로 적용한다. 이 알고리즘은 이동이 전체 차분 스펙트럼(DDT) 및 월시 스펙트럼(Walsh spectrum)에 기반한 품질 함수를 엄격하게 개선할 때만 이동을 수락한다.

주요 결과

이론적 기여

• 불변성 증명: D-클래스가 지정된 군 작용 및 국소 평행 이동에 대해 불변임을 확립하였다.
• 경직성 정리: 리프티드 CP 부클래스 $D^\uparrow$는 단일 연산에 의해 생성될 수 없음을 증명하였으며, 이는 복합 구성 체인이 필요함을 시사한다.
• CCZ-부등가 기준: 차분 분포표(DDT) 또는 절대 월시 계수의 멀티셋(multiset) 변화 여부를 확인하는 것을 통해, 새로 구성된 CP가 시드와 CCZ-부등가인지 판단하는 기준을 도출하였다.
• 암호학적 경계: 국소 수정 하에서의 차분 균일도($\delta$), 비선형성($nl$), 대수적 차수($\deg$)에 대한 경계값을 도출하였다. 특히$\delta$는 수정된 부분집합의 크기$m$에 대해 최대$2m$만큼 변한다.

실험적 결과

$H \cong \mathbb{F}_{2^5}$ (32개 원소)에 대해 실험이 수행되었다:

• $\delta=4$ CP 생성: 선형 시드($\delta=32$) 및 무작위 시드로부터 시작하여, 탐욕적 탐색을 통해 차분 균일도가 $\delta=4$인 여러 완전 순열을 성공적으로 찾아냈다.
• 구별되는 스펙트럼: 생성된 CP들은 서로 다른 차분 스펙트럼을 보였으며, 참조용 Dillon 기반 CP(차분 균일도 $\delta=8$)와도 구별되는 스펙트럼을 나타냈다.
• CCZ-부등가성: 구별되는 차분 스펙트럼은 본 구성이 단순히 시드의 아핀 변형이 아니라, 새로운 CCZ-부등가 클래스를 생성함을 확인시켜 준다.
• 연결성 증거: 서로 다른 무작위 시드로부터 유사한 지표 분포로 반복적으로 수렴하는 현상은, 리프티드 CP 집합 $D^\uparrow$가 국소 공액 이동 하에서 연결되어 있을 가능성에 대한 예비적 증거를 제공한다.

의의 및 주장

본 논문은 LCP 클래스의 내부 구조를 활용하여 새로운 완전 순열을 생성하는 체계적인 대수적 프레임워크를 제공한다고 주장한다.

• 크루키드 함수를 넘어서: 크루키드 함수에서 시작해야 하는 기존 방식과 달리, 이 접근법은 LCP 공간 자체를 탐색하여 CP를 찾을 수 있게 한다.
• 암호학적 유용성: 본 방법은 S-box 설계에 바람직한 특성인 낮은 차분 균일도($\delta=4$)를 가진 CP를 성공적으로 생성한다. 이는 표준적인 크루키드 함수 대응 관계를 통해서는 구성하기 어려웠던 성과이다.
• 구조적 통찰: $D^\uparrow$의 "경직성"과 국소 평행 이동을 "수정"하는 데 있어 중심화 소자의 구체적인 역할에 대한 규명은 LCP와 CP 사이의 관계에 대한 더 깊은 이론적 이해를 제공한다.
• 미해결 과제: 저자는 $D^\uparrow$의 연결성과 이 클래스 내 APN 함수의 존재 여부를 열린 문제로 제시하며, 실험 결과가 연결성을 지지하고 있으나 이를 공식적으로 증명하기 위해서는 추가 연구가 필요함을 언급하였다. 또한, 결과가 APN 순열과의 잠재적 연결성을 시사하지만, 본 연구에서 APN 순열을 명시적으로 확립한 것은 아니라고 밝히고 있다.