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

技術要約：ユークリッド空間におけるSVP近似の決定論的NP困難性

問題設定
本論文は、ユークリッド空間における最短ベクトル問題（SVP）の計算複雑性を扱う。具体的には、$\rho$-GapSVP問題、すなわち、整格子の基底と閾値 $d$ が与えられたとき、最短の非ゼロベクトルの長さが $\lambda_2(L) \le d$ であるケース（YES）と、$\lambda_2(L) > \rho d$ であるケース（NO）を判別する問題を調査している（ここで $\rho > 1$ は定数近似因子である）。

本研究以前では、ユークリッドSVPの近似に関する決定論的なNP困難性は、$\rho < \sqrt{2}$ という近似因子に限定されていた。ランダム化された還元を用いることで、任意の定数近似因子（Khot [22]）や、さらに準多項式的な近似因子（Haviv and Regev [19]）に対する困難性は確立されていたが、これらをユークリッド空間において決定論的に導出（デランダム化）することは、10年以上にわたり未解決の課題であった。ユークリッドノルムは、符号理論におけるハミング距離とは異なり、テンソル積の下での乗法特性を持たないことが、主要な障壁となっていた。

手法
著者は、任意の定数 $\rho > 1$ に対して、NP完全問題からユークリッド $\rho$-GapSVPへの決定論的多項式時間一対一還元を構成する。証明戦略は、以下の3つのコンポーネントに基づいている。

1. 決定論的バイナリ $\ell_1$ ギャップ構成:
   著者はまず、$\ell_1$ ノルムにおいて「バイナリ・ギャップ」を持つ格子を構成する。これには、Gap Exact Set Coverからの決定論的還元と、リード・ソロモン局所高密度格子（Reed–Solomon locally dense lattice）のガジェットを組み合わせる手法を用いる。

   • セットカバーの還元（Micciancio [27] および Bennett–Peikert [9] に基づく）は、YESインスタンスでは低重みのバイナリベクトルを生み出し、NOインスタンスではすべての非ゼロ整数ベクトルが高支持（high support）を持つように強制するソースインスタンスを作成する。
   • リード・ソロモン・ガジェット（著者の以前の研究 [36] から派生）は、任意の指定されたバイナリ射影に対して、特定の剰余類に含まれるバイナリかつ格子の最小値の半分をわずかに上回る $\ell_1$ ノルムを持つ格子ベクトルが存在することを保証する。
   • これらをブロック埋め込みによって組み合わせることで、以下の性質を持つ格子 $L$ と閾値 $d$ を生成する。
     • YES: $y \in L \cap \{0,1\}^N$ かつ $\|y\|_1 < d$ を満たすバイナリベクトル $y$ が存在する。
     • NO: すべての非ゼロ $x \in L$ に対して、$\|x\|_1 \ge \eta d$ である（ここで $1 < \eta < 2$ は固定された定数）。

2. 正確な $\ell_1$ テンソル恒等式:
   極めて重要な理論的貢献は、整格子の最小 $\ell_1$ ノルムがテンソル積の下で乗法的であることを証明した点にある。

   • ユークリッドノルム（$\ell_2$）の場合、テンソル積格子 $L_1 \otimes L_2$ における最短ベクトルは必ずしも純粋なテンソルになるとは限らず（したがって $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$）、一方で $\ell_1$ 最小値は以下の正確な恒等式を満たす：
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • この結果は、格子の $\ell_1$ 最小値を、整数剰余環上の商符号の最小リー重み（minimum Lee weight）に関連付けることで確立される。著者は、完全ランク格子のリー重みのOjiro–Matsui積公式 [29] を利用して、この乗法性を証明し、補完議論を通じて任意のランクの格子へと拡張している。

3. テンソル増幅:
   著者は、ステップ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$ を入力サイズに応じて成長させることを許容することで、以前はランダム化された還元によってのみ知られていた次元依存の困難性レジームの決定論的版本を導出している：
  • 準多項式時間還元: 因子の $2^{(\log n)^{1-\varepsilon}}$ に対する困難性。
  • 劣指数時間還元: 因子の $n^{c/\log \log n}$ に対する困難性。

意義と主張
本論文は、ユークリッド空間における任意の定数近似のSVPのNP困難性を証明する際に、ランダム性を必要としないことを示すことで、格子理論における長年の未解決問題を解決したと主張している。

• デランダム化: 本研究は、ユークリッド空間における決定論的な局所高密度格子を構築することの困難さゆえに、これまで困難であったユークリッドSVPの還元を成功裏にデランダム化した。
• 手法の転換: 証明は、Khotの構成を一行ずつデランダム化しようとするものではない。代わりに、新しい構造的アプローチを導入している。すなわち、決定論的なバイナリ・ガジェットを用いて $\ell_1$ ギャップを作り出し、その後、$\ell_1$ ノルムの正確な乗法性を利用して、このギャップをユークリッド領域へと増幅させる手法である。
• 符号理論とのアナロジー: 本論文は、格子問題と符号理論の間の深い関連性を強調している。線形符号の最小ハミング距離がテンソル積の下で乗法的であるのと同様に、整格子の最小 $\ell_1$ ノルム（リー計量による）もこの特性を共有しており、これにより符号理論の増幅技術を格子へと転送することが可能になる。
• 先行研究との比較: 著者は、Hair and Sahai [18] が最近、PCPアプローチと劣指数時間還元を用いて任意の定数に対する決定論的困難性を得たことに触れている。本論文は、多項式時間の還元によってこの結果を実現している点で、それを改善している。

結論として、テンソル増幅法には自然な限界（固定された $\varepsilon$ に対して $n^\varepsilon$ ではなく $n^{o(1)}$ を与える）があるものの、ユークリッドSVPおよびすべての有限 $\ell_p$ ノルムに対する定数因子の決定論的困難性を確立することに成功している。