Fugu-MT 論文翻訳(概要): Algorithms for Sparse LPN and LSPN Against Low-noise

論文の概要: Algorithms for Sparse LPN and LSPN Against Low-noise

arxiv url: http://arxiv.org/abs/2407.19215v7
Date: Fri, 07 Feb 2025 14:12:34 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-10 14:52:43.404859
Title: Algorithms for Sparse LPN and LSPN Against Low-noise
Title（参考訳）: 低雑音に対するスパースLPNとLSPNのアルゴリズム
Authors: Xue Chen, Wenxuan Shu, Zhaienhe Zhou,
Abstract要約: ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
参考スコア（独自算出の注目度）: 1.2143710013809321
License:
Abstract: We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem. Our main contribution is a new algorithmic framework that provides learning algorithms against low-noise for both Learning Sparse Parities (LSPN) problem and sparse LPN problem. Different from previous approaches for LSPN and sparse LPN, this framework has a simple structure and runs in polynomial space. Let $n$ be the dimension, $k$ denote the sparsity, and $\eta$ be the noise rate. As a fundamental problem in computational learning theory, Learning Sparse Parities with Noise (LSPN) assumes the hidden parity is $k$-sparse. While a simple enumeration algorithm takes ${n \choose k}=O(n/k)^k$ time, previously known results stills need ${n \choose k/2} = \Omega(n/k)^{k/2}$ time for any noise rate $\eta$. Our framework provides a LSPN algorithm runs in time $O(\eta \cdot n/k)^k$ for any noise rate $\eta$, which improves the state-of-the-art of LSPN whenever $\eta \in (\sqrt{k/n},k/n)$. The sparse LPN problem is closely related to the classical problem of refuting random $k$-CSP and has been widely used in cryptography as the hardness assumption. Different from the standard LPN, it samples random $k$-sparse vectors. Because the number of $k$-sparse vectors is ${n \choose k}<n^k$, sparse LPN has learning algorithms in polynomial time when $m>n^{k/2}$. However, much less is known about learning algorithms for constant $k$ like 3 and $m<n^{k/2}$ samples, except the Gaussian elimination algorithm of time $e^{\eta n}$. Our framework provides a learning algorithm in $e^{O(\eta \cdot n^{\frac{\delta+1}{2}})}$ time given $\delta \in (0,1)$ and $m \approx n^{1+(1-\delta)\cdot \frac{k-1}{2}}$ samples. This improves previous learning algorithms. For example, in the classical setting of $k=3$ and $m=n^{1.4}$, our algorithm would be faster than $e^{\eta n}$ for any $\eta<n^{-0.6}$.
Abstract（参考訳）: ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースLPN(Learning Sparse Parities)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいアルゴリズムフレームワークである。 LSPNやスパースLPNの以前のアプローチとは異なり、このフレームワークは単純な構造を持ち、多項式空間で実行される。 n$ を次元とし、k$ を空間とし、$\eta$ を雑音率とする。計算学習理論の根本的な問題として、LSPN(Learning Sparse Parities with Noise)は、隠れたパリティが$k$-sparseであると仮定する。単純な列挙アルゴリズムは${n \choose k}=O(n/k)^k$timeを取るが、これまで知られていた結果は${n \choose k/2} = \Omega(n/k)^{k/2}$time for any noise rate $\eta$である。我々のフレームワークは、任意のノイズレート$\eta$に対して、時間$O(\eta \cdot n/k)^k$で実行されているLSPNアルゴリズムを提供し、$\eta \in (\sqrt{k/n},k/n)$のときいつでも、LSPNの最先端技術を改善する。スパースLPN問題は、ランダム$k$-CSPを論じる古典的な問題と密接に関連しており、暗号学においてハードネスの仮定として広く用いられている。標準のLPNとは異なり、ランダムな$k$-sparseベクトルをサンプリングする。 k$-スパースベクトルの数は${n \choose k}<n^k$であるため、スパースLPNは$m>n^{k/2}$の多項式時間で学習アルゴリズムを持つ。しかし、時間$e^{\eta n}$のガウス除去アルゴリズムを除いて、3 と $m<n^{k/2}$のサンプルに対する一定の$k$の学習アルゴリズムについてはあまり知られていない。我々のフレームワークは、$\delta \in (0,1)$と$m \approx n^{1+(1-\delta)\cdot \frac{k-1}{2}}$サンプルの学習アルゴリズムを$e^{O(\eta \cdot n^{\frac{\delta+1}{2}})} で提供する。これにより、従来の学習アルゴリズムが改善される。例えば、$k=3$と$m=n^{1.4}$の古典的な設定では、我々のアルゴリズムは任意の$\eta<n^{-0.6}$に対して$e^{\eta n}$よりも高速である。

論文の概要: Algorithms for Sparse LPN and LSPN Against Low-noise

関連論文リスト