論文の概要: New constructions of pseudorandom codes
- arxiv url: http://arxiv.org/abs/2409.07580v1
- Date: Wed, 11 Sep 2024 19:14:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-13 18:42:28.878096
- Title: New constructions of pseudorandom codes
- Title（参考訳）: 擬似乱数符号の新しい構成法
- Authors: Surendra Ghentiyala, Venkatesan Guruswami,
- Abstract要約: Pseudorandom error-correcting codes (PRCs) は、生成AIモデルをウォーターマークする新しい暗号プリミティブである。
BKR23]で導入された植込みハイパーループ仮定とGoldreichのPRGホールディングのセキュリティの両方が、効率の良い敵がランダムなコードワードを識別できない公開鍵PRCが存在することを示す。
これは$textitunconditionally$ indistinguishable random by $textpoly()である。
- 参考スコア（独自算出の注目度）: 23.22566380210149
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random, except to individuals with the decoding key. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a polynomial number of codewords from random with better than $o(1)$ advantage. 2. We revisit the construction of [CG24] and show that it can be based on a wider range of assumptions than presented in [CG24]. To do this, we introduce a weakened version of the planted XOR assumption which we call the weak planted XOR assumption and which may be of independent interest. 3. We initiate the study of PRCs which are secure against space-bounded adversaries. We show how to construct secret-key PRCs of length $O(n)$ which are $\textit{unconditionally}$ indistinguishable from random by $\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.
- Abstract（参考訳）: CG24で導入された疑似ランダム誤り訂正符号(PRC)は、生成AIモデルの透かしに応用された新しい暗号プリミティブである。
これらは、多項式的に多くのコードワードの集合が、復号鍵を持つ個人を除いて、ランダムと計算的に区別できないコードである。
本研究では,一定誤差率に対して頑健なPRCが存在するという仮定を考察する。
1) [BKR23] で導入された植込みハイパーループ仮定とゴールドライヒのPRGホールディングスのセキュリティの両方を併用すると, 効率の良い逆数を持たない公開鍵PRCが$o(1)$より有利な符号ワードの多項式数とランダムに区別できることを示す。
2) [CG24] の構成を再検討し, [CG24] に示されるよりも広い範囲の仮定に基づくことができることを示す。
これを実現するために、弱植込み XOR 仮定を弱植込み XOR 仮定と呼び、独立した関心を持つかもしれない弱植込み XOR 仮定の弱化版を導入する。
3. スペースバウンドな敵に対して安全なPRCの研究を開始する。
これは$\textit{unconditionally}$ indistinguishable from random by $\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversariesである。
関連論文リスト
- Ideal Pseudorandom Codes [8.382679821011134]
擬似乱数符号は誤り訂正符号であり、効率のよい敵が一様ランダムな文字列から符号化を区別できない性質を持つ。
その後、いくつかの擬似乱数符号の構成が提案されているが、これらは以前に見られたコードワードに依存するエラーチャネルに対して堅牢なものではない。
単一ビットメッセージに対して適応的にロバストな擬似乱数符号を用いて、CCAセキュアな擬似乱数符号を構築することができることを示す。
論文 参考訳（メタデータ） (2024-11-08T20:22:14Z) - Towards Unconditional Uncloneable Encryption [1.18749525824656]
Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。
関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
論文 参考訳（メタデータ） (2024-10-30T14:40:06Z) - Crooked indifferentiability of the Feistel Construction [53.572703605492904]
Feistelの構築は擬似乱数置換とブロック暗号を構築するための基本的な技術である。
本稿では, アルゴリズム置換攻撃に対しても, 簡単な構成法が適用可能であることを示す。
論文 参考訳（メタデータ） (2024-04-15T04:29:24Z) - Pseudorandom Error-Correcting Codes [0.716879432974126]
暗号置換や削除エラーに対して堅牢な擬似乱数符号を構築します。
ランダムな置換と削除の出力に対する検出不能な透かし方式を提案する。
第2の応用はステガノグラフィーで、秘密のメッセージが無実のコンテンツに隠されている。
論文 参考訳（メタデータ） (2024-02-14T18:17:45Z) - Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。
これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。
我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
論文 参考訳（メタデータ） (2024-02-06T02:17:08Z) - Towards Optimal Statistical Watermarking [95.46650092476372]
仮説テスト問題として定式化して統計的透かしを研究する。
我々の定式化の鍵は、出力トークンと拒絶領域の結合である。
一般仮説テスト設定において,UMP(Uniformly Most Powerful)の透かしを特徴付ける。
論文 参考訳（メタデータ） (2023-12-13T06:57:00Z) - Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。
私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
論文 参考訳（メタデータ） (2023-11-01T20:54:50Z) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。
我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
論文 参考訳（メタデータ） (2023-03-15T15:00:20Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。