Green/Red Listウォーターマーク（グリーンレッドリストウォーターマーク）
LLMウォーターマーキングにおいて語彙をGreen List（透かしトークン）とRed List（非透かしトークン）に分割し、Green Listからの選択確率を操作する基本的な分割メカニズム。
Green/Red Listウォーターマークとは
Green/Red Listウォーターマーク（Green/Red List Watermark）は、LLMのウォーターマーキングにおける最も基本的かつ広く採用されているメカニズムである。Kirchenbauer et al.（2023）が提案したこの方式では、トークン生成の各ステップで語彙集合をGreen List（選択を促進するトークン群）とRed List（選択を抑制するトークン群）に動的に分割する。
動作原理
分割の生成
各トークン位置 t で以下の手順を実行する：
- シード生成: 直前のトークン s_{t-1} と秘密鍵 k を入力としてハッシュ値 H(s_{t-1}, k) を計算
- 擬似乱数生成: ハッシュ値をシードとして擬似乱数生成器を初期化
- 語彙分割: 語彙 V の各トークンを確率 γ で Green List、(1-γ) で Red List に割り当て
- logit操作: Green List トークンの logit にバイアス δ を加算
γ（ガンマ）パラメータ
γ はGreen Listの比率を制御するパラメータ。
| γ値 | Green List比率 | 検出特性 | 品質影響 |
|---|---|---|---|
| 0.25 | 25% | 高感度（少数のGreenで有意差検出） | 品質低下小 |
| 0.50 | 50%（標準） | バランス型 | 標準 |
| 0.75 | 75% | 低感度（多数のGreenで差が薄まる） | 品質低下大 |
γ=0.5が標準設定で、Green ListとRed Listが等分される。
検出の統計量
z-score 検定
テキスト中のGreen Listトークン数 |G| に対して：
z = (|G| - γT) / sqrt(γ(1-γ)T)
- T: 総トークン数
- γ: Green List 比率
- z > 4.0 → ウォーターマーク有りと判定（p < 0.00003）
検出閾値の設定
| 用途 | z閾値 | 偽陽性率 | 必要トークン数（γ=0.5） |
|---|---|---|---|
| スクリーニング（広く検出） | 2.0 | 2.3% | 約50 |
| 標準判定 | 4.0 | 0.003% | 約100 |
| 高信頼判定 | 6.0 | <0.000001% | 約200 |
| 法的証拠レベル | 8.0 | 実質0% | 約400 |
Green List の動的性質
Green/Red Listの最も重要な特性は、前のトークンが変わるたびにリストの構成が完全に変わることである。これにより：
- 文脈依存性 — 同じ単語でも文脈によってGreen/Redの割り当てが変化
- 予測不能性 — 秘密鍵なしでは分割パターンを予測できない
- 一様分布 — 人間のテキストではGreen率がγに収束（ウォーターマークなし）
Unigram方式との対比
| 特性 | 標準Green/Red（Context-dependent） | Unigram方式（Context-free） |
|---|---|---|
| 前トークン依存 | あり（ハッシュにシード使用） | なし（固定分割） |
| パラフレーズ耐性 | 低い（前トークン変更で破壊） | 高い（文脈非依存） |
| 検出精度 | 高い（偽陽性少ない） | やや低い（固定パターンのバイアス） |
| 実装複雑度 | 中程度 | 低い |
実装における注意点
低エントロピー領域の処理
固有名詞、数値、定型表現など選択肢が限られるトークン位置では、Green Listトークンが存在しない可能性がある。この場合の対処法：
- スキップ方式: エントロピーが閾値以下のトークンではδ加算をスキップ（品質保持優先）
- 適応的δ方式: エントロピーに比例してδを調整（Kuditipudi et al. 2024）
- 強制選択方式: Red Listでも最も確率の高いトークンを選択（検出精度優先）
ハッシュウィンドウサイズ
標準のKirchenbauer方式は直前1トークンのみをハッシュシードに使用（h=1）。ウィンドウサイズを拡大すると：
| h値 | ロバスト性 | 計算コスト | 検出精度 |
|---|---|---|---|
| 1 | 低（1トークン変更で破壊） | 最小 | 高 |
| 2 | 中 | 低 | 高 |
| 4 | 高（4トークン連続変更が必要） | 中 | やや低下 |
攻撃手法と対策
Green List 推定攻撃
攻撃者が同じプロンプトを繰り返し投入し、出力トークンの分布からGreen Listを推定する攻撃。対策としてプロンプト依存のハッシュシードを導入する手法がある。
トークン置換攻撃
Green Listトークンを意図的にRed Listの同義語に置換する攻撃。セマンティックウォーターマーク（文意レベルでの埋め込み）で対抗。
よくある質問
Q1: Green ListとRed Listの名前の由来は？
A1: 交通信号のアナロジー。Green=「進め」（選択促進）、Red=「止まれ」（選択抑制）を意味する。実際にはトークンの使用を完全に禁止するわけではなく、確率を操作するだけである（ソフトウォーターマークの場合）。
Q2: Green Listの比率は固定ですか？
A2: 標準実装ではγ=0.5で固定だが、適応的な手法ではトークンごとにγを変動させる。高エントロピーの位置ではγを大きく（検出しやすく）、低エントロピーの位置ではγを小さく（品質維持）する。
Q3: 複数のウォーターマークを同時に埋め込めますか？
A3: 理論的に可能だが、各ウォーターマークのδが干渉し合い、検出精度と品質が共に低下する。Multi-bit方式を使えば、単一のウォーターマーク内に複数の情報ビットを埋め込める。