論文の概要: On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography

• arxiv url: http://arxiv.org/abs/2501.02626v1
• Date: Sun, 05 Jan 2025 18:43:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 17:05:06.219681
• Title: On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography
• Title（参考訳）: 準暗号暗号における独立性の推定について
• Authors: Maxime Bombar, Nicolas Resch, Emiel Wiedijk,
• Abstract要約: 最も効率的な提案は、構造化符号の復号化の難しさを前提としている。 HQCは2つの巡回ブロックからなる行列によって生成される準循環符号に基づいている。 準巡回符号の平均ケース削減に対する本結果の影響を考察する。
• 参考スコア（独自算出の注目度）: 3.298620737848292
• License:
• Abstract: Cryptography based on the presumed hardness of decoding codes -- i.e., code-based cryptography -- has recently seen increased interest due to its plausible security against quantum attackers. Notably, of the four proposals for the NIST post-quantum standardization process that were advanced to their fourth round for further review, two were code-based. The most efficient proposals -- including HQC and BIKE, the NIST submissions alluded to above -- in fact rely on the presumed hardness of decoding structured codes. Of particular relevance to our work, HQC is based on quasi-cyclic codes, which are codes generated by matrices consisting of two cyclic blocks. In particular, the security analysis of HQC requires a precise understanding of the Decryption Failure Rate (DFR), whose analysis relies on the following heuristic: given random ``sparse'' vectors $e_1,e_2$ (say, each coordinate is i.i.d. Bernoulli) multiplied by fixed ``sparse'' quasi-cyclic matrices $A_1,A_2$, the weight of resulting vector $e_1A_1+e_2A_2$ is very concentrated around its expectation. In the documentation, the authors model the distribution of $e_1A_1+e_2A_2$ as a vector with independent coordinates (and correct marginal distribution). However, we uncover cases where this modeling fails. While this does not invalidate the (empirically verified) heuristic that the weight of $e_1A_1+e_2A_2$ is concentrated, it does suggest that the behavior of the noise is a bit more subtle than previously predicted. Lastly, we also discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.
• Abstract（参考訳）: 復号化の難しさを前提とした暗号(コードベースの暗号)は、量子攻撃者に対する確実なセキュリティのため、最近関心が高まっている。 特に、さらなるレビューのために第4ラウンドに進んだNIST後の標準化プロセスに関する4つの提案のうち、2つはコードベースであった。 HQC や BIKE を含む最も効率的な提案は、NIST が上述したように、実際は構造化されたコードの復号化の難しさに依存している。 HQCは2つの巡回ブロックからなる行列によって生成される準循環符号に基づいています。 具体的には、HQCのセキュリティ分析は、以下のヒューリスティックな解析に依存する復号失敗率(DFR)の正確な理解を必要とする: 与えられたランダムな ``sparse'' ベクトル $e_1,e_2$ (例えば、各座標は i.d. Bernoulli) で、固定された ` ‘`sparse' の準循環行列 $A_1,A_2$ で乗算され、結果として得られるベクトル $e_1A_1+e_2A_2$ の重みはその期待に非常に集中している。 ドキュメンテーションにおいて、著者は独立座標(および正しい辺分布)を持つベクトルとして$e_1A_1+e_2A_2$の分布をモデル化する。 しかし、このモデリングが失敗するケースを明らかにする。 これは、e_1A_1+e_2A_2$の重みが集中しているという(実際に検証された)ヒューリスティックを無効にしないが、騒音の挙動が以前予測されたよりも少し微妙であることを示している。 最後に, 準巡回符号の平均ケース削減に対して, この結果が最悪の場合に与える影響についても論じる。

関連論文リスト

• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  繰り返しビットフリップデコーダは、sparse $(v,w)$-regular符号の効率的な選択である。 閉形式モデルに基づくしきい値決定のための具体的な基準を提案する。
  論文  参考訳（メタデータ） (2025-01-23T17:38:22Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  本稿では,嘉心表現の原理に基づくデータ量子化アルゴリズムを提案する。 以上の結果から, カシ量子化はモデル性能の競争力や優れた品質を達成できることが示唆された。
  論文  参考訳（メタデータ） (2024-04-15T12:38:46Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。 本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
  論文  参考訳（メタデータ） (2024-01-30T11:40:24Z)
• Reduction from sparse LPN to LPN, Dual Attack 3.0 [1.9106435311144374]
  全く異なるアプローチに依存する RLPN-decoding と呼ばれる新しいアルゴリズムが導入された。 コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。 このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。
  論文  参考訳（メタデータ） (2023-12-01T17:35:29Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。 我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
  論文  参考訳（メタデータ） (2023-03-15T15:00:20Z)
• Good Gottesman-Kitaev-Preskill codes from the NTRU cryptosystem [5.497441137435869]
  我々は,いわゆるNTRU暗号系の暗号解析から得られた,ランダムなGottesman-Kitaev-Preskill(GKP)符号のクラスを導入する。 NTRU-GKP符号の派生型は、変位ノイズモデルの復号化がNTRU暗号システムの復号化と等価であるという付加的な性質を持つ。 この構造は、GKPコードがどのように古典的誤り訂正、量子誤り訂正、およびポスト量子暗号の側面を橋渡しするかを強調している。
  論文  参考訳（メタデータ） (2023-03-04T14:39:20Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。 VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
  論文  参考訳（メタデータ） (2022-05-07T03:15:15Z)
• Log-domain decoding of quantum LDPC codes over binary finite fields [4.340338299803562]
  2次有限体 GF$(q=2l)$ 上での量子低密度パリティチェック(LDPC)符号の復号について、総和積アルゴリズム(英語版)を用いて検討する。 従来のBPに必要なベクトルメッセージよりも,非二項量子符号のBP復号に十分であることを示す。
  論文  参考訳（メタデータ） (2021-04-01T07:15:41Z)

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

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