論文の概要: Regular Syndrome Decoding Is Easier Than Previously Estimated

• arxiv url: http://arxiv.org/abs/2610.29175v1
• Date: Wed, 21 Oct 2026 04:08:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.200115
• Title: Regular Syndrome Decoding Is Easier Than Previously Estimated
• Title（参考訳）: レギュラーシンドロームの復号は、これまでより簡単になった
• Abstract要約: 多くの広く使われているパラメータ集合は、以前推定されたよりも解くのがかなり簡単であることを示す。 この改善は、以前は見過ごされていた具体的な複雑さの源を露出し、取り除く、洗練されたハイブリッド代数攻撃に起因している。 我々は、フェレット、ウルヴァリン、コミットVOLEなどのRSDベースのアプリケーションを再評価する。
• 参考スコア（独自算出の注目度）: 3.5929502798593664
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Regular Syndrome Decoding (RSD) problem is a structured variant of classical Syndrome Decoding and underlies a growing number of efficient cryptographic constructions, including zero knowledge protocols, pseudorandom correlation generators, and MPC in the Head signatures. Although RSD is generally believed to be computationally hard, recent works have shown that algebraic attacks can outperform information set decoding on important RSD parameter regimes. Building on this line of work, we revisit the concrete hardness of RSD and show that many widely used parameter sets are substantially easier to solve than previously estimated. This improvement stems from a refined hybrid algebraic attack that exposes and removes a previously overlooked source of concrete complexity: the joint blockwise placement of zero coordinate guesses and syndrome based variable eliminations. Rather than treating the two guessing stages and linear elimination as largely separate choices, our method coordinates them across all regular blocks so that the guessing penalty is balanced while sufficient equations are retained for linearization. This gives a systematic block balancing principle for the entire guess reduce solve pipeline. We reassess several RSD based applications, including Ferret, Wolverine, and committed VOLE. Our estimates place at least one parameter set per application below its 128 bit target, with losses approaching 67 bits. On PCG benchmarks, we improve previous best attack costs by up to 29.77 and 25.91 bits over non binary and binary fields, respectively. Moreover, for the revised 128 bit PCG parameter sets of Liu et al. evaluated here, estimated attack costs are all below $2^{111}$ field operations. These results substantially revise the concrete security landscape of RSD and indicate that several existing parameter choices overestimate the hardness of their underlying RSD instances.
• Abstract（参考訳）: 規則型シンドローム復号法(RSD)問題は古典型シンドローム復号法(英語版)の構造化版であり、ゼロ知識プロトコル、擬似ランダム相関生成器、ヘッドシグネチャのMPCを含む多くの効率的な暗号構造の基礎となっている。 RSDは一般に計算が難しいと考えられているが、近年の研究では、代数的攻撃は重要なRSDパラメーターレジームでデコードされた情報よりも優れていることが示されている。 本研究は, RSDの具体的な硬さを再考し, 広く使われているパラメータセットの多くが, 以前推定したよりも解き易いことを示す。 この改良は、ゼロ座標推定とシンドロームに基づく変数除去の連立ブロックワイド配置という、以前見過ごされた具体的な複雑さの源を露出し、取り除く、洗練されたハイブリッド代数攻撃に起因している。 2つの推定段階と線形除去を大まかに別個の選択として扱うのではなく、線形化に十分な方程式を保ちながら、推算ペナルティのバランスを保たせるように、全ての正則ブロックで座標を調整する。 これにより、推測全体に対して、システマティックなブロックバランスの原則が解決パイプラインを削減します。 我々は、フェレット、ウルヴァリン、コミットVOLEなどのRSDベースのアプリケーションを再評価する。 我々の推定では、アプリケーション毎の少なくとも1つのパラメータセットが128ビットのターゲット以下であり、損失は67ビットに近づいた。 PCGベンチマークでは、非バイナリフィールドとバイナリフィールドでそれぞれ29.77ビットと25.91ビットの攻撃コストを改善する。 さらに、ここで評価したLiuらによる128ビットPCGパラメーターの修正について、推定攻撃コストは2.111}$フィールド演算以下である。 これらの結果は、RSDの具体的なセキュリティ状況を大幅に改善し、既存のパラメータ選択が基礎となるRSDインスタンスの硬さを過大評価していることを示している。

関連論文リスト

• Can Language Models Learn to Reject Their Own Bad Reasoning Steps? [29.52749228408909]
  セルフステップ・リジェクション(SSR)は、ベースモデルの凍結を維持しながら、発電機のバックボーンに軽量のロラ受入ゲートを訓練する。 SSRは、生成されたトークンの1.21--1.40倍を用いて、シングルパスデコードよりも平均マクロ平均精度を5.4--10.1ポイント向上させる。
  論文  参考訳（メタデータ） (2026-10-05T08:27:16Z)
• DRSR: Learning Set-Level Deletion Risk for Efficient Long-Horizon Agents [55.84813053778976]
  ロングホライゾン言語モデルエージェントは、現在の決定と関係が変化する推論の痕跡、ツール交換、観察を蓄積する。 直接セットリスクスコアは、削除セットの選択としてエージェント履歴圧縮リスクを定式化する。 メカニカル・アナリシスとアブリケーションは、決定に制約のある関係、保持されたコンテキスト情報、ペア・インタラクション、および棄権がそれぞれ信頼できるプルーニングに寄与していることを示している。
  論文  参考訳（メタデータ） (2026-09-23T03:06:01Z)
• Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS [0.47267770920095525]
  制約付きシンドロームデコーディングの解法は、特定の構造のベクトルと、新たに構築された符号の小さなノルムから導出可能であることを示す。 これにより、リミテッドシンドロームデコーディングをコードベース(レギュラーシンドロームデコーディング)と格子ベース問題の両方に削減できる。
  論文  参考訳（メタデータ） (2026-04-10T13:03:00Z)
• Breaking the Simplification Bottleneck in Amortized Neural Symbolic Regression [8.351253396371686]
  SimpliPyはルールベースの単純化エンジンで、SymPyよりも100倍のスピードアップを実現している。 この利点をFlash-ANSRフレームワークで示しています。
  論文  参考訳（メタデータ） (2026-02-09T16:47:00Z)
• Residual Context Diffusion Language Models [90.07635240595926]
  Residual Context Diffusion (RCD) は、捨てられたトークン表現をコンテキスト残留に変換し、次のデノイングステップでそれらを注入するモジュールである。 RCDは、最小限の計算オーバーヘッドで、5-10ポイントの精度でフロンティアdLLMを一貫して改善する。
  論文  参考訳（メタデータ） (2026-01-30T13:16:32Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。 Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。
  論文  参考訳（メタデータ） (2025-05-19T07:32:56Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。 本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
  論文  参考訳（メタデータ） (2024-01-30T11:40:24Z)
• Sparse-Inductive Generative Adversarial Hashing for Nearest Neighbor Search [8.020530603813416]
  本稿では,Sparsity-induced Generative Adversarial Hashing (SiGAH)と呼ばれる新しい教師なしハッシュ法を提案する。 SiGAHは、大規模な高次元特徴をバイナリコードにエンコードする。 Tiny100K、GIST1M、Deep1M、MNISTの4つのベンチマーク実験の結果、提案されたSiGAHは最先端のアプローチよりも優れた性能を示している。
  論文  参考訳（メタデータ） (2023-06-12T08:07:23Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)

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

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