論文の概要: Limitations of the decoding-to-LPN reduction via code smoothing

• arxiv url: http://arxiv.org/abs/2408.03742v3
• Date: Tue, 18 Mar 2025 02:42:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-19 14:11:05.588136
• Title: Limitations of the decoding-to-LPN reduction via code smoothing
• Title（参考訳）: 符号平滑化による復号-LPN削減の限界
• Authors: Madhura Pathegama, Alexander Barg,
• Abstract要約: 研究者は、ノイズ問題を伴う学習パリティのアルゴリズム的難しさを実証しようと試みている。 復号化問題とプリミティブ問題のパラメータの観点から,削減の効率を特徴付ける。
• 参考スコア（独自算出の注目度）: 59.90381090395222
• License:
• Abstract: The Learning Parity with Noise (LPN) problem underlines several classic cryptographic primitives. Researchers have attempted to demonstrate the algorithmic hardness of this problem by finding reductions from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a tool to achieve reductions for codes with vanishing rate. This has left open the question of attaining a reduction with positive-rate codes. Addressing this case, we characterize the efficiency of the reduction in terms of the parameters of the decoding and LPN problems. As a conclusion, we isolate the parameter regimes for which a meaningful reduction is possible and the regimes for which its existence is unlikely.
• Abstract（参考訳）: LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。 研究者は、線形符号の復号化問題から減算を求めることによって、この問題のアルゴリズム的硬さを実証しようと試みており、いくつかの硬さが存在する。 以前の研究では、コードスムーシングを、消滅率の低いコードの削減を実現するツールとして使用していました。 このことは、前向きなレートのコードで削減する、という疑問を解き放った。 本稿では,復号化問題とLPN問題のパラメータによる削減の効率を特徴付ける。 結論として,有意な還元が可能なパラメータ規則と,その存在が不可能なパラメータ規則を分離する。

関連論文リスト

• Quantum advantage from soft decoders [0.7728149002473877]
  最適多項式補間法(OPI)問題におけるいくつかのインスタンス化の改善について述べる。 我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。 本稿では,Regevのリダクションの設定にデコーダを利用できるように,シンドロームからコセットサンプリング問題への新たなリダクションを提案する。
  論文  参考訳（メタデータ） (2024-11-19T15:12:03Z)
• Localized statistics decoding: A parallel decoding algorithm for quantum low-density parity-check codes [3.001631679133604]
  任意の量子低密度パリティチェック符号に対する局所統計復号法を導入する。 我々のデコーダは専用ハードウェアの実装に適しており、実験からリアルタイムシンドロームをデコードするための有望な候補として位置づけられている。
  論文  参考訳（メタデータ） (2024-06-26T18:00:09Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  低密度パリティ・チェック (LDPC) コードは、他の種類のコードに対していくつかの利点がある。 提案手法は,既存の人気符号の復号性能を桁違いに向上させる。
  論文  参考訳（メタデータ） (2024-06-09T12:08:56Z)
• Reduction from sparse LPN to LPN, Dual Attack 3.0 [1.9106435311144374]
  全く異なるアプローチに依存する RLPN-decoding と呼ばれる新しいアルゴリズムが導入された。 コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。 このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。
  論文  参考訳（メタデータ） (2023-12-01T17:35:29Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Boost decoding performance of finite geometry LDPC codes with deep learning tactics [3.1519370595822274]
  有限幾何LDPC符号のクラスに対して,低複雑かつ高性能なデコーダを求める。 高品質なトレーニングデータを効果的に生成する方法について詳述する。
  論文  参考訳（メタデータ） (2022-05-01T14:41:16Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• A PDD Decoder for Binary Linear Codes With Neural Check Polytope Projection [43.97522161614078]
  基本ポリトープに基づく最大可算(ML)復号問題に対処するPDDアルゴリズムを提案する。 また、PDD復号アルゴリズムの最も時間を要する部分に機械学習技術を統合することを提案する。 本稿では、デコード遅延を低減するために特別に設計されたニューラルCPP(N CPP)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-11T07:57:15Z)

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

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