New Insights into Involutory and Orthogonal MDS Matrices

기술 요약: 인볼루토리(Involutory) 및 직교(Orthogonal) MDS 행렬에 대한 새로운 통찰

문제 정의
최대 거리 분리(Maximum Distance Separable, MDS) 행렬은 최적의 브랜치 넘버(branch number)를 갖기 때문에 블록 암호 및 해시 함수의 확산 계층(diffusion layers)에 있어 필수적이다. 효율적인 MDS 후보를 구축하기 위한 상당한 문헌이 존재하지만, 특정 구조적 특성, 즉 인볼루토리(자기 역행렬) 및 직교(전치 역행렬) 특성은 암호화와 복호화에 동일하거나 거의 동일한 회로를 사용할 수 있게 하여 구현 비용을 줄이는 데 매우 바람직하다. 최근 이러한 개념들은 "세미-인볼루토리(semi-involutory)" 및 "세미-직교(semi-orthogonal)" 행렬로 일반화되었다. 그러나 기존 연구는 주로 새로운 구성을 제안하거나 구현 지표를 최적화하는 데 집중해 왔다. 이들 일반화된 변체(세미-인볼루토리/세미-직교)와 전통적인 대응물(인볼루토리/직교) 사이의 구조적 상호 연결 관계, 특히 유한체 $\mathbb{F}_{2^m}$ 상에서의 열거(enumeration)에 관한 체계적인 이해가 부족한 실정이다.

방법론
저자들은 새로운 행렬 구성을 제안하기보다는 구조적 분석 접근 방식을 채택한다. 핵심 방법론은 $\mathbb{F}_{2^m}^*$ 상의 비특이 행렬을 $M = D_1 M_1 D_2$ 형태(여기서 $D_1$과 $D_2$는 비특이 대각 행렬이고 $M_1$은 특정 정규 형태(첫 행과 열이 1로 구성됨)를 가진 "대표 행렬"임)로 고유하게 분해하는 것에 의존한다.

주요 방법론적 단계는 다음과 같다:

1. 상호 연결 확립: 본 논문은 $D_1 M_1 D_2$를 적용할 때 인볼루토리, 세미-인볼루토리, 직교, 또는 세미-직교 특성이 예측 가능한 방식으로 보존되거나 변환됨을 증명한다.
2. 계수 관계 도출: 행렬 $M$이 특정 속성을 만족하기 위해 필요한 $D_1$과 $D_2$에 대한 제약 조건을 분석함으로써, 저자들은 일반화된 행렬과 그들의 전통적인 대응물 사이의 양방향 관계를 도출한다.
3. 구조적 특징 규명: 저자들은 임의의 차수 $n$에 대해 $\mathbb{F}_{2^m}$ 상의 직교 행렬의 일반적인 대수적 구조를 도출하고, 이를 $n=3$ 및 $n=4$에 대해 특수화한다.
4. 열거: 인볼루토리 MDS 행렬에 대한 알려진 열거 결과와 도출된 구조적 관계를 사용하여, 특정 차수와 체 크기에 대한 세미-인볼루토리 및 세미-직교 MDS 행렬의 정확한 개수를 계산한다.

주요 기여 및 결과

• 구조적 상호 연결: 본 논문은 세미-인볼루토리와 인볼루토리 행렬 사이, 그리고 세미-직교와 직교 행렬 사이의 유의미한 관계를 확립한다. 구체적으로, $n \times n$ 인볼루토리 MDS 행렬의 개수는 $M_1$ 형태의 세미-인볼루토리 MDS 행렬의 개수에 $(2^m - 1)^{n-1}$을 곱한 것과 같음을 보여준다. 세미-직교와 직교 행렬에 대해서도 유사한 대응 관계가 증명된다.
• $3 \times 3$ 행렬의 열거:
  • 직교 MDS: 저자들은 $\mathbb{F}_{2^m}$ 상의 $3 \times 3$ 직교 MDS 행렬의 개수를 $(2^m - 2)(2^m - 3)(2^m - 4)$라는 명시적인 공식으로 도출한다.
  • 세미-직교 MDS: 구조적 연결 고리를 활용하여, $3 \times 3$ 세미-직교 MDS 행렬의 개수를 $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$로 도출한다.
  • 세미-인볼루토리 MDS: 본 논문은 $3 \times 3$ 세미-인볼루토리 MDS 행렬의 개수에 대한 직접적인 도출을 제공하며, 공식 $(2^m - 1)^5(2^m - 2)(2^m - 4)$를 확인한다. 이는 기존 문헌에서 발견되는 증명들에 대한 대안이 된다.
• 속성의 교집합: 저자들은 세미-인볼루토리이면서 동시에 세미-직교인 행렬들을 규명한다. 그들은 $3 \times 3$ 행렬의 경우, $M_1$ 형태의 모든 세미-인볼루토리 행렬은 반드시 대칭 행렬임을 증명하며, 이는 두 속성을 모두 가진 행렬의 개수가 세미-인볼루토리 행렬의 개수와 동일함을 의미한다.
• $4 \times 4$ 행렬 열거: 본 연구는 $4 \times 4$ 행렬로 확장된다. 저자들은 $m = 3, \dots, 8$에 대해 세미-인볼루토리 MDS 행렬의 개수를 계산하고, $m=3, 4$에 대해 직교/세미-직교 행렬의 개수를 계산한다. 또한 d-XOR 게이트 수를 기준으로 경량 직교 MDS 행렬(order 4)을 식별하여, $\mathbb{F}_{2^3}$에서 64개, $\mathbb{F}_{2^4}$에서 72개의 최적 개수를 찾아냈다.
• 일반 구조: $\mathbb{F}_{2^m}$ 상의 $n \times n$ 직교 행렬에 대한 일반적인 형태가 나머지 부분 행렬 요소들과 특정 합계 제약 조건을 통해 표현되도록 도출된다.

의의 및 주장
본 논문은 특정 구조적 제약을 가진 MDS 행렬의 열거를 이해하기 위한 통합된 프레임워크를 제공한다고 주장한다. 구성을 넘어 구조적 관계에 초점을 맞춤으로써, 저자들은 일반화된 변체(세미-인볼루토리/세미-직교)의 개수가 그들의 전통적인 대응물로부터 직접 도출될 수 있음을 입증한다.

저자들은 자신들의 연구가 다음과 같은 점을 제공한다고 밝힌다:

1. 대안적 도출: 기존의 포괄적인 증명들에 비해 $3 \times 3$ 세미-인볼루토리 및 세미-직교 MDS 행렬의 계수 공식에 대한 더 직접적이고 간결한 도출을 제공한다.
2. 새로운 열거 데이터: $3 \times 3$ 직교 MDS 행렬의 개수(기존 문헌에서 확립되지 않았던 것)와 더 큰 유한체에 대한 $4 \times 4$ 행렬의 확장된 개수를 제공한다.
3. 이론적 통찰: $3 \times 3$ 행렬의 경우, 세미-인볼루토리와 세미-직교 속성의 교집합이 세미-인볼루토리 행렬의 집합과 일치한다는 사실을 증명하며, 이는 고차수(예: $n \ge 4$)에서는 반드시 성립하는 것은 아닌 성질이다.

본 논문은 이러한 상호 연결 관계가 추가적인 구조적 제약을 만족하는 MDS 행렬의 개수를 결정하는 체계적인 방법을 제공하며, 여러 대수적으로 제약된 $3 \times 3$ 및 $4 \times 4$ MDS 클래스에 대한 명시적인 열거 공식을 통합한다고 결론짓는다.