論文の概要: Improved Pseudorandom Codes from Permuted Puzzles

• arxiv url: http://arxiv.org/abs/2512.08918v1
• Date: Tue, 09 Dec 2025 18:53:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-10 22:28:08.103117
• Title: Improved Pseudorandom Codes from Permuted Puzzles
• Title（参考訳）: 可変ノズルからの擬似符号の改良
• Authors: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs,
• Abstract要約: 疑似ランダム性セキュリティを実現するための疑似ランダムコードを構築し、二進アルファベットによる最悪の場合の編集に対する堅牢性、そして計算不能な敵に対する堅牢性を実現する。 この予想は、以前に2倍効率のプライベート情報検索を構築するために使われた変分パズル予想によって導かれることを示す。
• 参考スコア（独自算出の注目度）: 28.363531214070196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equivalent to watermarks with strong robustness and quality guarantees. A PRC is a pseudorandom encryption scheme whose decryption algorithm tolerates a high rate of errors. Pseudorandomness ensures quality preservation of the watermark, and error tolerance of decryption translates to the watermark's ability to withstand modification of the content. In the short time since the introduction of PRCs, several works (NeurIPS '24, RANDOM '25, STOC '25) have proposed new constructions. Curiously, all of these constructions are vulnerable to quasipolynomial-time distinguishing attacks. Furthermore, all lack robustness to edits over a constant-sized alphabet, which is necessary for a meaningfully robust LLM watermark. Lastly, they lack robustness to adversaries who know the watermarking detection key. Until now, it was not clear whether any of these properties was achievable individually, let alone together. We construct pseudorandom codes that achieve all of the above: plausible subexponential pseudorandomness security, robustness to worst-case edits over a binary alphabet, and robustness against even computationally unbounded adversaries that have the detection key. Pseudorandomness rests on a new assumption that we formalize, the permuted codes conjecture, which states that a distribution of permuted noisy codewords is pseudorandom. We show that this conjecture is implied by the permuted puzzles conjecture used previously to construct doubly efficient private information retrieval. To give further evidence, we show that the conjecture holds against a broad class of simple distinguishers, including read-once branching programs.
• Abstract（参考訳）: 透かしはAI生成コンテンツを識別するための重要なツールである。 近年、Christ and Gunn (CRYPTO '24) は、強い堅牢性と品質保証を持つ透かしと同等の擬似乱数誤り訂正符号 (PRC) を導入した。 PRCは、復号アルゴリズムが高いエラー率を許容する擬似ランダム暗号方式である。 Pseudorandomnessは透かしの品質を保証し、復号の誤り耐性は、透かしの修正に耐えられる能力に変換される。 PRCの導入以来、いくつかの作品(NeurIPS '24, RANDOM '25, STOC '25)が新たに提案されている。 奇妙なことに、これらの構造は準ポリノミカル時間差攻撃に対して脆弱である。 さらに、すべてが一定の大きさのアルファベットで編集する堅牢性に欠けており、これは有意義に堅牢なLLM透かしに必要である。 最後に、透かし検出キーを知っている敵にとっては堅牢性に欠ける。 これまでのところ、これらの特性のいずれかが個別に達成可能かどうかは不明だった。 上記のすべてを達成する擬似乱数符号を構築する: 疑似乱数セキュリティ、二進アルファベットによる最悪の場合の編集に対する堅牢性、そして検出キーを持つ計算不能な敵に対する堅牢性。 Pseudorandomness は、置換符号予想(permuted codes conjecture)を形式化する新しい仮定に基づいている。 この予想は、以前に2倍効率のプライベート情報検索を構築するために使われた変分パズル予想によって導かれることを示す。 さらに証拠を与えるために、この予想は読み取りオンス分岐プログラムを含む幅広い単純な微分器のクラスに対して成り立つことを示す。

関連論文リスト

• Ideal Pseudorandom Codes [8.382679821011134]
  擬似乱数符号は誤り訂正符号であり、効率のよい敵が一様ランダムな文字列から符号化を区別できない性質を持つ。 その後、いくつかの擬似乱数符号の構成が提案されているが、これらは以前に見られたコードワードに依存するエラーチャネルに対して堅牢なものではない。 単一ビットメッセージに対して適応的にロバストな擬似乱数符号を用いて、CCAセキュアな擬似乱数符号を構築することができることを示す。
  論文  参考訳（メタデータ） (2024-11-08T20:22:14Z)
• Edit Distance Robust Watermarks via Indexing Pseudorandom Codes [29.69428894587431]
  AI生成テキストの検出の問題に触発されて、証明可能な保証付き言語モデルの出力を透かしする問題を考える。 a)非検出性、(a)Christ, Gunn & Zamir (2024) が導入した暗号概念、(b) 敵の挿入、置換、削除を一定の割合で導入するチャネルに対する堅牢性。
  論文  参考訳（メタデータ） (2024-06-04T04:03:17Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  サブワードに基づく言語モデルを使用する際に生じるセグメンテーションの曖昧さ問題は、時にはデコード障害を引き起こす。 そこで我々はSyncPoolという,セグメンテーションのあいまいさ問題に効果的に対処する,セキュアな曖昧さ回避手法を提案する。 SyncPoolは、候補プールのサイズやトークンの分布を変えないため、確実に安全な言語ステガノグラフィー手法に適用できる。
  論文  参考訳（メタデータ） (2024-03-26T09:25:57Z)
• Pseudorandom Error-Correcting Codes [0.716879432974126]
  暗号置換や削除エラーに対して堅牢な擬似乱数符号を構築します。 ランダムな置換と削除の出力に対する検出不能な透かし方式を提案する。 第2の応用はステガノグラフィーで、秘密のメッセージが無実のコンテンツに隠されている。
  論文  参考訳（メタデータ） (2024-02-14T18:17:45Z)
• SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation [72.10931780019297]
  既存の透かしアルゴリズムはトークンレベルの設計のため、パラフレーズ攻撃に弱い。 局所性に敏感なハッシュ(LSH)に基づく頑健な文レベルのセマンティック透かしアルゴリズムSemStampを提案する。 実験結果から,本アルゴリズムは従来手法に比べて,従来手法よりも頑健であるだけでなく,生成品質の維持にも有効であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-06T03:33:42Z)
• Who Wrote this Code? Watermarking for Code Generation [53.24895162874416]
  本稿では,機械生成テキストを検出するために,Entropy Thresholding (SWEET) を用いたSelective WatErmarkingを提案する。 実験の結果,SWEETはコード品質を著しく向上し,すべてのベースラインを上回ります。
  論文  参考訳（メタデータ） (2023-05-24T11:49:52Z)

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

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