論文の概要: Reduction from sparse LPN to LPN, Dual Attack 3.0

• arxiv url: http://arxiv.org/abs/2312.00747v1
• Date: Fri, 1 Dec 2023 17:35:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 13:25:19.053716
• Title: Reduction from sparse LPN to LPN, Dual Attack 3.0
• Title（参考訳）: Sparse LPN から LPN, Dual Attack 3.0 への移行
• Authors: Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich,
• Abstract要約: 全く異なるアプローチに依存する RLPN-decoding と呼ばれる新しいアルゴリズムが導入された。 コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。 このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。
• 参考スコア（独自算出の注目度）: 1.9106435311144374
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders (ISD). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly ISD decoders for a rather large range of rates. This RLPN decoder relies on two ingredients, first reducing decoding to some underlying LPN problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit RLPN-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-LPN problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-LPN to plain-LPN with a coding approach inspired by coded-BKW. It outperforms significantly the ISD's and RLPN for code rates smaller than 0.42. This algorithm can be viewed as the code-based cryptography cousin of recent dual attacks in lattice-based cryptography. We depart completely from the traditional analysis of this kind of algorithm which uses a certain number of independence assumptions that have been strongly questioned recently in the latter domain. We give instead a formula for the LPNs noise relying on duality which allows to analyze the behavior of the algorithm by relying only on the analysis of a certain weight distribution. By using only a minimal assumption whose validity has been verified experimentally we are able to justify the correctness of our algorithm. This key tool, namely the duality formula, can be readily adapted to the lattice setting and is shown to give a simple explanation for some phenomena observed on dual attacks in lattices in [DP23].
• Abstract（参考訳）: コードベースの暗号のセキュリティは、主にジェネリックリニアコードの復号化の難しさに依存している。 ごく最近まで、デコード問題を解決する最良のアルゴリズムは情報セットデコーダ(ISD)であった。 しかし、最近、全く異なるアプローチに依存したRLPN復号法と呼ばれる新しいアルゴリズムを導入し、かなり広い範囲のICD復号器よりも高い性能を示した。 このLPNデコーダは2つの要素に依存しており、最初は根底にあるLPN問題にデコーディングを還元し、次にいくつかの位置に制限された場合、多くのパリティチェックを効率的に計算する。 我々は、このアルゴリズムでは、復号化がスパースLPN問題(すなわちハミング重みが小さい秘密)に還元されることに気づき、LPN復号化を再考する。 我々の新しいアプローチは、coded-BKWにインスパイアされたコーディングアプローチにより、スパースLPNからプレーンLPNへのさらなる削減を図っている。 コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。 このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。 我々は、最近後者の領域で強く疑問視されている、ある種の独立性の仮定を使用する、この種のアルゴリズムの伝統的な分析から完全に離れている。 代わりに、ある重み分布の分析にのみ依存してアルゴリズムの挙動を分析することができる双対性に依存するLPNの雑音に対する公式を与える。 妥当性を実験的に検証した最小限の仮定のみを使用することで、アルゴリズムの正しさを正当化することができる。 この鍵となるツール、すなわち双対式は格子設定に容易に適用でき、[DP23]における格子の二重攻撃で観測されたいくつかの現象の簡単な説明を与える。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。 本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。 我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
  論文  参考訳（メタデータ） (2024-08-07T12:54:43Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。 本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
  論文  参考訳（メタデータ） (2024-01-30T11:40:24Z)
• Viderman's algorithm for quantum LDPC codes [13.916368399461895]
  本稿では,量子LDPC符号に対するバイダーマンのアルゴリズムの一般化について述べる。 これは、定数レート量子LDPC符号に対して最大$Omega(D)$エラーを補正できる最初の消去変換アルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-11T20:17:21Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• 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)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Pruning Neural Belief Propagation Decoders [77.237958592189]
  本稿では,機械学習を用いたBPデコードに対して,過剰完全パリティチェック行列を調整する手法を提案する。 我々は,デコーダの複雑さを低減しつつ,0.27dB,1.5dBのML性能を実現する。
  論文  参考訳（メタデータ） (2020-01-21T12:05:46Z)

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

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