The Closure of LCD-to-GI Reductions via Generalized Inner Products

기술 요약: 일반화 내적을 통한 LCD-to-GI 축소 폐쇄

1. 문제 제기

선형 부호에 대한 치환 동치 문제 (PEP) 는 두 개의 주어진 선형 부호가 좌표 치환을 통해 동일한지 여부를 묻는 문제입니다. 이 문제는 선형 부호의 분류와 코드 기반 암호학 (예: LESS 서명 체계 및 SPECK 체계) 의 보안 분석에 모두 근본적입니다.

PEP 의 복잡성은 그래프 동형 (GI) 문제와 밀접하게 연관되어 있습니다. PEP 은 일반적으로 어렵다고 간주되지만, Bardet 등 [3] 의 중요한 돌파구는 선형 상보적 이중 (LCD) 부호 (자명한 핵을 가진 부호, 즉 $C \cap C^\perp = \{0\}$) 에 대한 PEP 이 다항 시간 내에 GI 로 축소됨을 보여주었습니다. 이 축소는 직교 사영자 $\Pi_C = G^T(GG^T)^{-1}G$ 를 통해 LCD 부호를 가중 그래프로 매핑합니다.

그러나 이 방법은 그람 행렬 $GG^T$ 가 비특이적이어야 한다는 점에 의존하므로 LCD 부호에 국한됩니다. 자명하지 않은 핵을 가진 부호 (여기서 $\dim(\text{Hull}(C)) \ge 1$) 는 이 특정 구성으로 처리할 수 없습니다. 본 논문에서 다루는 핵심 질문은 다음과 같습니다: 직교 사영자 방법을 얼마나 확장할 수 있는가? 구체적으로, 다른 이차 형식을 사용하여 자명하지 않은 핵을 가진 부호로 일반화할 수 있는가, 그리고 만약 그렇다면 그러한 축소의 정확한 구조적 한계는 무엇인가?

2. 방법론

저자들은 표준 내적을 구조 행렬 $M$ 으로 표현되는 임의의 비퇴화 대칭 이차 형식으로 일반화합니다.

• 일반화 사영자: 그들은 $M$-이중 부호 $C^{\perp_M}$ 과 $M$-핵 $\text{Hull}_M(C)$ 를 정의합니다. ($M$-LCD 부호, 즉 $\text{Hull}_M(C) = \{0\}$ 인 경우) 일반화 직교 사영자를 구성합니다:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• 축소 조건: 축소의 핵심은 $P$ 가 치환 행렬일 때 $\Pi_{CP, M} = P^T \Pi_{C,M} P$ 라는 항등식에 의존합니다. 이 항등식은 두 부호가 치환 동치라면 그들의 사영자가 가중 그래프로서 동형임을 보장합니다.
• $M$ 의 특성화: 저자들은 모든 치환 $P$ 에 대해 $P M P^T = M$ (또는 그 스칼라 배) 을 만족하는 구조 행렬 $M$ 이 무엇인지 조사합니다. 이는 사영자가 치환 하에서 올바르게 동작하도록 하기 위해 필요합니다.
• 열거 및 알고리즘: 2 차 형식에 대한 문자 합 (특히 Weil 정리) 을 사용하여 저자들은 축소 가능한 부호의 수에 대한 정확한 열거 공식을 유도합니다. 또한 주어진 부호 쌍을 GI 로 축소하기 위한 적합한 $M$ 을 찾는 다항 시간 알고리즘을 구성합니다.

3. 주요 기여 및 결과

A. 유효한 구조 행렬의 특성화 (정리 3.5)
본 논문은 직교 사영자 방법이 유효한 축소 ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) 를 산출하기 위해서는 구조 행렬 $M$ 이 다음 형태를 가져야 함을 증명합니다:
$$M = aI + bJ$$
여기서 $I$ 는 단위 행렬, $J$ 는 모든 성분이 1 인 행렬이며, $a, b \in \mathbb{F}_q$ 는 비퇴화 조건 ($a \neq 0$ 및 $a + nb \neq 0$) 을 만족합니다. 이 축소를 허용하는 다른 비퇴화 대칭 이차 형식은 존재하지 않습니다. 이는 직교 사영자 접근법의 폐쇄성을 확립합니다: 임의의 이차 형식을 선택하여 방법을 확장할 수 없으며, 그 형식은 단위 행렬과 모든 성분이 1 인 행렬의 선형 결합이어야 합니다.

B. 축소 가능한 부호의 완전한 특성화 (정리 4.5)
저자들은 어떤 부호가 이러한 축소를 허용하는지 정확히 규명합니다:

• 부호 $C$ 가 이 방법을 통해 GI-축소 가능하기 위해서는 다음 중 하나를 만족해야 합니다:
  1. $C$ 가 LCD 부호인 경우 (표준 경우, $M=I$), 또는
  2. $\dim(\text{Hull}(C)) = 1$ 이고 유일한 핵 벡터 $x$ 가 $(x, \mathbf{1}) \neq 0$ 을 만족하는 경우 (여기서 $\mathbf{1}$ 은 모든 성분이 1 인 벡터).
• 특성 2: 특성 2 의 체에서는 핵 내의 어떤 벡터에 대해서도 $(x, \mathbf{1}) \neq 0$ 조건이 불가능합니다 ($(x, x) = (x, \mathbf{1})^2 = 0$ 이 $(x, \mathbf{1}) = 0$ 을 의미하기 때문). 따라서 특성 2 에서는 LCD 부호만 축소 가능합니다.
• 더 높은 핵에 대한 불가능성: $\dim(\text{Hull}(C)) \ge 2$ 인 부호는 $M = aI + bJ$ 의 선택과 관계없이 직교 사영자 방법을 통해 축소 불가능함이 증명됩니다.

C. 열거 공식 (정리 5.3)
본 논문은 (홀수 $q$ 에 대해) GI-축소 가능한 $[n, k]_q$ 부호의 수를 세기 위한 정확한 공식을 제공합니다. 이 수는 다음 두 가지의 합입니다:

1. 표준 LCD 부호의 수, $L(n, k, q)$.
2. 좌표 합 조건을 만족하는 핵 차원 1 의 부호 수. 이는 비영 좌표 합을 갖는 등방성 벡터의 수와 특정 판별식을 가진 몫 공간 위의 LCD 부호에 대한 질량 공식을 사용하여 유도됩니다.

D. 축소 알고리즘 (6 절)
다항 시간 알고리즘이 제시됩니다:

1. 핵 차원을 확인합니다. $\ge 2$ 이면 "GI-축소 불가"를 출력합니다.
2. LCD 인 경우 $M=I$ 를 사용합니다.
3. 핵 차원이 1 인 경우, $M = I + bJ$가 두 부호 모두를$M$-LCD 로 만들도록 스칼라 $b$ 를 탐색합니다.
4. 일반화 사영자를 구성하고 결과적으로 발생하는 그래프 동형 문제를 해결합니다.

4. 중요성 및 주장

본 논문은 직교 사영자 방법의 능력을 완전히 특성화했다고 주장합니다.

• 폐쇄성: 이 특정 기법을 사용하여 Bardet 등의 축소를 큰 핵 ($\ge 2$) 을 가진 부호로 확장하는 문을 definitively 닫습니다. 이 방법이 본질적으로 핵 차원이 최대 1 인 부호 (특성 2 에서는 LCD 부호만) 로 제한됨을 증명합니다.
• 구조적 한계: 축소가 작동하기 위해 필요한 특정 대수적 구조 ($M = aI + bJ$) 를 식별하여, 다른 대칭 이차 형식은 이러한 매핑을 지원할 수 없음을 보여줍니다.
• 암호학적 함의: 이 결과들은 코드 기반 암호 체계 (SPECK 등) 에서 매개변수를 선택하기 위한 기준을 제공하여, 부호들이 핵 차원 $\ge 2$ 를 갖도록 보장함으로써 이러한 특정 GI-축소 공격 벡터의 범위를 벗어날 수 있게 합니다.

저자들은 다음과 같은 열린 질문으로 결론을 맺습니다: 직교 사영자에 기반하지 않는 다른 축소 전략이 $\dim(\text{Hull}(C)) \ge 2$ 인 부호에 대한 PEP 를 GI 로 매핑할 수 있는지, 아니면 그러한 축소가 증명적으로 불가능한지 여부입니다.