論文の概要: 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の攻撃
• 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の時間複雑さの間に新たなトレードオフをもたらす。

関連論文リスト

• Towards Worst-case Hardness for Low-Noise LPN [6.6603865098703805]
  既存の[BLVW19, YZ21]の最悪のケース・ツー・ケースの削減は、線形符号の統計的平滑化に依存している。 効率的な解法を効率の良いアルゴリズムに変換できることを示す。
  論文  参考訳（メタデータ） (2026-06-04T08:11:23Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• 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)
• Exponential Weights Algorithms for Selective Learning [39.334633118161285]
  本稿では,Qiao と Valiant が導入した選択学習問題について考察する。 学習者が引き起こす余剰リスクは、これらの$w$のデータポイントに対する$hatellの損失の平均値の差として定義される。 また,長さ$w$の予測ウィンドウが選択された場合,学習者の判断は最新の$w$のデータポイントにのみ依存する。
  論文  参考訳（メタデータ） (2021-06-29T18:14:01Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)

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

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