Fugu-MT 論文翻訳(概要): Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell

論文の概要: Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$

arxiv url: http://arxiv.org/abs/2510.16991v1
Date: Sun, 19 Oct 2025 20:17:26 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-25 00:56:39.239159
Title: Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
Title（参考訳）: $\ell_p$ norms for $p>2$における一様SVPとGapSVPの近似の決定論的硬さ
Authors: Yahli Hecht, Muli Safra,
Abstract要約: 我々は、$ell_p$ norm(mathsfSVP_p$)およびUnique-SVP(mathsfuSVP_p$)における最短ベクトル問題に対する近似結果の決定的困難性を確立する。すべての$p > 2$に対して、定数比硬さを証明します: no-time algorithm almosts $mathsfSVP_p$ or $mathsfuSVP_p$ in a ratio of $sqrt2 - o(1)$。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We establish deterministic hardness of approximation results for the Shortest Vector Problem in $\ell_p$ norm ($\mathsf{SVP}_p$) and for Unique-SVP ($\mathsf{uSVP}_p$) for all $p > 2$. Previously, no deterministic hardness results were known, except for $\ell_\infty$. For every $p > 2$, we prove constant-ratio hardness: no polynomial-time algorithm approximates $\mathsf{SVP}_p$ or $\mathsf{uSVP}_p$ within a ratio of $\sqrt{2} - o(1)$, assuming $\textsf{3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$, and, $\textsf{Unambiguous-3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$. We also show that for any $\varepsilon > 0$ there exists $p_\varepsilon > 2$ such that for every $p \ge p_\varepsilon$: no polynomial-time algorithm approximates $\mathsf{SVP}_p$ within a ratio of $2^{(\log n)^{1- \varepsilon}}$, assuming $\text{NP} \nsubseteq \text{DTIME}(n^{(\log n)^\varepsilon})$; and within a ratio of $n^{1/(\log\log(n))^\varepsilon}$, assuming $\text{NP} \nsubseteq \text{SUBEXP}$. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for $\mathsf{uSVP}_p$ under the assumptions $\textsf{Unambiguous-3SAT} \not\subseteq \text{DTIME}(n^{(\log n)^\varepsilon})$ and $\textsf{Unambiguous-3SAT} \not\subseteq \text{SUBEXP}$, improving the previously known $1+o(1)$ [Stephens-Davidowitz, Approx 2016]. Strengthening the hardness of $\textsf{uSVP}$ has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for $\gamma$-$\mathsf{uSVP}_p$ carries over to ${\frac{1}{\gamma}}$-$\mathsf{BDD}_p$ (Bounded Distance Decoding). Thus, understanding the hardness of $\textsf{uSVP}$ improves worst-case guarantees for two core problems that underpin security in lattice-based cryptography.
Abstract（参考訳）: すべての$p > 2$ に対して、$\ell_p$ ノルム(\mathsf{SVP}_p$) と Unique-SVP(\mathsf{uSVP}_p$) の近似結果の決定的困難性を確立する。以前は$\ell_\infty$を除いて決定論的硬さの結果は知られていない。多項式時間アルゴリズムが$\mathsf{SVP}_p$または$\mathsf{uSVP}_p$を$\sqrt{2} - o(1)$と仮定すると、$\textsf{3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$と$\textsf{Unambiguous-3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$である。任意の$\varepsilon > 0$ に対して、$p_\varepsilon > 2$ が存在して、すべての$p \ge p_\varepsilon > 2$ に対して、多項式時アルゴリズムが $\mathsf{SVP}_p$ の比$$2^{(\log n)^{1- \varepsilon}}$、$\text{NP} \nsubseteq \text{DTIME}(n^{(\log n)^\varepsilon})$、および$n^{1/(\log\log(n)^\varepsilon}$, assuming $\text{NP} \nsubseteq \text{DTIME}(n^{(\log n)^\varepsilon}$であることを示す。これは [Haviv, Regev, Theory of Computing 2012] で改善され、ランダム化還元の下で同様の不近似比が得られた。仮定の下で$\mathsf{uSVP}_p$に対して、$\textsf{Unambiguous-3SAT} \not\subseteq \text{DTIME}(n^{(\log n)^\varepsilon})$および$\textsf{Unambiguous-3SAT} \not\subseteq \text{SUBEXP}$に対して同様の結果を得る。 $\textsf{uSVP}$の硬さを強化することは、直接的な暗号化の影響をもたらす。 Lyubashevsky と Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009] の削減により、$\gamma$-$\mathsf{uSVP}_p$ は${\frac{1}{\gamma}}$-$\mathsf{BDD}_p$ (Bounded Distance Decoding) になる。したがって、$\textsf{uSVP}$の難しさを理解することは、格子ベースの暗号におけるセキュリティの基盤となる2つのコア問題に対する最悪のケース保証を改善する。

論文の概要: Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$

関連論文リスト