On the Direct Construction of MDS and Near-MDS Matrices

논문 개요

이 논문은 암호학, 특히 블록 암호와 해시 함수의 확산 계층 (Diffusion Layer) 설계에 필수적인 최대 거리 분리 (MDS, Maximum Distance Separable) 행렬과 근접 MDS (NMDS, Near-MDS) 행렬의 직접 구성 (Direct Construction) 방법을 제안합니다. 기존에는 작은 크기의 행렬에 대해 탐색 (Search) 기반 방법이 주로 사용되었으나, 큰 크기의 행렬이나 경량 암호 환경에서는 직접 구성법이 필수적입니다. 특히, 기존 문헌에서 직접 구성법이 부재했던 재귀적 (Recursive) NMDS 행렬과 대칭적 (Involutory) NMDS 행렬의 구성 방법을 최초로 제시했다는 점이 핵심입니다.

1. 문제 정의 (Problem)

• MDS 행렬의 중요성: MDS 행렬은 최적의 분기 수 (Branch Number) 를 가지며, 암호 시스템의 확산 속도와 안전성을 보장합니다.
• NMDS 행렬의 필요성: 경량 암호 (Lightweight Cryptography) 환경에서는 MDS 행렬보다 구현 비용이 낮으면서도 보안과 효율성 사이의 균형을 제공하는 NMDS 행렬이 선호됩니다.
• 기존 연구의 한계:
  • MDS 행렬에 대해서는 재귀적 및 비재귀적 직접 구성법이 존재하지만, NMDS 행렬에 대한 재귀적 직접 구성법은 존재하지 않았습니다.
  • NMDS 행렬에 대한 대칭적 (Involutory, 즉 $A^2 = I$) 구성 방법도 부재했습니다.
  • 기존 구성법 (Cauchy, Vandermonde 기반) 은 주로 MDS 코드에 집중되어 있어 NMDS 특성을 직접적으로 제어하기 어려웠습니다.

2. 방법론 (Methodology)

저자들은 **일반화된 Vandermonde 행렬 (Generalized Vandermonde Matrices)**과 **伴侶 행렬 (Companion Matrices)**을 핵심 도구로 활용하여 새로운 구성 알고리즘을 개발했습니다.

가. 재귀적 구성 (Recursive Constructions)

• 伴侶 행렬 기반: 다항식 $g(x)$의 근을 이용하여伴侣 행렬 $C_g$를 정의하고, $C_g^m$이 MDS 또는 NMDS 행렬이 되기 위한 조건을 도출했습니다.
• 일반화된 Vandermonde 행렬 활용: $C_g$가 대각화 가능할 때, 이를 Vandermonde 행렬 $V$와 대각 행렬 $D$를 사용하여 $C_g = VDV^{-1}$로 표현합니다. 이를 통해 생성 행렬 $G'$의 부분 행렬의 랭크 조건을 분석하여 NMDS 조건 (특정 선형 종속성 유도) 을 만족하는 다항식을 구성했습니다.
  • NMDS 조건: 특정 부분 집합의 근의 합이 0 이 되도록 ($\sum \theta^{r_i} = 0$) 하여 선형 종속성을 인위적으로 생성하되, 다른 조건들은 만족하도록 설계했습니다.
  • MDS 조건: 모든 부분 집합의 합이 0 이 아니도록 조건을 설정했습니다.

나. 비재귀적 구성 (Non-recursive Constructions)

• 일반화된 Vandermonde 행렬 ($V^\perp(x; I)$): 지수 집합 $I$를 $\{1\}$, $\{n-1\}$, $\{1, n\}$ 등으로 제한하여 행렬식을 계산하고, 이를 기반으로 두 개의 일반화된 Vandermonde 행렬 $V_1, V_2$를 사용하여 $V_1^{-1}V_2$ 형태의 행렬을 구성했습니다.
• 대칭적 (Involutory) 행렬 구성: 유한체 $F_{2^r}$에서 $n$이 짝수일 때, $y_i = l + x_i$와 같은 대칭적인 관계를 부여하여 $V_1^{-1}V_2$가 대칭 행렬이 되도록 조건을 부여했습니다.

3. 주요 기여 (Key Contributions)

1. 재귀적 NMDS 행렬의 직접 구성: 문헌상 최초로 재귀적 NMDS 행렬을 구성하는 방법을 제안했습니다. (伴侶 행렬 기반, Theorem 10, Lemma 11)
2. 재귀적 MDS 행렬의 새로운 구성: 기존에 알려진 방법과 다른 새로운 재귀적 MDS 구성법을 제시했습니다. (Theorem 11)
3. 일반화된 Vandermonde 행렬을 통한 비재귀적 구성: $I=\{1\}, \{n-1\}, \{1, n\}$인 일반화된 Vandermonde 행렬을 활용하여 MDS 및 NMDS 행렬을 직접 구성하는 방법론을 정립했습니다. (Theorems 12, 13, 15, 16, 17)
4. 대칭적 (Involutory) 행렬의 구성:
   • 대칭적 MDS 행렬: 일반화된 Vandermonde 행렬을 이용한 새로운 구성법 제시. (Corollary 7)
   • 대칭적 NMDS 행렬: 문헌상 최초로 대칭적 NMDS 행렬을 직접 구성하는 방법을 제시했습니다. (Corollary 8) 이는 암호화 및 복호화 과정에서 동일한 행렬을 사용할 수 있어 하드웨어 효율성을 극대화합니다.
5. NMDS 코드 관련 결과의 증명: 문헌에서 널리 인용되지만 증명이 생략되어 있던 NMDS 코드에 대한 여러 '속설 (Folklore results)'에 대한 엄밀한 수학적 증명을 제공했습니다. (Theorem 4, Lemma 2 등)

4. 결과 (Results)

• 이론적 검증: 제안된 구성 방법들이 유한체 위에서 MDS 및 NMDS 행렬의 정의 (단일성 조건, 최소 거리 조건 등) 를 만족함을 수학적 증명을 통해 입증했습니다.
• 구체적 예시: $F_{2^4}$, $F_{2^8}$ 등 다양한 유한체에서 구체적인 다항식과 행렬 예시를 들어 제안된 방법의 실현 가능성을 시연했습니다.
• 표 1 비교: 기존 문헌 (Cauchy, Vandermonde 기반, 검색 기반 등) 과 비교하여, 제안된 방법이 재귀적 NMDS와 대칭적 NMDS 분야에서 유일한 직접 구성법임을 명확히 했습니다.

5. 의의 및 중요성 (Significance)

• 경량 암호 설계의 확장: NMDS 행렬은 MDS 행렬보다 구현 비용이 낮아 경량 암호 (IoT, RFID 등) 에 적합합니다. 이 논문의 재귀적 및 대칭적 NMDS 구성법은 이러한 환경에서 고효율 확산 계층을 설계할 수 있는 새로운 도구를 제공합니다.
• 구현 효율성: 대칭적 (Involutory) 행렬은 암호화와 복호화에 동일한 행렬을 사용하므로, 하드웨어 면적과 전력 소모를 줄이는 데 결정적인 이점이 있습니다.
• 이론적 기여: NMDS 코드에 대한 수학적 기초를 다지고, 일반화된 Vandermonde 행렬의 대수적 구조를 암호학적으로 활용하는 새로운 패러다임을 제시했습니다.
• 미래 방향: 제안된 행렬 클래스에 대한 구체적인 하드웨어 구현 비용 (면적, 지연 시간) 을 평가하기 위한 최적화 연구의 기초를 마련했습니다.

요약하자면, 이 논문은 NMDS 행렬, 특히 재귀적 및 대칭적 NMDS 행렬의 직접 구성 문제를 해결함으로써 경량 암호학의 확산 계층 설계에 중요한 이론적, 실용적 기여를 한 연구입니다.