Shortest LCD embeddings of binary, ternary and quaternary linear codes

문제 정의
선형 보완 쌍대 코드(LCD 코드)는 부채널 공격 및 결함 주입 공격에 대한 저항성 때문에 부호 이론 및 암호학 분야에서 중요한 연구 영역입니다. 모든 $\mathbb{F}_q$ ($q \ge 4$) 상의 선형 코드가 LCD 코드와 동치라는 사실은 알려져 있으며, $\mathbb{F}_{q^2}$에 대해서도 유사한 결과가 존재하지만, $\mathbb{F}_2$, $\mathbb{F}_3$ 상의 LCD 코드 및 $\mathbb{F}_4$ 상의 헤르미션(Hermitian) LCD 코드의 최소 거리에 대한 경계값은 많은 길이와 차원에 대해 여전히 알려지지 않은 상태입니다. 부호 이론의 핵심 과제는 주어진 길이와 차원에 대해 가장 큰 최소 거리를 결정하는 것입니다. 본 논문은 임의의 선형 코드를 LCD 코드로 임베딩하는 문제, 즉 가장 짧은(최소 길이 증가) 임베딩을 찾는 것을 목표로 하며, 이 방법을 활용하여 새로운 거리 최적 LCD 코드를 구축하는 문제를 다룹니다.

방법론
저자들은 생성 행렬에 최소한의 열을 추가함으로써 주어진 선형 코드 $C$를 LCD 코드 $\tilde{C}$로 임베딩하는 체계적인 접근 방식을 소개합니다. 방법론은 다음과 같이 진행됩니다:

1. 이론적 토대: 주어진 $[n, k]$ 코드 $C$를 LCD 코드로 임베딩하는 데 필요한 최소 열의 수($m$)는 정확히 $C$의 헐(hull)의 차원 $\ell$ (여기서 $\text{Hull}(C) = C \cap C^\perp$)과 같음을 입증합니다. 결과적으로, 가장 짧은 LCD 임베딩의 길이는 $n + \ell$입니다.
2. 구조적 특성화: 저자들은 최단 LCD 임베딩의 생성 행렬을 특성화합니다. 만약 $C$의 생성 행렬 $G$가 헐을 생성하는 부분 $G(\text{Hull}(C))$와 나머지 부분 $A$로 분해된다면, 최단 LCD 임베딩은 다음과 같은 형태의 행렬에 의해 생성됩니다:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   여기서 $D$는 가역적인 $\ell \times \ell$ 행렬이고 $C$는 임의의 $(k-\ell) \times \ell$ 행렬입니다. 본 논문은 헐에 대응하는 행에 가역 행렬을 부가하고 나머지 행에 임의의 행렬을 부가하는 것이 항상 최단 LCD 임베딩을 생성함을 증명합니다.
3. 구축 전략: 저자들은 이 임베딩 방법을 기존의 선형 코드(특히 삼진 및 사진 코드) 중 LCD가 아닌 코드들에 적용합니다. 이러한 기존 코드들의 헐 차원을 계산하고 도출된 구조에 따라 필요한 열을 부가함으로써, 새로운 LCD 코드를 생성합니다.

주요 기여 및 결과
본 논문은 이론적 경계와 구체적인 구성을 모두 제공합니다:

• 이론적 결과:

  • 헐 차원이 $\ell$인 $[n, k]$ 코드의 최단 LCD 임베딩 길이는 $n + \ell$임을 증명합니다.
  • 이러한 최단 임베딩의 가능한 모든 생성 행렬 형태를 특성화하며, 이는 헐을 생성하는 행에 가역 행렬을 부가하는 것과 동치임을 보여줍니다.
  • 코드 $C$의 최단 LCD 임베딩 길이는 그 헐인 $\text{Hull}(C)$의 길이와 동일함을 입증합니다.

• 새로운 코드 구축:
  기존 선형 코드에 최단 LCD 임베딩 방법을 적용하여, 기존의 최소 거리를 개선하는 여러 새로운 LCD 코드를 구축했습니다:

  • 삼진(Ternary) LCD 코드:
    • $[23, 4, 14]$: 알려진 최소 거리를 13에서 14로 개선함.
    • $[23, 5, 12]$: 알려진 최소 거리를 11에서 12로 개선함.
    • $[24, 6, 12]$: 알려진 최소 거리를 11에서 12로 개선함.
    • $[25, 5, 14]$: 알려진 최소 거리를 13에서 14로 개선함.
  • 사진(Quaternary) 헤르미션 LCD 코드:
    • $[21, 10, 8]$: 알려진 최소 거리를 7에서 8로 개선함.

저자들은 새로운 파라미터 $[23, 4, 14]$와 $[23, 5, 12]$에 대해 각각 226개와 38개의 비동치(inequivalent) 코드를 발견했다고 언급했습니다. 이 코드들은 거리 최적이며 현재 BKLC(Best Known Linear Codes) 데이터베이스에 있는 코드들과 동치가 아닙니다.

의의
본 논문은 최단 LCD 임베딩 방법이 다양한 체(field) 상에서 거리 최적 LCD 코드를 찾기 위한 유용한 도구라고 주장합니다. 필요한 열의 수를 정확히 결정하고 그 구조를 특성화함으로써, 이 방법은 기존 선형 코드를 LCD 코드로 변환할 때 최소 거리를 높일 수 있는 구성적 경로를 제공합니다. 결과는 이 접근 방식이 특정 삼진 및 사진 파라미터에 대해 이전에 알려진 코드보다 최소 거리가 1 더 큰 새로운 코드를 성공적으로 산출했음을 보여줍니다.

한계 및 향atic 방향
저자들은 자신들의 접근 방식에 한계가 있음을 인정합니다. 부가되는 가역 행렬 및 임의의 행렬에 대한 탐색 공간이 지나치게 크기 때문에, 주어진 코드에 대해 절대적으로 가장 큰 최소 거리를 산출하는 특정 임베딩을 찾는 것을 보장하기 어렵습니다. 저자들은 향ator 연구가 결과의 최소 거리를 극대화하기 위해 부가되는 행렬을 더 전략적으로 선택하는 방법을 개발하거나, 탐색 공간을 줄이기 위해 부가되는 행렬이 동치 관계에 따라 더 제한될 수 있는지 결정하는 데 집중해야 한다고 제안합니다.