論文の概要: Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

• arxiv url: http://arxiv.org/abs/2603.27190v1
• Date: Sat, 28 Mar 2026 08:32:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 23:18:44.840137
• Title: Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs
• Title（参考訳）: 新しいサンプル時間トレードオフによるスパースLWEとスパースLPNの攻撃
• Authors: Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar,
• Abstract要約: 我々は、決定的な$k$-sparse Learning With Errors (LWE)と$k$-sparse Learning Parity with Noise (LPN)問題に対してアルゴリズムを提供する。 スパースLWE/LPNインスタンス用の菊池グラフを作成し、これらの問題に対して2つの攻撃を与える。
• 参考スコア（独自算出の注目度）: 1.6924726879815808
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper extends the Kikuchi method to give algorithms for decisional $k$-sparse Learning With Errors (LWE) and $k$-sparse Learning Parity with Noise (LPN) problems for higher moduli $q$. We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for $q=2$ given by Wein et. al. (Journal of the ACM 2019). The second approach computes non-trivial closed walks of the graph, and then decides by computing a certain polynomial of edge labels in the walks. This is a generalization of the attack for $q=2$ given by Gupta et. al. (SODA 2026). Both the attacks yield new tradeoffs between sample complexity and time complexity of sparse LWE/LPN.
• Abstract（参考訳）: 本稿では,木口法を拡張して,より高調な$q$に対する決定的な$k$sparse Learning With Errors(LWE)と$k$sparse Learning Parity with Noise(LPN)問題に対するアルゴリズムを提供する。 スパースLWE/LPNインスタンス用の菊池グラフを作成し、これらの問題に対して2つの攻撃を与える。 最初の攻撃は、Wiinらによって与えられた$q=2$の攻撃の一般化である菊池グラフの隣接行列のスペクトルノルムを計算することで決定される(ACM 2019のジャーナル)。 2つ目のアプローチは、グラフの非自明な閉ウォークを計算し、ウォーク内のエッジラベルの特定の多項式を計算することで決定する。 これは、Gupta et al (SODA 2026) から与えられた$q=2$の攻撃の一般化である。 どちらの攻撃もサンプルの複雑さとスパースLWE/LPNの時間複雑さの間に新たなトレードオフをもたらす。

関連論文リスト

• Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
  ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。 我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
  論文  参考訳（メタデータ） (2024-07-27T08:57:04Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。