Euclidean SVP is deterministically NP-hard to approximate within any constant factor

기술 요약: 유클리드 SVP 근사의 결정론적 NP-난해성

문제 정의
본 논문은 유클리드 최단 벡터 문제(SVP)의 계산 복잡도를 다룬다. 구체적으로, 정수 격자 기저와 임계값 $d$가 주어졌을 때, 최단 0이 아닌 벡터의 길이가 $\lambda_2(L) \le d$인 경우(YES)와 $\lambda_2(L) > \rho d$인 경우(NO)를 구별하는 $\rho$-GapSVP 문제를 조사한다. 여기서 $\rho > 1$은 상수 근사 계수이다.

이 연구 이전에는 유클리드 SVP 근사의 결정론적 NP-난해성이 $\rho < \sqrt{2}$인 경우로 제한되어 있었다. 무작위적 환원을 통해 임의의 상수 계수(Khot [22]) 및 거의 다항식 계수(Haviv와 Regev [19])에 대한 난해성은 확립되었으나, 유클리드 공간에서의 이러한 결과들을 결정론적으로 도출하는 것은 10년 넘게 미해결 과제로 남아 있었다. 코딩 이론의 해밍 거리와 달리, 유클리드 노름은 텐서 곱 하에서 곱셈적 성질(multiplicative properties)이 부족하다는 점이 주요 장애물이었다.

방법론
저자는 임의의 상수 $\rho > 1$에 대하여, NP-완전 문제로부터 유클리드 $\rho$-GapSVP로 가는 결정론적 다항 시간 일대일 환원(many-one reduction)을 구성한다. 증명 전략은 세 가지 핵심 요소에 의존한다:

1. 결정론적 이진 $\ell_1$ 간극(Gap) 구성:
   저자는 먼저 $\ell_1$ 노름에서 "이진 간극"을 갖는 격자를 구성한다. 저자는 Gap Exact Set Cover로부터의 결정론적 환원과 Reed–Solomon 국소 밀집 격자(locally dense lattice) 가젯을 결합한다.

   • Set Cover 환원(Micciancio [27] 및 Bennett–Peikert [9]에 기반함)은 YES 인스턴스는 낮은 가중치를 가진 이진 벡터를 생성하고, NO 인스턴스는 모든 0이 아닌 정수 벡터가 높은 서포트(support)를 갖도록 강제하는 소스 인스턴스를 생성한다.
   • Reed–Solomon 가젯(저자의 이전 연구 [36]에서 유도됨)은 임의의 규정된 이진 투영에 대해, 특정 코셋(coset) 내에 이진이며 $\ell_1$ 노름이 격자의 최소값보다 약간 큰 격자 벡터가 존재함을 보장한다.
   • 이를 블록 임베딩(block embedding)을 통해 결합함으로써, 다음과 같은 격자 $L$과 임계값 $d$를 생성한다:
     • YES: $L \cap \{0,1\}^N$에 속하는 이진 벡터 $y \in L$가 존재하며, $\|y\|_1 < d$이다.
     • NO: 모든 0이 아닌 $x \in L$에 대하여, $\|x\|_1 \ge \eta d$이다. 여기서 $1 < \eta < 2$는 고정된 상수이다.

2. 정확한 $\ell_1$ 텐서 항등식:
   본 논문의 중요한 이론적 기여는 정수 격자의 최소 $\ell_1$ 노름이 텐서 곱 하에서 **곱셈적(multiplicative)**임을 증명하는 것이다.

   • 텐서 곱 격자 $L_1 \otimes L_2$에서 최단 벡터가 순수 텐서(pure tensor)가 아닐 수 있는 유클리드 노름($\ell_2$)과 달리, $\ell_1$ 최소값은 다음의 정확한 항등식을 만족한다:
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • 이 결과는 격자의 $\ell_1$ 최소값을 정수 잔여 환(residue rings) 상의 몫 코드(quotient code)의 최소 리(Lee) 가중치와 연관시킴으로써 확립된다. 저자는 완전 계수 격자에 대한 Lee 가중치의 Ojiro–Matsui 곱 공식 [29]을 활용하여 이 곱셈성을 증명하고, 완비화(completion) 논증을 통해 이를 임의의 계수 격자로 확장한다.

3. 텐서 증폭(Tensor Amplification):
   저자는 단계 1에서 구성된 기본 격자 $L$의 $t$-중 텐서 거듭제곱을 취한다.

   • YES 케이스에서, 벡터 $y^{\otimes t}$는 이진성을 유지한다. 이진 벡터는 $\|v\|_2^2 = \|v\|_1$을 만족하므로, 유클리드 길이는 $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$가 된다.
   • NO 케이스에서, $\ell_1$ 노름의 곱셈적 성질은 $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$임을 보장한다. 정수 벡터에 대한 부등식 $\|x\|_2 \ge \|x\|_1^{1/2}$를 사용하면, 유클리드 길이는 $(\eta d)^{t/2}$보다 낮게 하한이 설정된다.
   • 결과적으로 발생하는 근사 간극은 $\eta^{t/2}$이다. 충분히 큰 상수 $t$를 선택함으로써, 이 간극은 원하는 임의의 상수 $\rho$를 초과할 수 있다.

주요 결과

• 정리 1.2 (주 정리): 모든 상수 $\rho > 1$에 대하여, 유클리드 $\rho$-GapSVP는 결정론적 다항 시간 일대로 환원을 통해 NP-난해이다. 이는 Khot의 무작위적 정리에 대한 결정론적 대응물을 제공한다.
• 정리 1.4 (모든 유한 노름): 이 결과는 모든 고정된 유한 $\ell_p$ 노름($1 \le p < \infty$)으로 확장된다. 임의의 고정된 $p$와 상수 $\rho > 1$에 대하여, $\rho$-GapSVP$_p$는 결정론적으로 NP-난해이다.
• 정리 1.5 (차원 의존적 영역): 텐서 차수 $t$가 입력 크기에 따라 증가하도록 허용함으로써(고정된 상수가 아니라), 저자는 기존에 무작위적 환으로만 알려졌던 차원 의존적 난해성 영역에 대한 결정론적 버전을 도출한다:
  • 준다항 시간(Quasipolynomial-time) 환원: 계수 $2^{(\log n)^{1-\varepsilon}}$에 대한 난해성.
  • 아지수간(Subexponential-time) 환원: 계수 $n^{c/\log \log n}$에 대한 난해성.

의의 및 주장
본 논문은 임의의 상수 계수에 대해 유클리드 SVP 근사의 NP-난해성을 증명하는 데 있어 무작위성을 제거함으로써, 격자 기반 복잡도 분야의 오랜 미해결 과제를 해결했다고 주장한다.

• 결정론적 도출(Derandomization): 본 연구는 유클리드 공간에서 결정론적인 국소 밀집 격자를 구성하는 어려움 때문에 이전의 시도들이 난항을 겪었던 유클리드 SVP 근사의 결정론적 환원을 성공적으로 수행했다.
• 방법론적 전환: 이 증명은 Khot의 구성을 한 줄씩 결정론적으로 바꾸려는 시도가 아니다. 대신, 새로운 구조적 접근 방식을 도입한다: 즉, 결정론적 이진 가젯을 사용하여 $\ell_1$ 간극을 만들고, $\ell_1$ 노름의 정확한 곱셈성을 활용하여 이 간극을 유클리드 영역으로 증폭시키는 것이다.
• 코딩 이론과의 유사성: 본 논문은 격자 문제와 코딩 이론 사이의 깊은 연결을 강조한다. 선형 코드의 최소 해밍 거리가 텐서 곱 하에서 곱셈적인 것과 마찬가지로, 저자는 정수 격자의 최소 $\ell_1$ 노름(Lee 메트릭을 통해) 또한 이러한 성질을 공유함을 보여줌으로써 코딩 이론의 증폭 기법을 격자로 전이할 수 있음을 보여준다.
• 기존 연구와의 비교: 저자는 Hair와 Sahai [18]가 최근 임의의 상수에 대한 결정론적 난해성을 얻었으나, 그들의 결과는 PCP 접근 방식과 아지수간 시간 환원에 의존했음을 언급한다. 본 논문은 다항 시간 환원을 통해 이보다 개선된 결과를 달라는 점을 명시한다.

본 논문은 텐서 증폭 방법이 자연스러운 한계(고정된 $\varepsilon$에 대해 $n^\varepsilon$가 아닌 $n^{o(1)}$의 계수를 생성함)를 가지고 있지만, 유클리드 $\rho$-GapSVP 및 모든 유한 $\ell_p$ 노름에 대한 결정론적 상수 계수 근사 난해성을 성공적으로 입증했다고 결론짓는다.