論文の概要: High-Rate Public-Key Pseudorandom Codes for Edit Errors

• arxiv url: http://arxiv.org/abs/2605.19402v1
• Date: Tue, 19 May 2026 05:57:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.150347
• Title: High-Rate Public-Key Pseudorandom Codes for Edit Errors
• Title（参考訳）: 編集エラーのための高レート公開鍵擬似乱数符号
• Authors: Shengtang Huang, Xin Li, Songtao Mao, Zhaienhe Zhou,
• Abstract要約: Pseudorandom codes (PRC) は、一様ランダムな文字列と計算的に区別できない誤り訂正符号である。 置換誤差の一定割合に対して頑健な二進ゼロビットPRCは、編集エラーに対して二進ゼロビットPRCに変換可能であることを示す。 高位制では、十分に大きな定数のアルファベットを任意に1ドル近く、バイナリのアルファベットを任意に1/2ドルに近いレートで公開鍵のPRCを構築する。
• 参考スコア（独自算出の注目度）: 4.314680428399915
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO '2024), are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings, while still being decodable by someone holding the key. They provide a natural primitive for robust and undetectable watermarking, particularly in applications to AI-generated content. Although recent works have obtained strong results for substitution errors, the edit-error setting remains much less understood, especially in the high-rate regime and over small alphabets. We study public-key pseudorandom codes against edit errors. First, we give a new reduction showing that binary zero-bit PRCs robust against a constant fraction of substitution errors can be transformed into binary zero-bit PRCs robust against edit errors. Consequently, under any assumption that yields zero-bit Hamming-robust PRCs, one also obtains zero-bit PRCs for edit channels, albeit only for the weaker class of sublinear polynomial edit channels, namely channels with edit error rate $1/n^γ$ for any constant $γ>0$. In the high-rate regime, we construct public-key PRCs with rate arbitrarily close to $1$ over sufficiently large constant alphabets, and with rate arbitrarily close to $1/2$ over the binary alphabet. Moreover, if we allow the alphabet size to be $\mathrm{poly}(λ)$, where $λ$ is the security parameter, then our public-key PRCs can attain the Singleton bound for insertion-deletion channels. Taken together, these results yield the first high-rate public-key binary PRC constructions for edit channels, under the same assumption that yields zero-bit Hamming-robust PRCs.
• Abstract（参考訳）: Christ and Gunn (CRYPTO '2024) が導入した Pseudorandom codes (PRCs) は、コードワードが一様ランダムな文字列と計算的に区別できないが、キーを持っている人によって復号可能であるエラー訂正符号である。 それらは、堅牢で検出不能な透かし、特にAI生成コンテンツへの応用において、自然なプリミティブを提供する。 近年の研究では置換エラーについて強い結果が得られているが、編集エラー設定は特に高位制や小文字よりもはるかに理解されていない。 編集エラーに対する公開鍵擬似乱数符号について検討する。 まず,バイナリゼロビットPRCが一定の置換誤差に対して頑健であることを示し,編集エラーに対して頑健なバイナリゼロビットPRCに変換可能であることを示す。 したがって、ゼロビットハミングローバストPRCを出力する任意の仮定の下で、編集チャネルのゼロビットPRCも取得するが、編集エラー率が1/n^γ$で、任意の定数$γ>0$に対して、サブ線形多項式編集チャネルの弱いクラスに限られる。 高位制では、十分大きな定型アルファベットを任意に1ドル近い確率で、二進アルファベットを1/2ドル近いレートで、公開鍵のPRCを構築する。 さらに、アルファベットサイズが$\mathrm{poly}(λ)$であるなら、$λ$はセキュリティパラメータである。 まとめると、これらの結果は、編集チャネルのための最初の高速な公開キーバイナリPRC構造をもたらすが、これは、ゼロビットのハミングローバストPRCをもたらす仮定と同じである。

関連論文リスト

• Public Key Encryption from High-Corruption Constraint Satisfaction Problems [6.201763450086127]
  本稿では,2つの制約満足度問題(CSP)の推測的難解性に基づく,有意な準指数セキュリティを備えた公開鍵暗号方式を提案する。 我々の公開鍵暗号方式は、汚染度の高いCSPを初めて活用し、同時に準ポリノミカルよりも遥かに高いセキュリティレベルを達成する。
  論文  参考訳（メタデータ） (2026-04-12T06:19:54Z)
• Improved Pseudorandom Codes from Permuted Puzzles [28.363531214070196]
  疑似ランダム性セキュリティを実現するための疑似ランダムコードを構築し、二進アルファベットによる最悪の場合の編集に対する堅牢性、そして計算不能な敵に対する堅牢性を実現する。 この予想は、以前に2倍効率のプライベート情報検索を構築するために使われた変分パズル予想によって導かれることを示す。
  論文  参考訳（メタデータ） (2025-12-09T18:53:42Z)
• The Coding Limits of Robust Watermarking for Generative Models [8.828526790179673]
  我々は、生成モデルに対する暗号透かしの堅牢性について、鋭いしきい値を示す。 簡単な作物と再サイズ操作が潜伏標識の約半分を確実に反転させ、信念伝達復号を一貫して防止したことを示す。
  論文  参考訳（メタデータ） (2025-09-11T18:08:32Z)
• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  繰り返しビットフリップデコーダは、sparse $(v,w)$-regular符号の効率的な選択である。 閉形式モデルに基づくしきい値決定のための具体的な基準を提案する。
  論文  参考訳（メタデータ） (2025-01-23T17:38:22Z)
• New constructions of pseudorandom codes [23.22566380210149]
  Pseudorandom error-correcting codes (PRCs) は、生成AIモデルをウォーターマークする新しい暗号プリミティブである。 本研究では,一定誤差率に対して頑健なPRCが存在するという仮定を考察する。 これは$textitunconditionally$ indistinguishable from random by $textpoly(n)$ time, $O(n1.5-varepsilon) spaceである。
  論文  参考訳（メタデータ） (2024-09-11T19:14:39Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
  有限出力であるが任意の入力アルファベットを持つメモリレスチャネルに対する一般性の問題を考える。 主な発見は、メッセージの最大長が$R,nlog n$、ブロック長$n$と超直線的にスケールすることである。 出力分布のペアの信頼性を保証し、DIコードを構築するのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-14T11:59:30Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。 これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。 本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
  論文  参考訳（メタデータ） (2024-02-06T18:59:30Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。 本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
  論文  参考訳（メタデータ） (2024-01-30T11:40:24Z)

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

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