💻 computer science

Synchronization-Free Algebraic Fingerprints for Large Language Models: From Autoregressive to Diffusion Models

本論文は、リード・ソロモン多項式と二進合同式を用いてトークン対に秘密の識別情報を埋め込むことにより、ブロック同期を必要とせずに、編集、言い換え、およびトークンの並べ替えに耐性を持つ堅牢な属性特定を可能にする、大規模言語モデルのための新しい同期フリーの電子透かし手法を提案する。

原著者： Jaroslaw Janas, Josef Pieprzyk, Pawel Morawiecki

公開日 2026-07-21

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

CC BY 4.0

原著者： Jaroslaw Janas, Josef Pieprzyk, Pawel Morawiecki

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

あなたは、非常に有能だが少しいたずら好きなロボットが作った砂の城の山に、秘密の署名を残そうとしているところだと想像してください。このロボットは、物語を書き、質問に答え、コードを作成する人工知能（AI）です。問題は、このロボットが人間のスタイルを模倣するのがあまりに上手いため、書かれた物語が人間によるものか機械によるものか判別することが不可能なことです。さらに悪いことに、もし誰かがその物語を「修正」しようとした場合（文章を削除したり、ジョークを加えたり、段落を入れ替えたりした場合）、その署名は通常、潮が満ちてきた時の足跡のように消し去られてしまいます。

科学者たちは、テキストの中に目に見えないコードを刻み込むことでこれを解決しようとしてきましたが、その手法のほとんどは、長い、壊れやすい「ペーパークリップの鎖」のようなものでした。もしペーパークリップを一つ抜いたり（単語の削除）、新しいものを一つ加えたり（単語の挿入）すると、鎖全体が切れ、秘密のメッセージは失われてしまいます。この新しい論文は、この問題に対する全く異なる考え方を提示しています。それは、壊れやすい鎖ではなく、何千もの小さな、独立した「ホタル」の野原を想像することです。それぞれのホタルは、秘密のコードの小さな断片を運んでいます。もし嵐（編集者）が吹き荒れてホタルの半分を吹き飛ばしたり、あるいは彼らが異なる順番で飛んでいたとしても、あなたはまだ秘密のメッセージを解読することができます。なぜなら、それらは一列に並んでいる必要はなく、ただ、いくつかのホタルがそこに存在していればよいからです。研究者たちは、多項式（数字の秘密のレシピのようなもの）を用いた数学的なトリックを用い、テキストの編集を「確率のゲーム」として扱うことで、編集された後でもAIの秘密の正体を復元できることを示しています。

問題点：「鎖」対「雲」

長い間、研究者たちは、秘密のメッセージをビーズの紐のような厳格なシーケンスとして整理することで、AIのテキストにウォーターマーク（電子透かし）を入れようとしてきました。彼らは、「最初の単語には秘密の印を、二番目の単語には次の印を、といった具合に」と考えてきました。これは、テキストが編集されない場合にはうまく機能します。しかし、誰かがテキストを編集すると、問題が発生します。もし最初の単語を削除すれば、二番目の単語が突然「最初」の単語になり、秘密のコード全体がバラバラになってしまいます。これは、本から5ページ目を破り取った途端に、6ページ目が5ページ目になってしまい、物語が意味をなさなくなるようなものです。これは「同期（シンクロニゼーション）」問題と呼ばれます。検出器（ウォーターマークをチェックする人）は、手がかりの順序が変わってしまったために混乱してしまいます。

この論文の著者たちは、このような「鎖」のアプローチは、編集される可能性のあるテキストに対して根本的に欠陥があると考えています。彼らは、劇的な転換を提案しています。つまり、順序に依存することを完全に止めることです。鎖ではなく、「雲」のように、独立した手がかりの集まりを提案しているのです。

解決策：独立したホタルと秘密のレシピ

この論文の核心となるアイデアは、「同期フリー（synchronization-free）」のウォーターマークです。その仕組みは、秘密のレシピと隣人同士の関係を用いた比喩を使って説明できます。

AIが物語を一つ一つの単語を書き進めていく様子を想像してください。研究者たちは、隣り合う単語のペア（「単語A」と「単語B」と呼びましょう）ごとに、システムが秘密の「レシピ」（数学的な多項式）をチェックし、単語Bがどのような「風味」を持つべきかを決定することを提案しています。

秘密のレシピ: AIの所有者は、秘密のアイデンティティ（32ビットまたは128ビットの数値のようなもの）を持っています。彼らはこの数値を数学的な公式に変換します。
隣人: すべての単語のペアに対して、システムは最初の単語を見て、公式上の特定の「テストポイント」を選択します。
決定: 公式は結果を出します。もし結果が「偶数」であれば、二番目の単語は「タイプ1」の単語（名詞など）でなければなりません。もし結果が「奇数」であれば、二番目の単語は「タイプ2」の単語（動詞など）でなければなりません。
魔法: 重要なのは、単語Bに対するこの決定が、単語Aと秘密のレシピのみに依存しているという点です。単語Aの前で何が起きたか、あるいは単語Bの後に何が来るかについては一切関知しません。

各単語のペアが自己完結した「ホタル」であるため、単語Aを削除したり、単語AとBの間に新しい単語を挿入したり、段落全体をシャッフルしたりしても問題ありません。残されたペアは、それぞれ独立した手がかりを保持しています。もし十分な数のペアが残っていれば、数学的に元の秘密のレシピを再構成することができます。

どのように機能することを証明したか

著者たちは、これが機能すると単に推測したのではなく、数学的モデルを構築して証明しました。彼らは、テキストの編集プロセス（単語の削除、単語の変更）を「バイナリ対称通信路（Binary Symmetric Channel）」として扱いました。簡単に言えば、あらゆる編集ミスを単純なコイン投げとして扱ったのです。つまり、手がかりが正しいか、あるいは間違った答えに反転しているか、という選択です。

彼らは、秘密を復元するためにどれほどの手がかり（単語のペア）が必要かを計算するために、数学を実行しました。

結果: 彼らは、非常に少ない「余分な」テキストで済むことを見出しました。たとえテキストが激しく編集されていても（手がかりの30%が間違っているか欠落していても）、32ビットの秘密のコードを99%の信頼度で復元するために、わずかな追加の文章があれば十分でした。
比喩: もしあなたがコイン投げによって32ビットのパスワードを当てようとしていて、投げた結果の30%が間違っていたとしたら、通常は行き詰まってしまうでしょう。しかし、彼らの数学は特別な種類のコード（リード・ソロモン符号）を使用しているため、それはまるで、十分な数の投げさえあれば、間違った結果を修正できる「魔法のデコーダーリング」を持っているようなものです。

彼らはまた、非常に長い秘密（128ビットなど）を扱う方法についてもテストしました。彼らは、大きな秘密を小さな塊（フラグメント）に分割し、各塊を独立したホタルの雲として扱うことで、膨大な量のテキストを必要とせずに全体を復元できることを見出しました。

他の種類のAIについては？

この論文は、より新しいタイプのAIである「拡散モデル（Diffusion Models）」についても考察しています。標準的なAIが左から右へと一文字ずつ書いていく（タイピストのように）のに対し、拡散モデルは、彫刻家が石を削り取って像を見つけ出すように、乱雑でバラバラな文章から始めて、徐々にそれを整えていきます。

著者たちは、彼らの「独立したホタル」方式がここでも完璧に機能することに気づきました。彼らは、AIがテキストを整える過程でどのようにウォーターマークを「コミット（確定）」させるかについて、3つの異なる方法を提案しました。

基本コミット (Basic Commit): AIは、左側の隣人のルールに適合した瞬間に単語をロックします。これは高速ですが、もし間違いが生じた場合、それを修正することはできません。
洗練されたコミット (Refined Commit): AIは両側の隣人をチェックします。もし一方の隣人が「イエス」と言い、もう一方が「ノー」と言った場合、エラーを修正するために隣人の判断を変えることがあります。これはより賢い方法ですが、少し時間がかかります。
スライディング・コミット (Sliding Commit): AIは、「ロックされた」単語と「アンロックされた」単語の境界線を、スライドドアのように扱います。すべてが完璧に適合するまで、ドアを前後に動かします。これが最も堅牢ですが、最も時間がかかります。

彼らのシミュレーションによれば、標準的なAIの場合、「基本」の方法で十分高速であることが示唆されています。拡散モデルの場合、「洗練された」方法が、エラーを修正しながら進むための良いバランスを提供します。

結論

この論文は、編集に対して非常に強い、AIテキストのタグ付けに関する新しい方法を示唆しています。以前の手法は、テキストが編集されると崩壊してしまいますが、この手法は、すべての手がかりが独立して存在するため、削除、挿入、およびシャッフルに対しても耐性があります。著者たちは、数学とシミュレーションを通じて、テキストが激しく編集されたとしても、高い信頼度でAIの秘密の正体を復元できることを示しました。また、標準的なテキスト生成器と、より複雑な拡散モデルの両方にどのように実装するかについてのロードマップも提供しています。

彼らは、あらゆる複雑な編集パターンを解決したと主張しているわけではありません（将来の研究では、より複雑な編集パターンを調査できる可能性があると述べています）。しかし、彼らは、ウォーターマークを以前よりもはるかに信頼性の高いものにする、数学的に証明された強力なフレームワークを提供しました。それは、壊れやすい「鎖」を作ることから、弾力性のある「雲」を作るへの転換なのです。

技術要約：大規模言語モデルのための同期フリー代数指紋法

1. 問題提起

大規模言語モデル（LLM）の普及に伴い、生成されたテキストの帰属を特定し、責任を明確にし、悪用を検知するための信頼性の高いウォーターマーキング手法への切実なニーズが生じている。既存のLLM向けウォーターマーキング・スキームは、一般に統計的、語彙的、構文的、または暗号学的なカテゴリに分類される。しかし、現在の手法の多くにおける根本的な限界は、その同期依存性にある。これらの手法は通常、ウォーターマークのビットを逐次的に、あるいは固定サイズのブロック内に埋め込むため、トークンの正確な位置順序に依存している。その結果、挿入、削除、パラフレーズ（言い換え）、あるいは文の並べ替えといった一般的な編集操作によって、エンコーダとデコーダの間のアライメント（整列）が破壊され、ウォーターマークが回収不能となる。本論文は、任意のテキスト編集後でも信頼性の高い検出が可能な**同期フリー（同期不要）**なウォーターマーキング技術の開発が、この分野における主要な未解決問題であると指摘している。

2. 手法

著者らは、回収時に明示的なトークン・アライメントを必要としない新しいウォーターマーキング・フレームワークを提案する。核心となる革新は、リード・ソロモン符号に基づく代数的指紋法であり、そこではすべてのウォーターマーク・ビットが、隣接する一対のトークンに対して独立して埋め込まれる。

2.1 代数的フレームワーク

アイデンティティの表現: 秘密のアイデンティティ $S$ は、 $n$ ビットのバイナリ・ベクトルとして表され、有限体 $\mathbb{F}_q$ （ここで $q > 2^n$ は奇素数）上の次数が最大 $n-1$ の多項式 $f_S(x)$ にマッピングされる。
バイナリ・フィンガープリント: スキームは、完全な体値 $f_S(\alpha)$ を送信する代わりに、単一のバイナリ観測値、すなわち評価のパリティ $\phi_S(\alpha) = f_S(\alpha) \pmod 2$ を抽出する。
埋め込みメカニズム: すべての連続するトークン対 $(t_i, t_{i+1})$ $(t_{i}, t_{i + 1})$ に対して：
1. 第1トークン $t_i$ は、一意の評価点 $\alpha_i = H(K, \text{id}(t_i)) \pmod q$ を決定する。ここで $H$ は暗号学的ハッシュであり、 $K$ は秘密鍵である。
2. ウォーターマーク・ビット $w_i = \phi_S(\alpha_i)$ が計算される。
3. 第2トークン $t_{i+1}$ は、特定のトークン・クラス（例：「グリーン」または「レッド」）に属するように生成（または偏向）される。このクラスは、ビット値 $w_i$ に対応している。
独立性: 各ビットはローカルなトークン対と秘密鍵のみに依存するため、あるビットの埋め込みは、以前のビットの位置や状態に依存しない。

2.2 回復とデコーディング

回復には、トークンが元の順序である必要はない。検出器は生存しているトークン対の集合を収集し、秘密鍵を用いて評価点 $\alpha_j$ を再計算し、対応するビット $\hat{w}_j$ を観測する。目標は、すべての観測されたペアに対して $\phi_S(\alpha_j) = \hat{w}_j$ を満たす一意のアイデンティティ $S$ を見つけることである。

アルゴリズム: 本論文は、アイデンティティのサイズに基づいた3つの回復アルゴリズムを提案している：
1. 全探索 (Exhaustive Search): 小規模な $n$ ( $n \lesssim 20$ ) の場合。
2. 中間一致法 (Meet-in-the-Middle): 中規模な $n$ ( $20 < n \le 60$ ) の場合。計算量を $O(2^n)$ から $O(2^{n/2})$ に低減する。
3. 断片化 (Fragmentation): 大規模なアイデンティティの場合、秘密を独立した断片に分割し、より小さな部分問題の並列的な回復を可能にする。

2.3 破損のモデリング

著者らは、ウォーターマーキング・プロセスを二元対称通信路 (Binary Symmetric Channel: BSC) としてモデル化している。挿入、削除、置換、および埋め込みの不完全性は、すべて単一のクロスオーバー確率 $p$ に抽象化できると彼らは主張している。

挿入/削除: ブロックベースの手法では、単一の削除がそれ以降のすべてのビットをシフトさせるが、本手法では、挿入や削除は特定の独立した観測を削除または追加するだけに過ぎない。検知されない編集の確率は約 $1/4$ であることが示されており、ほとんどの編集は検知可能な不整合を導入する。
回復確率: 回復の成功確率は、生存している正しい観測の数 $r$ のみに依存する。もし $r \ge n + \lambda$ であれば、失敗確率は $2^{-\lambda}$ で抑えられる。

2.4 拡散モデルへの拡張

本フレームワークは、テキストを自己回帰的ではなく反復的に生成する拡散言語モデル（DLM）へと拡張されている。著者らは、デノイジング（除去）プロセス中にウォーターマークの制約を強制するための3つの「コミット・アルゴリズム」を提案している：

基本コミット (Basic Commit): 左側の制約が満たされている場合にトークンを確定（コミット）する。
洗練されたコミット (Refined Commit): 左側の制約に基づいてコミットを行うが、右側の制約が失敗した場合には隣接するトークンを取り消す（リボーク）ことで、局所的な自己修正を可能にする。
スライディング・コミット (Sliding Commit): コミット済み領域と未コミット領域の境界が移動することを許容し、局所的な不整合を解決するためにプロセスをランダムウォークとして扱う。

3. 主な貢献

本論文の貢献は以下のようにまとめられる：

同期フリー・フレームワーク: すべてのウォーターマーク・ビットを独立して埋め込む手法であり、回復時のトークン・アライメントの必要性を排除する。
リード・ソロモン符号: 位置に関わらず、十分に大きな正しい観測の集合からアイデンティティを再構成する構成。
BSC モデリング: すべての破損源（埋め込みエラーと編集）を単一の二元対称通信路としてモデル化できることを示し、経験的な評価ではなく、原理的な数学的評価による堅牢性の検証を可能にした。
確率公式: 指定された信頼レベルで成功裏に回復するために必要な最小限のテキスト長を予測する、厳密および近似的な公式の導出。
スケーラビリティ: 長いアイデンティティを断片に分割することで、同期フリーの特性を維持しながら計算複雑性を低減する軽量なバリアント。
拡散モデルへの拡張: 効率的なトークン・コミット・アルゴリズムと確率的解析を備えた、拡散ベースのモデルへのフレームワークの拡張。

4. 結果と分析

堅牢性: 分析によれば、高いトークン破損率であっても、信頼できる回復にはわずかな冗長性しか必要としない。例えば、32ビットのアイデンティティを、エラー率 $p=0.3$ の通信路において99%の信頼度で回復するには、わずか25個の追加のトークン対（合計57ペア）が必要である。
効率性: 「中間一致法」により、標準的なワークステーションで $n \approx 60$ ビットまでのアイデンティティの現実的な回復が可能となる。断片化により、任意に長いアイデンティティの処理が可能になる。
拡散の収束:
- 基本コミットアルゴリズムは $O(\ln N / \epsilon)$ の反復で収束する。
- スライディング・コミットアルゴリズムは $O(N)$ の反復で収束するが、局所的な不整合が凍結されるのではなく、最終的に解決されることを保証する。
- 洗練されたコミットアルゴリズムは、初期のコミット速度は速いが、「チャーン（撹乱）」を導入し（有効なコミットを取り消す）、基本アプローチと比較してシーケンス全体の安定化を遅らせる可能性がある。

5. 重要性と主張

本論文は、その主要な意義は、LLMのウォーターマーキングにおける根本的な障壁であった同期問題の解消にあると主張している。ウォーターマーク・ビットをその逐次的な位置から切り離すことで、提案手法は既存のスキームを無効にするような編集操作に対しても堅牢性を維持する。

さらに、著者らは評価方法論の転換を提唱している。急速に陳腐化するモデル固有の広範な実験に頼るのではなく、二元対称通信路（BSC）の抽象化を使用することを提案している。これにより、単一のパラメータである実効エラー確率 $p$ に基づいて、異なるモデルや編集戦略にわたるウォーターマーキング・スキームの原理的な数学的比較が可能になる。

本論文は、BSCは簡略化ではあるものの、すべての編集操作が最終的には回収されたパリティ・ビットにおける独立したエラーとして現れるため、同期フリー・スキームにとって極めて有用な近似を提供すると結論付けている。このアプローチは、回復確率に関する明示的な保証を提供し、堅牢なウォーターマーキング・システムの設計を簡素化するものである。