기술 요약: 곡선 디코딩의 국소성 및 개선된 근접 간격 (Locality of Curve-Decoding and Improved Proximity Gaps)

1. 문제 정의

본 논문은 무작위 앙상블(random ensembles)의 오류 정정 부호에 대한 **근접 간격(proximity gaps)**을 설정하는 문제를 다룹니다. 근접 간격은 대화형 오라클 증명(IOPs) 및 간결한 비대화형 영지식 증명(SNARKs)에 있어 매우 중요한 속성입니다. 비유적으로, 부호 $C$가 차수 $\ell$인 곡선에 대해 근접 간격을 가진다는 것은, 임의의 차수 $\ell$인 곡선 $u(x)$에 대하여, 곡선 위의 모든 점이 $C$와 가깝거나, 혹은 $(1-\varepsilon)$ 분율의 점들이 $C$로부터 멀리 떨어져 있음을 의미합니다.

최근 Guruswami와 Goyal [GG25]의 연구는 서브스페이스 디자인 부호(subspace design codes, 폴디드 리드-솔로몬 및 다중도 부호 포함)에 대해 오차 허용치 $\delta$가 $1-R$($R$은 부호율)에 접근하는 파라미터 범위에서 최적에 가까운 근접 간격을 확립했습니다. 구체적으로, 서브스페이스 디자인 부호의 경우, "가까운" 점들의 수 $\varepsilon q$는 다음과 같이 스케일링됩니다:
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
그러나 [GG25]가 [BCDZ25, LMS25]의 프레임워크를 사용하여 이러한 결과를 무작위 앙상블(무작위 선형 부호, 무작위 평가 지점을 가진 무작위 리드-솔로몬 부호, 그리고 Gallager의 LDPC 앙상블)로 확장했을 때, 파라미터가 저하되었습니다. 결과적으로 도출된 무작위 앙상블에 대한 경계값은 $\ell$에 대한 지수적 의존성을 포함했습니다:
$$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$$
이러한 저하는 $\ell$이 클 때(예: $\ell = \Omega(\log n)$) 심각해지며, 경계값을 비실용적으로 만듭니다. 핵심 질문은 서브스페이스 디자인 부호에서 달성된 최적의 파라미터를 이러한 무작위 앙상블에서도 일치시킬 수 있는지 여부입니다.

2. 방법론: 행 스팬 제약이 있는 LCL 속성 (Row-Span Constrained LCL Properties)

저자들의 주요 기술적 혁신은 행 스팬 제약(row-span constrained) 버전으로 확장된 국소 좌표별 선형(Local Coordinate-wise Linear, LCL) 프레임워크의 확장입니다.

LCL 프레임워크와 과제

LCL 프레임워크([LMS25]에서 도입됨)는 열(column)이 부호(codeword)이고 행(row)이 프로파일 $V$에 의해 정의된 특정 선형 제약을 만족하는 증인(witness) 행렬 $M$의 존재를 통해 부호의 "나쁜" 속성을 특징짓습니다.

• 장애물: 곡선 디코딩 가능성(curve-decodability)(근접 간격을 함의함)이라는 속성은 LCL 속성임이 명확하게 드러나지 않았습니다. 이전 연구 [GG25]는 W-디코딩이라는 대리 속성을 정의함으로써 이를 우회했습니다. W-디코딩은 LCL 프레임워크에 부합했지만, 이 결과를 다시 곡선 디코딩으로 번역하는 과정에서 앞서 언급한 파라미터의 지수적 손실이 발생했습니다.

해결책: 행 스팬 제약

저자들은 곡선 디코딩 가능성이 증인 행렬의 **행 스팬(row-span)**에 대한 제약을 포함하도록 LCL 프레임워크를 확장함으로써 직접 포착될 수 있음을 관찰했습니다.

1. 국소 프로파일 (속성 A): 증인 행렬의 열(부호)은 광범위한 좌표 집합에서 주변의 차수 $\ell$인 곡선 $u(x)$와 일치해야 합니다. 이는 표준적인 국소 프로파일 $V$에 의해 포착됩니다.
2. 행 스팬 제약 (속성 B): 예시의 "나쁨"은 행렬의 $b$개의 열이 단일 차수 $\ell$인 부호 곡선 위에 놓이지 않는 것을 요구합니다. 이는 행렬 구조에 대한 전역적 제약입니다.
   • 저자들은 부분 공간 $U$가 어떤 벡터의 $b$개 좌표도 차수 $\ell$인 다항식 위에 놓이지 않을 때 **$(\ell, A, b)$ 곡선-프리(curve-free)**하다고 정의합니다.
   • 그들은 곡선 디코딩 가능성의 실패가 행 스팬 $U$가 곡선-프리이고 행들이 국소 프로파일 $V$를 만족하는 증인 행렬 $M$의 존재와 동치임을 보여줍니다.

저자들은 LCL 패밀리 $\mathcal{F}$를 (프로파일 $V$, 행 스팬 $U$)의 쌍들의 집합으로 정의함으로써, 곡선 디코딩을 행 스팬 제약이 있는 LCL 속성으로 규정했습니다. 이를 통해 [LMS25]와 [BCDZ25]의 메커니데이션을 중간 단계인 W-디코딩 없이 곡선 디코딩에 직접 적용할 수 있게 되었습니다.

3. 주요 기여

1. 블랙박스 전이 (Black-Box Transference)

본 논문은 서브스페이스 디자인 부호로부터 무작위 앙상블으로의 블랙박스 전이를 확립합니다. 저자들은 임의의 행 스팬 제약이 있는 LCL 속성에 대하여, 무작위 선형 부호(및 관련 앙상블)가 해당 속성을 만족하는 임계율(threshold rate)이 서브스페이스 디자인 부호의 임계율과 본질적으로 동일함을 증명합니다.

• 함의: 서브스페이스 디자인 부호에 대한 향후 모든 파라미터 개선은 무작위 선형 부호, 무작위 리드-솔로몬 부호, 무작위 LDPC 코드에 대해서도 유사한 개선을 자동으로 가져올 것입니다.

2. 개선된 근접 간격 경계값

이 프레임워크를 곡선 디코딩에 적용함으로써, 저자들은 무작위 앙상블에 대해 서브스페이스 디자인 부호에서만 알려졌던 최적의 경계값과 일치하는 개선된 근접 간격 경계값을 도출했습니다.

• 결과: 무작위 선형 부호, 무작위 리드-솔로몬 부호, Gallager의 LDPC 앙상블에 대하여, 근접 간격 파라미터는 다음과 같습니다:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  이는 [GG25]에서 발견된 $\ell$에 대한 지수적 의존성을 제거합니다.

3. 동치 정리 (Equivalence Theorems)

본 논문은 서로 다른 부호 패밀리 간의 행 스팬 제약이 있는 LCL 속성에 대한 동치 정리를 증명합니다:

• 무작위 선형 부호와 무작위 리드-솔로몬 부호는 동일한 임계값을 공유합니다.
• 무작위 LDPC 부호(Gallager 앙상블)는 부호가 좋은 거리(good distance)를 갖는다면(이는 높은 확률로 발생함), 무작위 선형 부호와 동일한 임계값을 공유합니다.

4. 주요 결과

본 논문은 이러한 발견들을 정리 1.2(및 정리 5.3, 5.6, 5.10에 상세 기술)로 공식화합니다. 차수 $R$과 $\ell$을 갖는 무작위 부호 $C$ (선형, 리드-솔로몬, 또는 LDPC)에 대하여:

• 높은 확률로, $C$는 $(\ell, 1-R-2\eta, \varepsilon)$ 근접 간격을 가집니다.
• $\varepsilon$에 대한 조건은 다음과 같습니다:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
• 또한 이 결과는 더 강력한 개념인 상관 일치(Correlated Agreement, CA) 및 **상호 상관 일치(Mutual Correlated Agreement, MCA)**를 동일하게 개선된 파라미터로 확립합니다.

구체적으로, 무작위 LDPC 부호의 경우, Gallager 앙상블에서 충분히 큰 홀수 차수 $s$에 대해 결과가 성립하며, 경계값의 주어(leading term)가 약간 조정될 수 있습니다 (예: 일부 공식에서는 $2n\ell(1-R)/\eta$).

5. 의의 및 주장

저자들은 세 가지 영역에서 본 논문의 의의를 주장합니다:

1. 파라미터 최적화: 무작위 앙상블의 파라미터 저하 문제를 해결하여 서브스페이스 디자인 부호에서 알려진 최적에 가까운 경계값과 일치시켰습니다. 이는 큰 $\ell$을 사용하는 WHIR 및 무작위 앙상블을 사용하는 Blaze 및 Bolt와 같은 프로토콜에 특히 중요합니다.
2. 이론적 통합: 곡선 디코딩이 자연스러운 행 스팬 제약 LCL 속성임을 입증하여, 명시적 부호(서브스페이스 디자인)와 무작위 앙상블의 분석을 단일 프레임워크 아래 통합했습니다.
3. 미래 보장성 (Future-Proofing): 전이의 "블랙박스" 특성 덕분에 무작위 앙상블에 대한 결과는 정체되어 있지 않습니다. 서브스페이스 디자인 부호의 이론이 발전함에 따라 결과도 자동으로 개선될 것입니다.

저자들은 무작위 리드-솔로몬 부호가 최적에 가까운 근접 간격을 달성한다는 것을 보여주었지만, 이러한 동일한 최적 파라미터를 달리는 명시적(explicit) 리드-솔로몬 부호(특정 평가 지점을 가진)를 식별하는 것은 여전히 미해결 과제로 남아 있다고 명시했습니다. 이는 "근접 상(Proximity Prize)" 및 명시적 리스트 디코딩(explicit list-decoding)과 연관된 문제입니다.