💻 computer science

Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes

Diese Arbeit präsentiert die erste Kryptanalyse von auf LDPC basierenden Pseudozufalls-Fehlerkorrekturcodes (PRCs) und zeigt durch neuartige Angriffe und reale Experimente auf, dass deren beanspruchte Sicherheitsgarantien in praktischen Anwendungen generativer Modell-Wasserzeichen grundlegend untergraben werden, während sie gleichzeitig spezifische Abwehrmaßnahmen vorschlägt und deren inhärente Sicherheitsgrenzen klärt.

Ursprüngliche Autoren: Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

Veröffentlicht 2026-06-16

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, Xiaoyun Wang

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Eine fehlerhafte unsichtbare Tinte

Stellen Sie sich eine neue Art von „unsichtbarer Tinte“ vor, die für Künstliche Intelligenz (KI) entwickelt wurde. Diese Tinte soll dazu dienen, ein geheimes, unlöschbares Merkmal auf KI-generierten Texten und Bildern zu stempeln (wie ein Wasserzeichen). Das Ziel ist es, zu beweisen, dass ein Stück Inhalt von einer bestimmten KI erstellt wurde, ohne dass jemand das Zeichen sehen oder wegwaschen kann.

Diese „unsichtbare Tinte“ wird PRC (Pseudorandom Error-Correcting Codes) genannt. Die Schöpfer behaupteten, sie sei mathematisch unknackbar.

Ein Team von Forschern der Tsinghua-Universität und der Shandong-Universität entschied sich jedoch, die Rolle von „Sicherheitstestern“ zu übernehmen. Sie versuchten, diese Tinte zu knacken. Ihr Fazit? Die Tinte leckt. Sie fanden drei verschiedene Wege, um entweder das unsichtbare Zeichen zu sehen oder es wegzuwaschen, was beweist, dass die aktuelle Version dieser Technologie nicht so sicher ist, wie beworben.

Die drei Wege, wie sie die Tinte knackten

Die Forscher konzentrierten sich auf das spezifische Rezept zur Herstellung dieser Tinte, genannt LDPC-PRC. Sie fanden drei deutliche „Schlupflöcher“ im Rezept:

1. Der „Teilschlüssel“-Raubzug (Attack-I)

Die Analogie: Stellen Sie sich vor, der geheime Schlüssel zur unsichtbaren Tinte ist ein riesiges, komplexes Kombinationsschloss mit tausenden von Stiften. Der öffentliche Schlüssel ist ein Hinweis auf das Schloss. Die Forscher fanden einen Weg, nur ein paar der Stifte zu knacken (einen Teil des geheimen Schlüssels zurückzugewinnen).
Was es bedeutet: Selbst wenn man nicht den ganzen Schlüssel hat, reicht es aus, ein paar Teile zu besitzen, um den Unterschied zwischen einem „wasserzeichenbehafteten“ Bild/Text und einem normalen zu erkennen. Es ist, als könnte man feststellen, ob ein Haus verschlossen ist, indem man sieht, dass genau ein bestimmtes Fenster einen Spalt breit offen steht.
Das Ergebnis: Sie konnten das Wasserzeichen mit nahezu perfekter Genauigkeit und einem relativ geringen Rechenaufwand erkennen.

2. Der „Doppelseiten“-Fehler (Attack-II)

Die Analogie: Stellen Sie sich vor, das Rezept für das Schloss beinhaltet das Mischen eines Kartendecks, um ein einzigartiges Muster zu erzeugen. Die Forscher bemerkten, dass die Mischmaschine defekt war. Manchmal druckte sie versehentlich exakt dasselbe Kartenmuster zweimal in das Deck.
Was es bedeutet: Da das „Mischen“ (die Schlüsselgenerierung) nicht zufällig genug war, waren einige der „Schlösser“ (Schlüssel) schwach. Wenn ein Angreifer eines dieser schwachen Schlösser findet, kann er das Wasserzeichen sofort entdecken.
Das Ergebnis: In vielen der vom Erfinderteam vorgeschlagenen Einstellungen treten diese „schwachen Schlösser“ fast zu 100 % auf. Es ist, als würde man versuchen, ein Geheimnis in einem Buch zu verstecken, in dem der Autor versehentlich auf jeder Seite denselben Satz geschrieben hat.

3. Die „Rausch-Überlagerung“ (Attack-III)

Die Analogie: Die unsichtbare Tinte ist darauf ausgelegt, ein wenig Regen (Rauschen) zu überstehen. Wenn man etwas Wasser auf das Papier sprüht, bleibt die Tinte sichtbar. Die Forscher erkannten, dass man eine spezielle Art von Wasser sprühen kann, die die Lesbarkeit der Tinte aufhebt, obwohl die Menge an Wasser für das bloße Auge normal aussieht.
Was es bedeutet: Sie fanden einen Weg, eine winzige, berechnete Menge an „Statik“ oder „Rauschen“ zum Text oder Bild hinzuzufügen. Dieses Rauschen ruiniert weder das Bild noch die Geschichte, aber es verwirrt den Decoder so sehr, dass er glaubt, das Wasserzeichen sei nicht vorhanden.
Das Ergebnis: Sie konnten das Wasserzeichen vollständig entfernen, ohne dass das Bild verschwommen oder der Text unleserlich wurde.

Der Praxistest: Funktioniert es bei echter KI?

Die Forscher haben dies nicht nur theoretisch auf dem Papier gemacht, sondern an echten KI-Modellen getestet:

Für Text (LLMs): Sie testeten die Wasserzeichenung von Texten eines Modells namens DeepSeek. Dabei stellten sie ein großes Problem fest: Um das Wasserzeichen erkennbar zu machen, musste die KI auf eine Weise schreiben, die sehr zufällig und von geringer Qualität war (wie ein Roboter, der halluziniert). Wenn die KI guten, natürlichen Text schrieb, verschwand das Wasserzeichen. Wenn das Wasserzeichen vorhanden war, war der Text unlesbar. Urteil: Es ist praktisch unbrauchbar für hochwertigen Text.
Für Bilder (GIMs): Sie testeten es auf Stable Diffusion. Hier funktionierten die Angriffe perfekt. Sie konnten das Wasserzeichen erkennen und mit hoher Erfolgsquote entfernen, was beweist, dass die Sicherheitsversprechen falsch waren.

Die „Fixes“ und warum sie schwierig sind

Die Forscher schlugen drei Wege vor, um diese Lücken zu schließen:

Die Zahlen ändern: Die „Schlösser“ größer und komplexer machen.
Das Mischen korrigieren: Den Code zur Generierung der Schlüssel umschreiben, damit er keine Duplikate erstellt.
Mehr Rauschen hinzufügen: Das System widerstandsfähiger gegen „Regen“ machen, damit der „Rausch-Überlagerungs“-Angriff nicht funktioniert.

Der Haken:
Um das System wirklich sicher zu machen (128-Bit-Sicherheit, was der Goldstandard ist), berechneten die Forscher, dass das „Wasserzeichen“ länger sein müsste als die maximale Menge an Text, die eine aktuelle KI in einem Durchgang schreiben kann.

Analogie: Es ist, als würde man versuchen, einen 100-seitigen Vertrag auf eine Postkarte zu quetschen. Die aktuellen KI-Modelle (wie GPT-4) haben einfach nicht genug „Platz“ (Ausgabelänge), um ein sicheres Wasserzeichen zu halten.

Das Fazit

Dieses Paper ist ein „Stresstest“ für eine neue KI-Wasserzeichen-Technologie.

Die gute Nachricht: Die Forscher haben die Fehler gefunden und Lösungsvorschläge präsentiert.
Die schlechte Nachricht: Die aktuelle Version dieser Technologie ist nicht sicher. Sie kann leicht erkannt oder entfernt werden.
Die Realität: Selbst mit den Korrekturen stößt die Technologie an eine physikalische Grenze: Aktuelle KI-Modelle sind zu kurz, um ein wirklich unknackbares Wasserzeichen zu halten.

Die Autoren kommen zu dem Schluss, dass wir dieser speziellen „unsichtbaren Tinte“ zum Schutz von KI-Inhalten derzeit nicht vertrauen können, ohne dass signifikante Änderungen vorgenommen werden.

Technisches Resümee: Kryptanalyse von LDPC-basierten pseudozufälligen Fehlerkorrekturcodes

Problemstellung

Pseudozufällige Fehlerkorrekturcodes (Pseudorandom Error-Correcting Codes, PRCs), die auf der CRYPTO 2024 vorgestellt wurden, stellen eine neuartige kryptographische Primitive dar, die darauf ausgelegt ist, unentdeckbares Watermarking für Large Generative Models (LLMs) und Generative Image Models (GIMs) zu ermöglichen. Die primäre Instanziierung von PRCs, bekannt als LDPC-PRC, stützt sich auf Low-Density Parity-Check-Codes und beansprucht Sicherheit basierend auf der Härte des Learning Parity with Noise (LPN) und der Planted XOR Probleme.

Trotz starker theoretischer asymptotischer Garantien bleibt die konkrete Sicherheit von LDPC-PRC unter praktischen Parameterkonfigurationen bisher unerforscht. Die bestehende Literatur legt nahe, dass PRCs anfällig für quasi-polynomialzeitliche Distinguisher-Angriffe sein könnten, doch wurde keine rigorose Analyse durchgeführt, um diese Schwachstellen in realen Einsatzszenarien zu quantifizieren. Diese Lücke lässt die Unentdeckbarkeit und Robustheit von PRC-basierten Watermarking-Schemata gegenüber praktischen Adversaries unverifiziert.

Methodik

Diese Arbeit präsentiert die erste konkrete Kryptanalyse von LDPC-PRC mit Fokus auf zwei spezifische Watermarking-Schemata: $\Pi_{LLM}$ (für Textgenerierung) und $\Pi_{GIM}$ (für Bildgenerierung). Die Autoren schlagen drei neuartige Angriffe vor, die auf die Unentdeckbarkeit und Robustheit des Schemas abzielen, und analysieren deren Komplexität unter realistischen Parameterkonfigurationen, die von State-of-the-Art-Modellen (DeepSeek und Stable Diffusion) abgeleitet sind.

1. Neuartige kryptographische Angriffe

Die Autoren entwerfen drei Angriffe mit variierenden Zielen:

Attack-I (Partielle Geheimschlüssel-Rekonstruktion): Dieser Angriff zielt auf die Eigenschaft der Unentdeckbarkeit ab. Durch die Adaption von Information Set Decoding (ISD) Algorithmen unter Verwendung eines Meet-in-the-Middle (MITM) Ansatzes rekonstruiert der Adversary eine Teilmenge der Zeilenvektoren des geheimen Schlüssels aus dem öffentlichen Schlüssel. Diese rekonstruierten Vektoren ermöglichen es dem Adversary, zwischen PRC-kodierten Codewörtern und Zufallsvektoren mit überwältigender Wahrscheinlichkeit zu unterscheiden, was die Unentdeckbarkeit effektiv bricht.
Attack-II (Schwacher-Schlüssel-Distinguisher): Dieser Angriff nutzt eine Schwachstelle im Schlüsselgenerierungsverfahren ($KeyGen$) aus. Die Autoren beobachten, dass in aktuellen Implementierungen die öffentliche Schlüsselmatrix $G$ mit nicht vernachlässigbarer Wahrscheinlichkeit identische Zeilen enthalten kann (ein „schwacher Schlüssel“). Ein Adversary kann diese statistischen Nicht-Uniformitäten detektieren, um wassermarkhaltige Inhalte von zufälligem Rauschen in linearer Zeit zu unterscheiden, wodurch die Notwendigkeit einer komplexen Schlüsselrekonstruktion umgangen wird.
Attack-III (Noise Overlay Attack): Dieser Angriff zielt auf die Robustheitseigenschaft ab. Durch die Rekonstruktion des ursprünglichen Bernoulli-Rauschvektors $e$ mittels Syndrome Decoding konstruiert ein Adversary einen bösartigen Overlay-Vektor $e'$ . Dieser Vektor ist so konzipiert, dass er, wenn er zum Codewort addiert wird, das gesamte Rauschgewicht über den Decoder-Korrektur-Schwellenwert hebt, was zu einem Dekodierungsfehler führt (Entfernung des Watermarks). Entscheidend ist, dass dieser Angriff die Lücke zwischen theoretischen Rauschgrenzen und den in praktischen Implementierungen beobachteten niedrigeren konkreten Rauschraten ausnutzt.

2. Konkrete Komplexitätsanalyse

Die Autoren analysieren die Zeit- und Datenkomplexität dieser Angriffe unter Verwendung spezifischer Parameter für $\Pi_{LLM}$ und $\Pi_{GIM}$ . Sie leiten theoretische Schranken (Theoreme 1–3) ab und validieren diese gegen konkrete Parameter, wobei sie Bit-Sicherheitslevel (z. B. $2^{46}$ , $2^{60}$ ) berechnen, anstatt sich allein auf die asymptotische Notation zu verlassen.

3. Real-World-Evaluierung

Zur Validierung praktischer Bedrohungen haben die Autoren $\Pi_{LLM}$ und $\Pi_{GIM}$ auf DeepSeek (LLM) und Stable Diffusion (GIM) implementiert. Sie evaluierten die Erfolgsraten der Angriffe sowie die Auswirkungen auf die Inhaltsqualität. Bemerkenswerterweise stellten sie fest, dass für $\Pi_{LLM}$ das Erreichen detektierbarer Watermarks eine hohe Token-Entropie erfordert, was die Lesbarkeit des Textes massiv verschlechtert und das Schema für die Generierung hochwertiger Texte unpraktikabel macht.

Zentrale Beiträge und Ergebnisse

1. Brechen der Unentdeckbarkeit

Attack-I: Demonstrierte, dass eine partielle Rekonstruktion des geheimen Schlüssels machbar ist. Für $\Pi_{GIM}$ bleibt das Sicherheitslevel über alle Parameterwahl hinweg unter 46 Bits. Für $\Pi_{LLM}$ gelingt der Angriff mit überwältigender Wahrscheinlichkeit.
Attack-II: Offenbarte, dass schwache Schlüssel mit nahezu 100 % Wahrscheinlichkeit für spezifische Parameter (z. B. $t=3, 4$ ) in beiden LLM- und GIM-Schemata auftreten. Dies ermöglicht polynomialzeitliche Distinguisher-Angriffe, was die Unentdeckbarkeit in diesen Regimen vollständig untergräbt.

2. Brechen der Robustheit

Attack-III: Bewies, dass das Sicherheitslevel von $\Pi_{LLM}$ unter Noise Overlay Attacks für $n \le 2^{17}$ nicht über 75 Bits liegen kann. Für $\Pi_{GIM}$ liegt das konkrete Sicherheitslevel unter 60 Bits aufgrund der niedrigen konkreten Rauschrate ( $\eta \ll \rho$ ).
Experimentelle Validierung: Auf Stable Diffusion erreichten die Autoren Erfolgsraten bei der Entfernung des Watermarks von 67 % bis 96 %, abhängig von der Perturbationsgrenze ( $\delta$ ), was zeigt, dass die Robustheit leicht kompromittiert werden kann.

3. Praktische Limitationen von $\Pi_{LLM}$

Die Evaluierung auf DeepSeek offenbarte einen fundamentalen Trade-off: Um die Fehlerkorrekturbereiche von LDPC-PRC zu erfüllen, muss das LLM hoch-entropische (niedrig-konfidente) Tokens generieren. Dies führt zu Texten, die entweder unentdeckbar (niedrige Entropie) oder unlesbar (hohe Entropie) sind. Folglich kommen die Autoren zu dem Schluss, dass $\Pi_{LLM}$ für das reale Watermarking von hochwertigem Text unpraktikabel ist.

4. Vorgeschlagene Abwehrmechanismen

Das Paper schlägt drei Minderungsstrategien vor:

Parameter-Empfehlungen: Eine Erhöhung der Codelänge $n$ und des Zeilengewichts $t$ kann die Angriffskomplexität erhöhen. Um jedoch eine 128-Bit-Sicherheit zu erreichen, ist ein $n > 2^{24}$ erforderlich, was die maximale Ausgabelänge aktueller State-of-the-Art-LLMs ( $2^{15}$ ) übersteigt.
Revidierte Schlüsselgenerierung: Ein modifizierter $KeyGen$-Algorithmus (Algorithmus 2), der Gauß-Elimination verwendet, wird vorgeschlagen, um die Wahrscheinlichkeit der Erzeugung schwacher Schlüssel zu eliminieren und somit Attack-II zu mildern.
Implementierungsanpassungen: Für GIMs wird vorgeschlagen, das Gewicht des hinzugefügten Rauschvektors zu erhöhen, um die Lücke zwischen theoretischen und konkreten Rauschraten zu schließen und damit die Komplexität von Attack-III zu steigおer.

Signifikanz und Behauptungen

Das Paper behauptet, die erste systematische Sicherheitsbewertung von PRCs zu liefern und die Lücke zwischen asymptotischer Theorie und praktischer Anwendung zu schließen. Die Autoren postulieren:

Sicherheitsgarantien sind untergraben: Die behauptete Sicherheit von LDPC-PRC ist über alle praktisch machbaren Regime hinweg unzureichend. Angriffe können Watermarks mit einer Wahrscheinlichkeit nahe 1 detektieren, zu Kosten, die signifikant unter 128 Bits liegen.
Praktische Unmöglichkeit für LLMs: Aufgrund inhärenter Beschränkungen großer generativer Modelle (speziell der Ausgabelänge und der Token-Entropie) ist das Erreichen einer 128-Bit-Sicherheit für LLM-Watermarking via LD-PRC derzeit unpraktikabel.
Notwendigkeit rigoroser Evaluierung: Die Arbeit unterstreicht, dass theoretische Härteannahmen (LPN/Planted XOR) sich nicht automatisch in konkrete Sicherheit übersetzen, wenn spezifische Implementierungsdetails (wie Key-Generation-Heuristiken und Rauschraten) berücksichtigt werden.

Die Autoren kommen zu dem Schluss, dass während das Image-Watermarking mittels PRC möglicherweise noch praktische Instanziierungen mit akzeptabler Qualität zulässt, der aktuelle Zustand von PRCs für LLMs eine signifikante Neubewertung der Parameter und Implementierungsstrategien erfordert, bevor ein breiter Einsatz erfolgen kann.