A New Class of Linear Codes

기술 요약: 새로운 부류의 선형 코드

문제 정의
본 논문은 유한체 $\mathbb{F}_r$ 상에서 길이 $n$을 가지며 상대 거리가 $1/2$에 점근적으로 가까운(구체적으로 $d \approx n/2$) 선형 코드의 구축 문제를 다룬다. 최소 거리 $d$가 대략 $n/2$인 이진 코드는 매우 기초적이지만, 플로트킨 경계(Plotkin bound)는 $d \ge n/2$일 때 이러한 코드의 크기를 극도로 작게 제한한다. $d < n/2$이지만 $n - 2d = \Omega(\sqrt{n})$인 영역에서, 기존의 최선책은 역사적으로 비선형 델사르테-고텔스(Delsarte–Goethals) 코드였다. 이러한 코드들은 효과적이기는 하나, 길이가 증가함에 따라 부호율이 지수적으로 감소하는 문제를 겪는다. 저자들은 상대 거리 $1/2$의 영역을 유지하면서도 델사르테-고텔스 코드보다 코드 크기(부호율) 측면에서 지수적인 개선을 달성하는 선형 코드를 구축하는 것을 목표로 한다.

방법론
저자들은 곱셈적 문자의 합(multiplicative character sums)과 초타원 곡선(superelliptic curves) 이론에 기반한 **섀도 코드(Shadow Codes)**라 명명된 구축법을 도입한다. 핵심 전략은 다음과 같다:

1. 체 설정: 보조 체 $\mathbb{F}_q$($q$는 소수의 거듭제곱)를 활용하여 더 작은 기저 체 $\mathbb{F}_r$($r$은 $q-1$을 나누는 소수) 상의 코드를 구축한다.
2. 초타원 곡선: $\mathbb{F}_q$ 상의 단항 기약 다항식 집합 $P = \{p_1, \dots, p_L\}$을 선택한다.
3. 문자 매핑: 메시지 벡터 $(v_1, \dots, v_L) \in \mathbb{F}_r^L$에 대해, 코드의 성분이 이 다항식들의 곱에 대한 차수 $r$의 곱셈적 문자 $\chi_r$을 평가하여 결정되도록 정의한다. 구체적으로, 코드의 $x \in \mathbb{F}_q$에서의 성분은 $\phi_r(\prod p_i(x)^{v_i})$이다 (여기서 $\phi_r$은 단위근을 $\mathbb{F}_r$의 가법군으로 매핑하는 동형 사상이다).
4. 기하학적 해석: "섀도(shadow)"는 초타원 곡선 $y^r = f(x)$ (여기서 $f$는 다항식들의 곱)를 $x$축 위로 투영한 것을 의미한다. 코드워드의 영점은 $f(x)$가 $r$제곱수가 되는 $x$좌표들에 대응한다.
5. **연결(Concatenation): 파라미터를 더욱 개선하기 위해, 저자들은 이러한 섀도 코드를 리드-솔로몬(Reed-Solomon, RS) 코드와 연결하는 방안을 제안한다.

주요 기여 및 결과

• 섀도 코드의 구축: 본 논문은 길이 $n=q$, 차원 $k \approx q^{1/2-\epsilon}$, 최소 거리 $d \ge \frac{r-1}{r}q - O(q^{1-\epsilon})$를 갖는 $\mathbb{F}_r$-선형 코드의 존재성을 증명한다.

  • 정리 I.1: 임의의 $\epsilon \in (0, 1/2)$와 충분히 큰 $q$에 대해 이러한 코드의 존재성을 확립한다.
  • 따름정리 I.2: 이를 이진 코드($r=2$)에 특화하여, 파라미터 $[q, \lfloor q^{1/2-\epsilon} \rfloor, d]$와 $d \ge q/2 - 2q^{1-\epsilon}$를 도출한다.

• 델사르테-고ethals 코드에 대한 지수적 개선:

  • 저자들은 $n - 2d = \Omega(\sqrt{n})$인 영역에서, 선형 섀도 코드가 델사르테-고텔스 코드보다 코드 크기가 지수적으로 더 크다는 것을 입증한다.
  • 명제 III.2: 일련의 파라미터 시퀀스에 대해, 섀도 코드의 크기의 로그와 델사르테-고텔스 코드의 로그의 비가 $\Omega(2^{m\delta/2}/m^2)$임을 보여줌으로써 지수적 이득을 확인한다. 델사르테-고텔스 코드와 달리, 새로운 코드들은 선형이며 복호 알고리즘을 갖는다.

• 연결을 통한 성능 향상:

  • RS-Shadow 연결 (정리 V.1): 리드-솔로몬 코드와 섀도 코드를 연결함으로써, 상대 거리가 $1/2$에 점근적으로 수렴하는 길이 $N = q^{n+1}$, 차원 $N^{1 - \frac{1}{2n+2} - \frac{2\epsilon}{n+1}}$인 코드를 달성한다.
  • RS-RM과의 비교: 표준적인 연결 구조에서 내부 리드-뮬러(RM) 코드를 섀도 코드로 대체할 경우, 섀도 코드가 1차 RM 코드보다 더 큰 차원을 지원하기 때문에 동일한 길이와 거리 영역에서 훨씬 높은 부호율을 얻을 수 있다고 논문은 주장한다.

• 섀도 코드의 제곱과 암호학:

  • 정리 VI.1: $q$가 차원 $L$에 비해 충분히 클 때, 섀도 코드의 제곱(슈어 곱(Schur product) 하에서)의 차원이 $L(L+1)/2$임을 증명한다. 이는 무작위 코드의 거동을 모사한다.
  • 의의: 높은 차원의 제곱을 갖는 코드는 특정 대수적 공격에 저항력이 있어 암호학적 응용(예: 서명 스킴)에 가치가 있다. 반면, 본 논문은 연결된 RS-RM 코드의 제곱의 차원이 보편적 경계에 비해 무시할 수 있을 정도로 작음을 보여준다(정리 VI.4). 이는 해당 코드들이 그러한 응용에 적합하지 않음을 나타낸다.

• 복호 알고리즘:

  • 섹션 VII: 본 논문은 Swastik Kopparty의 방법을 기반으로 한 이진 섀도 코드의 효율적인 복호 알고리즘을 제시한다. 이는 선형 대수와 다항식 분해를 활용하여, 이차 문자의 노이즈가 섞인 평가값으로부터 제곱 없는(square-free) 메시지 다항식을 복구하는 과정을 포함한다.

• 정수론에 대한 응용:

  • 섹션 IV: 저자들은 코딩 이론적 경계(Plotkin 및 McEliece)를 적용하여 지수 합(exponential sums)에 관한 새로운 결과를 도출하며, 특히 유한체 상의 특정 문자 합의 최댓값에 대한 하한을 확립한다.

의의 및 주장
본 논문은 상대 거리 $1/2$의 영역에서 기존의 델사르테-고텔스 비선형 코드를 능가하는 새로운 부류의 선형 코드의 존재성을 구성적으로 증명했다고 주장한다. 주요 의의는 상대 거리 $1/2$를 유지하면서 코드 크기(부호율)의 지수적 개선을 이루어냈으며, 선형성을 유지하고 명시적인 복호 알고리즘을 제공한다는 점에 있다. 또한, 이 코드들의 대수적 구조(특히 제곱의 거동)가 암호학적 응용에 유망하다는 점을 강조하며, 이는 RS-RM과 같은 다른 연결 코드 가문과 차별화되는 지점이다. 본 연구는 코딩 이론과 정수론을 연결하여 문자 합에 대한 새로운 경계를 도출함으로써 두 분야를 잇는 가교 역할을 한다.