論文の概要: Towards Worst-case Hardness for Low-Noise LPN

• arxiv url: http://arxiv.org/abs/2606.05834v1
• Date: Thu, 04 Jun 2026 08:11:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-05 22:39:44.637527
• Title: Towards Worst-case Hardness for Low-Noise LPN
• Title（参考訳）: 低雑音LPNの最悪の硬さに向けて
• Authors: Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen, Kel Zin Tan, Prashant Nalini Vasudevan,
• Abstract要約: 既存の[BLVW19, YZ21]の最悪のケース・ツー・ケースの削減は、線形符号の統計的平滑化に依存している。 効率的な解法を効率の良いアルゴリズムに変換できることを示す。
• 参考スコア（独自算出の注目度）: 6.6603865098703805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-α}$ for any constant $α< 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $α= 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.
• Abstract（参考訳）: LPN問題(Learning Parity with Noise)の難しさは暗号の基礎的な仮定であり、対称鍵プリミティブから公開鍵暗号などを含む構成の基礎を形成する。 LPNの平均ケース硬度は、LWE(Learning With Errors)問題において達成されたように、最悪のケースの複雑さの仮定に基づいているかという問題である。 LPN [BLVW19, YZ21] の既存の最悪のケース・ツー・ケースの削減は、線形符号の統計的スムース化に依存しており、結果として生じる平均ケースの硬さを1/2 - 1/\mathrm{poly}(n)$に制限する。 コードの生成行列の行のランダムなスパース結合が統計的に一様に近いことを要求するのではなく、計算的に一様と区別できないことを要求する。 効率的なLPNソルバは、任意の行列$A$が$\mathbb{F}_2$を超える適切な次元の任意の行列に対して、$S$が$A$で生成されたコードをランダムノイズからデコードするか、または$D$がこの符号の双対のランダムノイズコードワードを均一に区別するように、一対の効率的なアルゴリズム$(S, D)$に変換可能であることを示す。 この縮小を適切なパラメータでインスタンス化することにより、任意の定数$α<1$に対して逆多項式雑音率$n^{-α}$のLPNの平均ケース硬度を求める。 特に、$α=1/2$を設定すると、Alekhnovich氏の公開鍵暗号構築に必要なパラメータ規則におけるLPN硬さが得られます [Ale03]。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
  ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。 我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
  論文  参考訳（メタデータ） (2024-07-27T08:57:04Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
  高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。 これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。 我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
  論文  参考訳（メタデータ） (2024-02-06T02:17:08Z)
• Reduction from sparse LPN to LPN, Dual Attack 3.0 [1.9106435311144374]
  全く異なるアプローチに依存する RLPN-decoding と呼ばれる新しいアルゴリズムが導入された。 コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。 このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。
  論文  参考訳（メタデータ） (2023-12-01T17:35:29Z)

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

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