💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

本論文は、置換符号仮説に基づく擬似乱数符号の新しい構成を導入するものであり、これは、従来のウォーターマーキング手法における決定的な限界を克服しつつ、劣指数的なセキュリティ、バイナリ・アルファベットにおける最悪ケースの編集に対する堅牢性、および検出鍵を保有するアドバーサリに対する耐性を同時に達成するものである。

原著者： Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

公開日 2026-06-23

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、ある小説を書いている有名な作家だと想像してください。あなたは、特定の段落がコピーキャット（模倣者）やAIによって書かれたものではなく、自分によって書かれたものであることを証明したいと考えています。しかし、物語の内容を変えたり、不自然にしたりしたくはありません。テキストの中に、たとえ誰かが編集、削除、あるいは並べ替えようとしても、あなたにしか見つけられない「秘密の署名」を隠す方法が必要です。

この論文は、そのような秘密の署名システム（**擬似乱数符号（PRC）**と呼ばれるもの）の、はるかに優れたバージョンを構築することに関するものです。PRCとは、秘密のメッセージを長い無意味な文字列へと変える、魔法の暗号化マシンのようなものだと考えてください。もしあなたが鍵を持っていれば、たとえ中身がめちゃくちゃにされていても、その無意味な文字列から元のメッセージを復元することができます。

以下は、この論文の成果を簡単な比喩を用いて解説したものです。

1. 問題点：古い署名は破られやすすぎた

以前、研究者たちはこれらの署名システムを構築してきましたが、3つの大きな欠陥がありました。

「準多項式（Quasipolynomial）」の欠陥： 例えば、コンピュータが解くのに100万年かかるロックを想像してください。それは良いことですよね？しかし、これまでの古いロックは「準多項式」の時間で解けてしまうことがありました。これは、コンピュータが100万年ではなく、わずか数日で解けてしまうようなロックのことです。長期的な安全性としては不十分でした。
「アルファベット」の欠陥： 古いシステムは、アルファベット全体を変更できる場合（例えば、すべての「A」を「Z」に置き換えるなど）はうまく機能しました。しかし、現実のテキスト（英語など）は、固定された小さなアルファベット（26文字）を持っています。古いシステムは、数文字を変更したり、単語を削除したりするだけで、署名が壊れてしまうという問題を抱えていました。
「鍵」の欠陥： もしハッカーがあなたの秘密の鍵を知っていた場合、署名を消し去るための微細な変更を簡単に見つけることができました。古いシステムは、ハッカーが目隠しをしていることを前提としていました。ハッカーがメガネをかけている（＝情報を知っている）場合には、機能しなかったのです。

2. 解決策：「置換されたパズル（Permuted Puzzle）」

著者らは、「置換符号仮説（Permuted Codes Conjecture）」と呼ばれる概念に基づいた新しいシステムを作成しました。

美しい、複雑なモザイク画（コード）を想像してください。

タイルのシャッフル： モザイクを取り出し、タイルの位置をランダムにシャッフルします（インデックス置換）。
タイルの塗り替え： ブラシを取り、各タイルの色をランダムに塗り替えます（アルファベット置換）。
塵をまく： 全体にランダムな塵を振りかけます（ノイズ）。

著者らは、これら3つのステップをすべて行うと、その結果は見た目には全くランダムで無意味な塵の山のように見えると主張しています。鍵を持たない者にとって、この「シャッフルされたモザイク」と「ランダムな塵」の違いを見分けることは不可能です。これにより、署名は「検知不可能（undetectable）」になります（つまり、テキストの質を損なうことがありません）。

3. 3つの大きな勝利

この論文は、上述した3つの問題を同時に解決したと主張しています。

超強力なセキュリティ： 彼らの新しいロックは非常に強力であり、スーパーコンピュータを長時間稼働させたとしても（劣指数時間）、彼らのシャッフルされたモザイクとランダムな塵の違いを見分けることはできないと主張しています。
編集に対する堅牢性（「編集」の問題）： これが最大の画期的な成果です。彼らのシステムは「編集」に耐えることができます。ハッカーが単語を削除したり、タイポ（打ち間違い）を追加したり、文章を入れ替えたりしても、システムは依然として署名を見つけ出すことができます。
- 比喩： メッセージが長い紙の帯に書かれていると想像してください。もし誰かが数語を切り取ったり、新しい言葉を貼り付けたり、順番を入れ替えたりしたら、古いシステムは失敗します。新しいシステムは、たとえピースが少し損傷したり動いたりしていても、解くことができるパズルのようなものです。
「鍵を知っている」ハッカーに対しても堅牢： 彼らのシステムは、ハッカーが秘密の鍵を知っている場合でも機能します。
- 比喩： 通常、泥棒が金庫の組み合わせを知っていれば、中身を取り出すことができます。著者らは、たとえ泥棒が組み合わせを知っていても、金庫自体を破壊することなしには隠されたアイテムを取り出せないような金庫を作りました。これにより、信頼できる当事者だけでなく、誰でもシステムを壊すことなくウォーターマーク（透かし）を検証することが可能になります。

4. 実装方法（「折り畳み」のトリック）

これを実際のテキスト（エントロピー、つまり単語ごとのランダム性が低いテキスト）で実現するために、彼らは**折り畳みリード・ソロモン符号（Folded Reed-Solomon codes）**と呼ばれる特殊な数学的コードを使用しました。

比喩： 秘密のメッセージを送ろうとしているのですが、データが短く断片的な状態でしか送れないとします。従来の方法は、一文字ずつ送ることでした。新しい方法は、メッセージを「折り畳む」方法です。「A、B、C」と送る代わりに、「AとBとC」を一度に表す一つのブロックを送ります。これにより、テキストが高度にランダムであったり混沌としたりしていなくても、より多くの情報をテキスト内に詰め込むことが可能になります。

5. 「落とし穴」（仮定）

著者らは、大きな仮定を置いていることを認めています。彼らは、「置換されたパズル（シャッフルされたモザイク）」が、真にランダムな塵と区別することが不可能であるということに賭けています。

彼らは、これが数学的に解読不可能であることを（厳密に）証明したわけではありません（この特定のタイプのパズルについては、まだ誰も証明できていません）。
しかし、彼らは以下のことを示しました：
1. これは、別の有名な、よく研究されている暗号学的仮定（Permuted Puzzles）によって示唆されています。
2. 彼らは、さまざまな種類の攻撃（例えば、塵の中にパターンを探すような攻撃）を用いてこのシステムを打破しようと試みましたが、失敗しました。
3. 彼らは、もし3つのステップ（シャッフル、塗り替え、または塵まき）のいずれか一つでも欠けていれば、システムが簡単に破られてしまうことを証明しました。これは、3つのステップすべてが必要であり、システムが堅牢であることを示唆しています。

まとめ

この論文は、AI生成テキストに対する、極めて安全な新しいウォーターマーク（透かし）の手法を紹介しています。これは、以下のすべてを実現した最初のシステムであると主張しています。

検知がほぼ不可能である（通常のテキストに見える）。
重度の編集（タイポ、削除、書き換え）にも耐えられる。
攻撃者が秘密の鍵を知っている場合でも機能する。

彼らは、テキストを「シャッフルされたパズル」へと変えることでこれを達成しており、その仕組みは、広範なテストと確立された他の数学理論との関連性に基づいた、非常に妥当性の高い新しい数学的仮定に依存しています。

技術要約：置換パズルから得られる改良型擬似乱数符号

問題提起

AI生成コンテンツの普及に伴い、その出自を特定するための堅牢なウォーターマーキング・スキームが必要となっている。近年の研究により、**擬似乱数符号（Pseudorandom Codes: PRC）**は、強力なロバスト性と品質保証を備えたウォーターマーキング・スキームと等価であることが確立された。PRCとは、暗号文が一様分布と計算量的に区別不能であり（これにより不可知性／品質を保証）、復号アルゴリズムが高いエラー率を許容する（これによりロバスト性を保証する）、秘密鍵を用いた暗号化スキームである。

しかし、既存のPRC構成には、以下の3つの決定的な限界が存在する：

脆弱なセキュリティ： 従来の構成はすべて、準多項式時間での識別攻撃に対して脆弱である。これらは $(\log n)$ -スパースな構造を隠蔽することに依存しており、それが総当たり探索攻撃を許してしまう。
限定的なアルファベットのロバスト性： エディット（編集）エラーを扱う構成はあるものの、それらは多項式サイズのアルファベットを必要とする。現実のテキスト（LLMなどによるもの）は低エントロピー（単語あたり約1ビット）であるため、定数サイズの（理想的にはバイナリの）アルファベットに対してエディット耐性を持つPRCが必要である。
弱い敵対者モデル： 従来の先行研究は、敵対者が計算量的に制限されているか、あるいは検出鍵を持っていないことを前提としていた。PRCが、検出鍵を保持している計算量的に無制限な敵対者に対してもロバスト性を維持できるのか（強適応的ロバスト性）は不明であった。

中心となる未解決の問いは、単一の構成によって、劣指数セキュリティ、バイナリ・アルファベット上でのエディット耐性、および鍵保持者に対するロバスト性を同時に達成できるか、という点であった。

手法

1. 置換符号予想（The Permuted Codes Conjecture）

著者らは、新たな計算量的困難性仮定である置換符号予想を導入している。この予想は、「スクランブル（撹乱）されたノイズを含む符号語」の分布が、一様分布と計算量的に区別不能であると仮定するものである。

分布 $D_{n,\Sigma,C,\eta,T}$ は以下のように生成される：

ランダムなインデックス置換 $\sigma \in S_n$ と、アルファベット置換 $\pi_1, \dots, \pi_n \in S_\Sigma$ をサンプリングする。
$T$ 個の符号語 $c_1, \dots, c_T$ を、線形符号 $C \subseteq \Sigma^n$ から一様にサンプリングする。
各符号語に対し、インデックスを $\sigma$ によって置換し、各位置のシンボルを $\pi_j$ によって置換することで、 $\hat{c}$ を得る。
$\hat{c}$ に対して、ノイズ率 $\eta$ の置換チャネルを適用する。

重要な洞察： 著者らは、この予想が（二重効率的なプライベート情報検索において以前使用された）置換パズル予想（Permuted Puzzles Conjecture）によって示唆されることを証明している。定数サイズのアルファベットと高次双対距離を持つ符号の場合、対数個のサンプルは統計的に一様であることを統計的証拠により示している。さらに、これら3つの要素すべて（インデックス置換、アルファベット置換、およびノイズ）が必要であることを実証している。アルファベット置換を省略した場合（「トイ」バージョン）、低次多項式攻撃によってリード・ソロモン符号が識別可能になってしまう。

2. エディット耐性を持つPRCの構成

バイナリ・アルファベット上でのエディット耐性を実現するために、著者らは折り畳みリード・ソロモン（Folded Reed-Solomon: FRS）符号に基づくPRCを構築する。

エンコーディング： 秘密鍵は置換とワンタイムパッドで構成される。エンコード時には、基礎となる符号からランダムな符号語を選択し、置換、ノイズ付加を行い、その後にシンボルのサブセットを選択する。極めて重要な点は、選択された各シンボルが、シンボルの値とそのインデックスの両方を含むバイナリ文字列として出力されることである。
デコーディング： デコーダは、エディット（挿入・削除）によって破損した可能性がある文字列を受け取る。デコーダは特定の長さのすべての部分文字列をスキャンし、潜在的な $(index, symbol)$ ペアを復元するために「総当たり」的にエディット距離を試行する。これらの候補は各位置に対するリストを形成する。その後、元の符号語を復元するために、基礎となる符号のリスト復元アルゴリズムが適用される。
ロバスト性のメカニズム： 出力にインデックスを含めることで、挿入や削除によって位置がずれたとしても、エディット数が制限されている限り、デコーダは正しいシンボルを復元できる。FRS符号の使用により、アルファベットが事実上バイナリ（変換を介して）であっても、定数割合のエディットを許容できる。

3. ウォーターマーキングへの変換

ChristおよびGunn (CRYPTO '24) によって確立されたフレームワークを用い、著者らは自らのPRCを自己回帰型言語モデルのためのウォーターマーキング・スキームへと変換する。このスキームは、トークンの選択をPRC符号語のビットへとバイアスさせることで、ウォーターマーク付きテキストを生成する。エディットに対するPRCのロバスト性は、モデルが十分なトークンあたりのエントロピーを持つ限り、テキストの敵対的な修正に対するウォーターマークの生存能力に直接的に反映される。

主な貢献と結果

1. 3つの特性を備えた新しいPRC構成

本論文は、以下の3つを同時に満たす初のPRC構成を提示している：

妥当な劣指数セキュリティ： 準多項式攻撃に対して脆弱な疎な構造を回避する、置換符号予想に基づいている。
バイナリ・アルファベットのエディット耐性： 本構成は、バイナリ・アルファベットにおける最悪ケースの定数レートのエディット（挿入、削除、置換）を許容する。
強適応的ロバスト性： 検出鍵を知っている計算量的に無制限な敵対者に対しても、ロバスト性を維持する。

2. 理論的保証

定理 5.6： 置換符号予想の下で、劣指数セキュリティを持ち、定数レートのエディットに対して強適応的なバイナリ・アルファベットPRCが存在する。
定理 5.14： 折り畳みリード・ソロモン符号に関する予想の変種の下で、定数レートの（ $\tilde{O}(\alpha^7)$ ）エディットに対して、かつ定数レートのトークンあたりエントロピー $\alpha$ のみを必要とする、不可知なLLMウォーターマークが存在する。これは、現実的なエントロピー制約下で、最悪ケースのエディットに対して不可知性とロバスト性の両立を実現した初のウォーターマークである。

3. 暗号解読と証拠

アルファベット置換の必要性： 著者らは、インデックス置換とノイズがあっても、アルファベット置換がない場合、リード・ソロモン符号は効率的に識別可能であることを証明した。
従来研究への準多項式攻撃： 従来の広範なPRC構成（植え付けられた疎な構造やノイズ耐性のある述語に依存するもの）は、本質的に準多項式時間の攻撃に対して脆弱であることを示した。
統計的一様性： 定数サイズのアルファベットにおいて、少数の置換された符号語は統計的に一様分布と区別不能であることを証明し、予想の妥当性を裏付ける証拠を提供した。

意義

本論文は、これまで互いに排他的または達成不可能と考えられていた、PRCの3つの望ましい特性間の緊張関係を解消したと主張している。置換符号予想を定式化し、折り畳みリード・ソロモン符号を活用することで、著者らは以下の特性を持つウォーターマーキング・スキームの理論的基盤を提供している：

不可知性（Undetectable）： 真の言語モデルの出力と区別不能である。
ロバスト性（Robust）： テキストへの敵対的なエディット（挿入・削除）に耐えうる。
安全性（Secure）： 検出鍵を持つ攻撃者に対してもロバストであり、ロバスト性を損なうことなく公開検証を可能にする。

この研究は、これらの特性を達成するためには、疎な構造を超えて、置換されノイズを含む符号語をランダムな文字列と区別することの困難さを受け入れる必要があることを示している。セキュリティは新たな予想に基づいているが、著者らはその妥当性を示す強力な証拠を提示し、実用的な、堅牢なAI生成テキスト用ウォーターマークの存在を実証している。