💻 computer science

Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes

本論文は、LDPCベースの擬似乱数誤り訂正符号（PRC）に対する初の暗号解読を提示するものであり、新たな攻撃と実世界での実験を通じて、それらが主張するセキュリティ保証が、実用的な生成モデル・ウォーターマーキングのアプリケーションにおいて根本的に損なわれていることを実証すると同時に、具体的な防御策を提案し、その固有のセキュリティ限界を明確にするものである。

原著者： Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

公開日 2026-06-16

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

CC BY 4.0

原著者： Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

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

全体像：欠陥のある「見えないインク」

AI（人工知能）のために設計された、新しいタイプの「見えないインク」を想像してみてください。このインクは、AIが生成したテキストや画像に、誰にも見えず、消すこともできない秘密の印（ウォーターマーク）を刻むために使われるはずのものです。その目的は、そのコンテンツが特定のAIによって作られたものであることを証明することですが、その印は見えず、拭い去ることもできません。

この「見えないインク」は、PRC（擬似乱数誤り訂正符号）と呼ばれています。開発者は、これは数学的に解読不可能であると主張していました。

しかし、清華大学と山東大学の研究チームは、「セキュリティテスター」の役割を果たすことにしました。彼らは、このインクを壊そうと試みたのです。彼らの結論はこうです。「このインクは漏洩している」。彼らは、見えない印を見つけ出すか、あるいは印を洗い流してしまう3つの異なる方法を発見しました。これにより、この技術の現行バージョンは、宣伝されているほど安全ではないことが証明されました。

インクを壊した3つの方法

研究者たちは、このインクを作るための特定のレシピであるLDLC-PRCに焦点を当てました。彼らは、このレシピの中に3つの明確な「抜け穴」を発見しました。

1. 「部分的な鍵」による強奪（攻撃I）

比喩: 見えないインクの秘密の鍵が、数千ものツムブラー（回転体）を持つ巨大で複雑なダイヤル錠だと想像してください。公開鍵はその錠に対するヒントです。研究者たちは、わずか数個のツムブラーだけを特定する方法（秘密鍵の一部を復元する方法）を見つけ出しました。
意味: たとえ「鍵のすべて」を持っていなくても、ほんの少しの断片さえあれば、ある画像やテキストに「ウォーターマーク」が入っているか、通常の物であるかの違いを判別できてしまいます。それは、窓が一つだけ少し開いているのを見ただけで、その家が施錠されているかどうかを判断できるようなものです。
結果: 彼らは、比較的少ない計算能力を用いて、ほぼ完璧な精度でウォーターマークを検出することができました。

2. 「重複したページ」のミス（攻撃II）

比喩: 錠を作るためのレシピには、独自のパターンを作るためにトランプのデッキをシャッフルする工程が含まれています。研究者たちは、そのシャッフルマシンが故障していることに気づきました。時々、マシンはデッキの中に全く同じカードのパターンを2回、誤って印刷してしまうのです。
意味: 「シャッフル（鍵の生成）」が十分にランダムではなかったため、一部の「錠（鍵）」が脆弱になっていました。攻撃者がこれらの弱い錠を見つければ、即座にウォーターマークを特定できます。
結果: 開発者が提案した多くの設定において、これらの「弱い錠」はほぼ100%の確率で発生します。それは、著者が誤ってすべてのページに同じ文章を書いてしまった本の中に、秘密を隠そうとするようなものです。

3. 「ノイズの重ねがけ」（攻撃III）

比喩: この見えないインクは、多少の雨（ノイズ）には耐えられるように設計されています。紙に少し水をかけても、インクは見えたままです。しかし、研究者たちは、肉眼では普通の水の量に見えるのに、インクの読み取り能力を打ち消してしまう「特定の種類の水」をかける方法を見つけ出しました。
意味: 彼らは、テキストや画像に、計算された微量の「静止（スタティック）」や「ノイズ」を加える方法を見つけました。このノイズは、画像や物語を台無しにすることはありませんが、デコーダー（復号器）を混乱させ、ウォーターマークが存在しないと思い込ませるのに十分なものです。
結果: 彼らは、画像がぼやけたりテキストが支離滅裂になったりすることなく、ウォーターマークを完全に除去することに成功しました。

実世界でのテスト：実際のAIでは機能するか？

研究者たちは、単に紙の上で数学的な計算をしただけではありません。実際のAIモデルに対してテストを行いました。

テキストの場合 (LLMs): 彼らはDeepSeekというモデルのテキストに対してウォーターマークのテストを行いました。そこで重大な問題を発見しました。ウォーターマークを検出可能にするためには、AIが非常にランダムで質の低い書き方（まるでロボットが幻覚を見ているような状態）をしなければなりませんでした。AIが良質で自然なテキストを書くと、ウォートマークは消えてしまいます。逆に、ウォーターマークが存在する場合、テキストは読めないものになってしまいます。判定：高品質なテキストにおいては、実用性に乏しい。
画像の場合 (GIMs): 彼らはStable Diffusionに対してテストを行いました。こちらでは、攻撃は完璧に機能しました。彼らは高い成功率でウォーターマークを検出し、除去することができました。これは、セキュリティの主張が虚偽であることを証明しています。

「修正策」と、なぜそれが困難なのか

研究者たちは、これらの穴を塞ぐための3つの方法を提案しました。

数字を変える: 「錠」をより大きく、より複雑にする。
シャッフルを直す: 重複を作らないように、鍵を生成するコードを書き換える。
ノイズを増やす: 「ノイズの重ねがけ」攻撃が効かないよう、より多くの「雨」に耐えられるようにする。

落とし穴:
真に安全なレベル（ゴールドスタンダードである128ビットのセキュリティ）を実現するために、研究者たちは、ウォーターマークは現在のAIが一度に書ける最大量よりも長くなる必要があると計算しました。

比喩: それは、100ページの契約書をポストカードに詰め込もうとするようなものです。現在のAIモデル（GPT-4など）には、安全なウォーターマークを保持するための「スペース（出力長）」がそもそも足りていないのです。

結論

この論文は、新しいAIウォーターマーク技術に対する「ストレス・テスト」です。

良いニュース: 研究者たちは欠陥を発見し、それを修正する方法を提示しました。
悪いニュース: 現在のバージョンのこの技術は、安全ではありません。簡単に検出され、あるいは除去されてしまいます。
現実的な視点: 修正を行ったとしても、この技術は物理的な限界に直面しています。現在のAIモデルは、真に解読不可能なウォーターマークを保持するには短すぎるのです。

著者たちは、アイデア自体は有望であるものの、大幅な変更なしには、AIコンテンツを保護するためにこの特定の「見えないインク」を信頼することはできないと結論付けています。

技術要約：LDPCベースの擬似乱数誤り訂正符号の暗号解読

問題提起

CRYPTO 2024で発表された擬似乱数誤り訂正符号（PRC）は、大規模生成モデル（LLM）および生成画像モデル（GIM）に対して検知不可能なウォーターマーキングを可能にするために設計された、新しい暗号プリミティブである。LDPC-PRCとして知られるLDPC-PRCの主要なインスタンス化は、低密度パリティ検査符号に依拠しており、LPN（Learning Parity with Noise）および植え付けられたXOR問題の困難性に基づいたセキュリティを主張している。

強力な理論的漸近保証にもかかわらず、実用的なパラメータ設定下におけるLDPC-PRCの具体的なセキュリティは未探索のままである。既存の文献では、PRCが準多項式時間の識別攻撃に対して脆弱である可能性を示唆しているが、現実世界の展開シナリオにおけるこれらの脆弱性を定量化するための厳密な分析は行われていない。このギャップにより、PRCベースのウォーターマーキング・スキームの検知不可能性と堅牢性が、実用的な攻撃者に対して検証されていない状態となっている。

手法

本研究は、LDPC-PRCの最初の具体的な暗号解読を提示し、2つの特定のウォーターマーキング・スキーム、 $\Pi_{LLM}$ （テキスト生成用）および $\Pi_{GIM}$ （画像生成用）に焦点を当てる。著者らは、スキームの検知不可能性と堅牢性を標的とする3つの新しい攻撃を提案し、最先端のモデル（DeepSeekおよびStable Diffusion）から導出された現実的なパラメータ構成下でのそれらの複雑さを分析する。

1. 新しい暗号学的攻撃

著者らは、異なる目的を持つ3つの攻撃を設計した：

攻撃I（部分的な秘密鍵の復元）： この攻撃は、検知不可能性の特性を標的とする。中間一致（Meet-in-the-Middle: MITM）アプローチを用いた情報集合復号（Information Set Decoding: ISD）アルゴリズムを適応させることで、攻撃者は公開鍵から秘密鍵の行ベクトルの一部を復元する。復元されたこれらのベクトルにより、攻撃者はPRC符号化された符号語とランダムなベクトルの間を圧倒的な確率で識別できるようになり、事実上、検知不可能性を打破する。
攻撃II（弱い鍵による識別器）： この攻撃は、鍵生成手順（$KeyGen $）における脆弱性を利用する。著者らは、現在の実装において、公開鍵行列$ G$ が非無視できない確率で同一の行を含むこと（「弱い鍵」）を観察している。攻撃者は、これらの統計的な非一様性を検出することで、複雑な鍵復元を必要とせずに、線形時間でウォーターマーク付きコンテンツとランダムノイズを識別できる。
攻撃III（ノイズオーバーレイ攻撃）： この攻撃は、堅牢性の特性を標的とする。シンドローム復号を通じて元のベルヌーイ・ノイズベクトル $e$ を復元することにより、攻撃者は悪意のあるオーバーレイベクトル $e'$ を構築する。このベクトルは、符号語に加算された際に、総ノイズ重みがデコーダの訂正閾値を超え、復号失敗（ウォーターマークの除去）を引き起こすように設計されている。決定的なことに、この攻撃は、理論的なノイズ境界と、実用的な実装で観察されるより低い具体的なノイズ率との間のギャップを突いている。

2. 具体的な複雑さの分析

著者らは、 $\Pi_{LLM}$ および $\Pi_{GIM}$ に対するこれらの攻撃の計算量とデータ複雑さを分析する。彼らは理論的な境界（定理1–3）を導出し、漸近的な表記のみに頼るのではなく、ビットセキュリティレベル（例： $2^{46}, 2^{60}$ ）を計算することで、これらを具体的なパラメータに対して検証している。

3. 実世界での評価

実用的な脅威を検証するために、著者らはDeepSeek（LLM）およびStable Diffusion（GIM）上で $\Pi_{LLM}$ と $\Pi_{GIM}$ を実装した。彼らは攻撃の成功率とコンテンツ品質への影響を評価した。特筆すべき点として、 $\Pi_{LLM}$ において、検知可能なウォーターマークを実現するには高いトークンエントロピーが必要であり、これがテキストの可読性を著しく低下させ、高品質なテキスト生成には不向きであることを発見した。

主な貢献と結果

1. 検知不可能性の打破

攻撃I： 部分的な秘密鍵の復元が可能であることを示した。 $\Pi_{GIM}$ の場合、セキュリティレベルはすべてのパラメータ選択において46ビット未満である。 $\Pi_{LLM}$ の場合、この攻撃は圧倒的な確率で成功する。
攻撃II： 特定のパラメータ（例： $t=3, 4$ ）において、弱い鍵がほぼ100%の確率で発生することを明らかにした。これにより、多項式時間の識別攻撃が可能となり、これらのレジームにおける検知不可能性を完全に無効化する。

2. 堅牢性の打破

攻撃III： $\Pi_{LLM}$ のセキュリティレベルは、 $n \le 2^{17}$ の条件下でノイズオーバーレイ攻撃に対し75ビットを超えられないことを証明した。 $\Pi_{GIM}$ の場合、低い具体的なノイズ率（ $\eta \ll \rho$ ）のため、具体的なセキュリティレベルは60ビット未満である。
実験的検証： Stable Diffusionにおいて、著者らは摂動境界（ $\delta$ ）に応じて67%から96%のウォーターマーク除去成功率を達成し、堅牢性が容易に損なわれることを示した。

3. $\Pi_{LLM}$ の実用的な限界

DeepSeekを用いた評価により、根本的なトレードオフが明らかになった：LDPC-PRCの誤り訂正境界を満たすためには、LLMは高エントロピー（低信頼度）のトークンを生成しなければならない。これは、テキストが「検知不可能（低エントロピー）」であるか「読みにくい（高エントロピー）」かのいずれかになることを意味する。したがって、著者らは $\Pi_{LLM}$ は高品質なテキストのリアルタイム・ウォーターマーキングには実用的ではないと結論付けている。

4. 提案される防御策

論文では、3つの緩和戦略を提案している：

パラメータの推奨事項： コード長 $n$ と行重み $t$ を増やすことで、攻撃の複雑さを高めることができる。しかし、128ビットのセキュリティを実現するには $n > 2^{24}$ が必要であり、これは現在の最先端LLMの最大出力長（ $2^{15}$ ）を大幅に超えている。
改訂された鍵生成： 弱い鍵の生成確率を排除するために、ガウス消去法を用いた修正された $KeyGen$ アルゴックリズム（Algorithm 2）を提案している。これは攻撃IIの緩和につながる。
実装の調整： GIMに対しては、追加されるノイズベクトルの重みを増やすことで、理論的なノイズ率と具体的なノイズ率の間のギャップを埋め、攻撃IIIの複雑さを高めることが示唆されている。

重要性と主張

本論文は、漸近理論と実用的な展開の間のギャップを埋める、PRCの最初の体系的なセキュリティ評価を提供することを主張している。著者らは以下の通り断言している：

セキュリティ保証の毀損： LDPC-PRCの主張されるセキュリティは、すべての実用的に実行可能なレジームにおいて不十分である。攻撃は、128ビットよりも大幅に低いコストで、圧倒的な確率でウォーターマークを検知できる。
LLMにおける実用的な不可能： 大規模生成モデルの固有の制約（特に出力長とトークンエントロピー）により、LDPC-PRCによるLLMウォーターマーキングでの128ビットセキュリティの達成は、現在実用的ではない。
厳密な評価の必要性： 本研究は、特定の実装の詳細（鍵生成のヒューリスティックやノイズ率など）を考慮した場合、理論的な困難性の仮定（LPN/植え付けられたXOR）が自動的には具体的なセキュリティに変換されないことを浮き彫りにしている。

著者らは、画像ウォーターマーキングにおけるPRCは依然として許容可能な品質を伴う実用的なインスタンス化が可能である可能性があるものの、現在のLLMにおけるPRCは、広範な展開の前にパラメータと実装戦略の重大な再評価が必要であると結論付けている。