Mind the Gap? Not for SVP Hardness under ETH!

1. 問題設定と背景

背景:
格子問題、特に最短ベクトル問題（SVP）と最近傍ベクトル問題（CVP）は、ポスト量子暗号の安全性の基盤となっています。これらの問題の近似アルゴリズムの存在可能性は、P $\neq$ NP だけでなく、より強力な「指数時間仮説（ETH）」や「ギャップ指数時間仮説（Gap-ETH）」の下で研究されてきました。

• ETH: 3SAT は $2^{o(n)}$ 時間で解けないという仮説。
• Gap-ETH: 3SAT の近似（満足可能な場合と、ほとんど満足できない場合の区別）が $2^{o(n)}$ 時間で解けないという、より強い仮説。

これまでに、SVP や CVP の近似困難性は Gap-ETH の下で証明されていましたが、ETH のみで証明された例は限られていました。特に、$p > 2$ における SVP の ETH 下での困難性は未解決でした。

目的:
Gap-ETH を仮定せずに、ETH のみから、$\ell_p$ ノルムにおける近似 SVP（SVP$_{p,\gamma}$）、近似 CVP（CVP$_{p,\gamma}$）、および有界距離復号（BDD$_{p,\alpha}$）の指数時間下での困難性を証明すること。

---

2. 主要な貢献と結果

著者らは、Bitansky ら [BHIRW24] による「3SAT から gap-MAXLIN への多項式時間還元」という最近のブレイクスルーを基盤とし、以下の結果を導き出しました。

A. CVP$_{p,\gamma}$ の ETH 下での困難性

• 結果: 任意の $p \in [1, \infty)$ に対して、ある明示的な定数 $\gamma > 1$ が存在し、CVP$_{p,\gamma}$ は ETH が偽でない限り $2^{o(n)}$ 時間で解けない。
• 手法: 3SAT から gap-MAXLIN への還元を用い、それを決定論的に CVP$_{p,\gamma}$ に還元する。
• 特徴: 還元は確率的要素を含まず、整数格子上の線形方程式系を直接 CVP インスタンスに変換する。

B. SVP$_{p,\gamma}$ の ETH 下での困難性（主要な貢献）

• 結果: 任意の $p \in (2, \infty)$ に対して、ある明示的な定数 $\gamma > 1$ が存在し、SVP$_{p,\gamma}$ は確率的ETH が偽でない限り $2^{o(n)}$ 時間で解けない。
• 意義: これは $p > 2$ における SVP の ETH 下での最初の困難性結果である（$p=2$ や $p=\infty$ の場合の既存結果を補完・拡張）。
• 手法:
  1. CVP$_{p,\gamma}$ から SVP$_{p,\gamma}$ への確率的還元を構築。
  2. そのために、整数格子 $\mathbb{Z}^n$ における新しい幾何学的性質を発見・証明した。
  3. 局所高密度性（Locally Dense）: 原点に近い「短いベクトル」の数よりも、ベクトル $\frac{1}{2}\mathbf{1}_n$（全成分が 1/2）に近いベクトルの数が指数関数的に多いという性質を $p > 2$ で示した。

C. BDD$_{p,\alpha}$ の ETH 下での困難性

• 結果: 任意の $p \in [1, \infty)$ と、$p$ に依存する明示的な閾値 $\alpha^\ddagger_p$ に対して、$\alpha > \alpha^\ddagger_p$ ならば BDD$_{p,\alpha}$ は ETH 下で $2^{o(n)}$ 時間で解けない。
• 改善: 既存の Gap-ETH 下での結果（$\alpha$ の閾値）を維持しつつ、仮定を Gap-ETH から ETH へ緩和した。

---

3. 技術的アプローチと手法

3.1. MAXLIN から CVP への還元

• MAXLIN: 有限体上の線形方程式系で、可能な限り多くの式を満たす変数を見つける問題。
• 構成: 行列 $B = [M \mid 2I_m]$ とターゲットベクトル $t = v$ を用いて格子を定義する。
  • $2I_m$ を追加することで、格子点とターゲットの距離計算が mod 2 の世界（$\mathbb{F}_2$）に制限されるようにする。
  • YES インスタンス（多くの式が満たされる）ではターゲットに近い格子点が存在し、NO インスタンスでは遠くなる。これにより、CVP$_{p,\gamma}$ のギャップが生成される。

3.2. SVP への還元と「局所高密度ガジェット」

SVP は「原点に近い最短ベクトル」を探す問題であるため、CVP のような「任意のターゲット」への還元は単純ではない。著者らは以下の戦略をとった。

1. ガジェットの設計:

   • 整数格子 $\mathbb{Z}^d$ とターゲット $t^\dagger = \frac{1}{2}\mathbf{1}_d$ を用いる。
   • この構成では、ターゲットの偶数倍（$2\ell t^\dagger$）は整数ベクトルとなり、格子に含まれる。これにより、CVP から SVP への還元時に生じる「偶数倍のターゲット」の問題を回避できる。

2. Theta 関数と不等式の証明:

   • 格子点の数を評価するために Theta 関数 $\Theta_p(\tau, t) = \sum_{z \in \mathbb{Z}} \exp(-\tau |z-t|^p)$ を用いる。
   • 核心となる定理: $p > 2$ に対して、ある $\tau > 0$ が存在し、$\Theta_p(\tau, 1/2) > \Theta_p(\tau, 0)$ が成り立つことを証明した。
   • 証明の工夫:
     • $p=2$ の場合、この不等式は成り立たない（Jacobi の虚数変換により負になることが知られている）。
     • $p > 2$ の場合、Fourier 解析とポアソン和公式（Poisson summation formula）を用いる。
     • 超ガウス関数 $e^{-|z|^{2+\epsilon}}$ の Fourier 変換の漸近展開（[EOR91]）を分析し、ある $\tau$ を選ぶことで、差の級数が正になることを示した。
   • この結果、$\frac{1}{2}\mathbf{1}_d$ 付近の格子点の数が、原点付近の格子点の数よりも指数関数的に多いことが保証される。

3. 格子の疎化（Sparsification）:

   • Khot の手法を借用し、ランダムな超平面で格子を制限（疎化）する。
   • YES インスタンスでは、$\frac{1}{2}\mathbf{1}_d$ 付近の多数のベクトルのうち少なくとも 1 つが生存し、NO インスタンスでは原点付近のベクトルがすべて消滅するようにする。これにより、SVP のギャップが維持される。

3.3. BDD への還元

• CVP から BDD への還元において、ターゲットが格子に十分近いという「約束（Promise）」を満たすようにする。
• 局所高密度なガジェットを用いて、YES 時のターゲット近傍のベクトル数を NO 時のそれよりも指数関数的に大きくし、かつ最短ベクトルの長さも適切に制御することで、BDD の条件を満たす還元を構築した。

---

4. 結果のまとめ

問題	ノルム	仮定	結果
CVP$_{p,\gamma}$	$1 \le p < \infty$	ETH	$2^{o(n)}$ 時間アルゴリズムは存在しない（決定論的還元）
SVP$_{p,\gamma}$	$2 < p < \infty$	確率的 ETH	$2^{o(n)}$ 時間アルゴリズムは存在しない（確率的還元）
BDD$_{p,\alpha}$	$1 \le p < \infty$	確率的 ETH	$\alpha > \alpha^\ddagger_p$ なら $2^{o(n)}$ 時間アルゴリズムは存在しない

• 注記: $p=2$ における SVP の ETH 下での困難性は今回の論文では未解決（Open Problem）として残されているが、$p \in [1, 2)$ の場合は $p=2$ の結果からノルム埋め込み技術により導かれる。

---

5. 意義と影響

1. Gap-ETH と ETH のギャップの埋め合わせ:
   これまで Gap-ETH のみが必須とされていた格子問題の近似困難性結果を、より弱い仮説である ETH のみで導出することに成功した。これは、ETH が実際には Gap-ETH を含む可能性（あるいは少なくとも格子問題の文脈では同等の力を持つ）を示唆する重要な証拠である。

2. 新しい幾何学的性質の発見:
   $p > 2$ における整数格子の「局所高密度性」の証明は、Theta 関数の解析を通じてなされた。これは格子理論における独立した興味深い結果であり、今後の研究に応用される可能性がある。

3. ポスト量子暗号への示唆:
   格子問題の困難性がより弱い仮説（ETH）の下でも保証されることは、これらの問題に基づく暗号方式（LWE など）の安全性に対する理論的根拠をさらに強固にする。特に、サブ指数時間アルゴリズムの存在可能性を排除する仮説が強化された。

4. 手法の一般化:
   MAXLIN からの還元や、Theta 関数を用いた点の数え上げの手法は、他の格子問題や符号理論の問題（線形符号の最小距離問題など）への応用が期待される。

総じて、この論文は計算複雑性理論と格子理論の交差点において、ETH 下での格子問題の困難性に関する理解を飛躍的に進めた重要な研究である。