論文の概要: A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes

• arxiv url: http://arxiv.org/abs/2609.02943v1
• Date: Mon, 31 Aug 2026 21:31:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:38.799691
• Title: A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes
• Title（参考訳）: 固定されたAlphabet多ビット擬似乱数符号に対する公開鍵依存型逆数削除シーリング
• Abstract要約: 擬似乱数符号(英: pseudorandom code、PRC)は、一様文字列と計算的に区別できない誤り訂正符号である。 固定字幕上のパブリックキーのPRCを、敵の削除に対して研究する。
• 参考スコア（独自算出の注目度）: 2.1485350418225244
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let $γ_q^{\mathrm{LCS}}$ denote the asymptotic normalised longest-common-subsequence length of two independent uniform $q$-ary strings. We prove that for every fixed $q\ge2$ no multi-message public-key PRC with a single-output decoder is robust against all such $δ$-deletion channels for any $δ>1-γ_q^{\mathrm{LCS}}$. For $q=2$, the current rigorous bound $γ_2\ge0.792665992$ rules out every constant $δ>0.207334008$. The proof uses pseudorandomness only to transfer an LCS event from uniform strings to independently sampled codewords and therefore also the resulting collision argument is information-theoretic and requires no secret key. We also extend the argument to list decoding: for every fixed constant $L$, provided the message space contains at least $L+1$ messages, no such PRC with output lists of size at most $L$ is robust for $δ>1-γ_2^{(L+1)}$. Since $γ_2^{(m)}=1/2+Θ(1/\sqrt m)$, these thresholds approach $1/2$. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.
• Abstract（参考訳）: 擬似乱数符号(英: pseudorandom code、PRC)は、一様文字列と計算的に区別できない誤り訂正符号である。 固定字幕上の公開鍵PRCを敵の削除に対して研究し、削除チャネルは公開符号化キーと送信されたコードワードに依存する可能性がある。 γ_q^{\mathrm{LCS}}$ は、2つの独立な$q$-ary文字列の漸近正規化長の長さを表す。 すべての固定$q\ge2$に対して、単一出力デコーダ付きマルチメッセージ公開鍵PRCは、任意の$δ>1-γ_q^{\mathrm{LCS}}$に対して、そのような$δ$-deletionチャネルに対して堅牢であることを示す。 q=2$ の場合、現在の厳密な境界である $γ_2\ge0.792665992$ はすべての定数 $δ>0.207334008$ を規則する。 この証明は擬似ランダム性を利用して、一様文字列から独立したサンプルコードワードにLCSイベントを転送するだけであり、その結果の衝突引数は情報理論であり、秘密鍵を必要としない。 メッセージ空間が少なくとも$L+1$メッセージを含む場合、少なくとも$L$の出力リストは$δ>1-γ_2^{(L+1)}$に対して堅牢である。 γ_2^{(m)}=1/2 + =(1/\sqrt m)$であるから、これらの閾値は1/2$に近づく。 我々のバウンダリは公開鍵依存の敵チャネルに特化しており、有害な編集チャネルには適用されない。

関連論文リスト

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。 加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
  論文  参考訳（メタデータ） (2026-09-04T18:28:01Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Discrepancy for Random Linear Codes [10.105438043325357]
  ランダムな線形符号は、幅広い状況下でほぼ最適な相違性を持つことを示す。 まず、ランダムな線形符号は、容量以上のエラーからリスト復号する非構造化のランダム符号と一致する。 第二に、素体上のランダム線形符号はゼロエラーリストのキャパシティ上の非構造化ランダム符号と一致する。
  論文  参考訳（メタデータ） (2026-06-23T12:01:54Z)
• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  本稿では,emphTri-Audit Protocolとしてフロアを運用する。このプロトコルは,プロンプト側推論レジストリ属性をモデル側実証ログから分離する2軸レポーティングプロトコルである。 CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of 28 pass-serving rows, 12-changed-of-record learned-can
  論文  参考訳（メタデータ） (2026-06-02T08:22:14Z)
• High-Rate Public-Key Pseudorandom Codes for Edit Errors [4.314680428399915]
  Pseudorandom codes (PRC) は、一様ランダムな文字列と計算的に区別できない誤り訂正符号である。 置換誤差の一定割合に対して頑健な二進ゼロビットPRCは、編集エラーに対して二進ゼロビットPRCに変換可能であることを示す。 高位制では、十分に大きな定数のアルファベットを任意に1ドル近く、バイナリのアルファベットを任意に1/2ドルに近いレートで公開鍵のPRCを構築する。
  論文  参考訳（メタデータ） (2026-05-19T05:57:25Z)
• One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification [0.0]
  リストプライバシー増幅(LPA) LPA の形式化と emphQuantum Listleftover Hash Lemma (QLLHL) の証明
  論文  参考訳（メタデータ） (2026-03-18T10:37:05Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
  普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。 ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T19:37:35Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• 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)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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