🔢 mathematics

LLM-Text Watermarking based on Lagrange Interpolation

Diese Arbeit stellt ein Wasserzeichenverfahren für von LLMs generierte Texte vor, das auf der Lagrange-Interpolation basiert und es ermöglicht, selbst nach starker Redaktion durch einen Angreifer die Autorenidentität durch die Lösung des Maximum-Collinear-Points-Problems wiederherzustellen.

Ursprüngliche Autoren: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

Veröffentlicht 2026-02-27

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

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

🕵️‍♂️ Der unsichtbare Fingerabdruck: Wie man KI-Texte sicher identifiziert

Stell dir vor, du hast einen riesigen, super-intelligenten Roboter (eine KI), der Geschichten, E-Mails oder Nachrichten schreibt. Das Problem: Niemand kann mehr unterscheiden, ob ein Text von einem echten Menschen oder von diesem Roboter stammt. Das ist gefährlich, weil Fake-News oder Plagiate so leicht zu verbreiten sind.

Die Forscher aus diesem Papier haben eine clevere Lösung entwickelt: Sie verstecken einen unsichtbaren Fingerabdruck (ein Wasserzeichen) direkt in den Texten der KI. Aber nicht so, dass man ihn sieht, sondern so, dass er auch dann noch da ist, wenn jemand versucht, den Text zu verändern.

📐 Die Idee: Eine unsichtbare Linie im Chaos

Stell dir vor, du zeichnest auf ein riesiges Blatt Papier (das ist der Text) viele kleine Punkte.

Das Geheimnis: Die Forscher sagen der KI: „Zeichne diese Punkte so, dass sie alle genau auf einer geraden Linie liegen."
Die Verschlüsselung: Diese Linie ist das Wasserzeichen. Sie wird durch zwei Zahlen definiert (wie bei einer einfachen Formel $y = mx + b$). Diese zwei Zahlen sind der „Code", der beweist, wer den Text geschrieben hat.

Wie wird das gemacht?
Die KI wählt beim Schreiben jedes Wortes (Token) normalerweise zufällig. Die Forscher sagen ihr aber: „Wenn du ein bestimmtes Wort wählst, dann ist das wie ein Punkt auf unserer Linie."

Sie verstecken die Koordinaten der Linie ( $x$ und $y$ ) in der Wahl der Wörter.
Es sieht für den Leser immer noch wie ein normaler, fließender Text aus. Niemand merkt, dass hier eine geheime Mathematik-Formel versteckt ist.

🧩 Das Rätsel: Die Nadel im Heuhaufen finden

Jetzt kommt der spannende Teil. Was passiert, wenn ein Bösewicht den Text verändert?

Er löscht Wörter.
Er fügt neue hinzu.
Er tauscht Wörter aus.

Dadurch werden viele der versteckten Punkte im Text „verdorben" oder verschoben. Wenn man den Text später analysiert, sieht man eine Ansammlung von Punkten:

Echte Punkte: Sie liegen immer noch auf der geheimen Linie (das sind die, die nicht verändert wurden).
Falsche Punkte: Sie liegen wild durcheinander (das sind die, die durch Änderungen oder Zufall entstanden sind).

Die Lösung:
Die Forscher nutzen einen cleveren Trick namens Lagrange-Interpolation (ein mathematisches Werkzeug, um aus Punkten eine Linie zu zeichnen).
Stell dir vor, du hast einen Haufen Punkte auf einem Tisch. Deine Aufgabe ist es, die eine gerade Linie zu finden, auf der die meisten Punkte liegen.

Selbst wenn nur noch 30 % der Punkte übrig sind und der Rest ein Chaos ist, findet der Algorithmus immer noch die Linie, auf der die meisten Punkte sitzen.
Sobald die Linie gefunden ist, kann man die zwei geheimen Zahlen (den Code) ablesen und beweisen: „Ja, dieser Text stammt von unserer KI!"

🛡️ Warum ist das so stark?

Die Stärke dieser Methode liegt in ihrer Robustheit:

Klassische Wasserzeichen sind wie ein Siegel auf einem Brief. Wenn jemand das Papier zerreißt oder das Siegel abschneidet, ist der Beweis weg.
Dieses neue Wasserzeichen ist wie eine Schnur, die durch viele Perlen gezogen ist. Wenn jemand 10 Perlen wegnimmt oder 10 neue dazwischenfädeln, ist die Schnur immer noch da. Solange genug Perlen auf der Schnur bleiben, kann man die Form der Schnur (die Linie) wiederherstellen.

🎯 Was haben die Tests gezeigt?

Die Forscher haben das an echten KI-Modellen getestet (wie Llama und Mistral):

Es funktioniert: Sie konnten den Code auch dann noch finden, wenn der Text leicht verändert wurde.
Es ist schnell: Das Finden der Linie dauert nur Bruchteile einer Sekunde.
Es ist sicher: Die Wahrscheinlichkeit, dass ein zufälliger Text fälschlicherweise als KI-Text erkannt wird, ist extrem gering (wie ein Lottogewinn).
Die Qualität bleibt gut: Der Text klingt immer noch natürlich. Die KI schreibt nicht „krummer" oder schlechter.

🌟 Zusammenfassung in einem Satz

Die Forscher haben eine Methode entwickelt, die KI-Texte mit einer unsichtbaren, geraden Linie markiert; selbst wenn jemand versucht, den Text zu zerstückeln, kann man diese Linie wiederfinden und so beweisen, dass die KI ihn geschrieben hat.

Es ist wie ein mathematischer Kompass, der auch dann noch zeigt, wo der Norden ist, selbst wenn der Wald (der Text) teilweise abgeholzt wurde.

1. Problemstellung

Mit dem rapiden Fortschritt von Large Language Models (LLMs) steigt die Notwendigkeit, die Herkunft von KI-generierten Texten nachzuweisen. Dies ist entscheidend zur Bekämpfung von Desinformation, Fake News, Plagiaten und zur Sicherstellung der Rechenschaftspflicht in Bereichen wie Journalismus und Bildung.
Das Hauptproblem besteht darin, eine Methode zu entwickeln, die es ermöglicht, einen Wasserzeichen-Code in den Text einzubetten, der auch dann noch extrahiert werden kann, wenn der Text teilweise von einem Angreifer bearbeitet, redigiert oder manipuliert wurde. Bestehende Methoden sind oft entweder nicht robust genug gegen solche Manipulationen oder erfordern eine Neu-Training des Modells.

2. Methodik

Das vorgeschlagene Verfahren ist ein training-freies, modellagnostisches Wasserzeichen-System, das auf algebraischen Strukturen (endlichen Körpern) und Lagrange-Interpolation basiert.

Kernkonzept: Lagrange-Interpolation über endlichen Körpern

Darstellung des Wasserzeichens: Das Wasserzeichen $W$ wird als Koeffizienten eines Polynoms $f(x)$ über einem endlichen Körper $GF(2^n)$ kodiert. Im einfachsten Fall (Linear) ist $f(x) = a_1x + a_0$ , wobei $W = (a_0 || a_1)$ .
Einbettung (Embedding):
1. Es werden pseudo-zufällige $x$ -Koordinaten generiert (basierend auf einem Hash des vorherigen Tokens und eines geheimen Schlüssels).
2. Die zugehörigen $y$ -Koordinaten werden durch Auswertung des Polynoms $y = f(x)$ berechnet.
3. Die Bits der $y$ -Koordinaten werden in den generierten Text eingebettet, indem die Wahrscheinlichkeitsverteilung (Logits) des LLMs verzerrt wird. Ähnlich wie bei „Green/Red"-Tokens wird die Vokabular-Auswahl basierend auf dem Bitwert (0 oder 1) in zwei Teilmengen aufgeteilt und die Logits der gewünschten Teilmenge erhöht.
Extraktion (Extraction):
1. Aus dem Text werden die $x$ - und $y$ -Koordinaten rekonstruiert. Aufgrund von Rauschen (stochastisches Sampling) oder Angriffen (Einfügen/Löschen von Tokens) enthalten die extrahierten Punkte Fehler.
2. Das Problem wird auf das Maximum Collinear Points (MCP) Problem reduziert: Finde die Gerade, die die maximale Anzahl von Punkten in der 2D-Ebene $GF(2^n) \times GF(2^n)$ verbindet.
3. Sobald die dominierende Gerade identifiziert ist, wird die Lagrange-Interpolation angewendet, um die ursprünglichen Koeffizienten $a_0$ und $a_1$ (das Wasserzeichen) wiederherzustellen.

Robustheit und Bit-Korrektur

Da einzelne Token-Änderungen zu fehlerhaften $y$ -Werten führen können, wird ein Bit-Korrektur-Mechanismus eingeführt. Dieser prüft bei der Extraktion Kandidaten innerhalb eines kleinen Hamming-Abstands (z. B. bis zu 1 Bitfehler pro Block), um die Wahrscheinlichkeit zu erhöhen, dass korrekte Punkte für das MCP-Problem gefunden werden.

3. Wichtige Beiträge

Neuer Ansatz: Einführung eines Wasserzeichens basierend auf der geometrischen Eigenschaft kollinearer Punkte in endlichen Körpern, anstatt nur statistischer Verteilungen.
Robustheit gegen Reduktion: Das System kann das Wasserzeichen wiederherstellen, selbst wenn ein erheblicher Teil der eingebetteten Punkte durch Textbearbeitung verloren geht, solange genügend Punkte auf der ursprünglichen Linie verbleiben, um die MCP-Lösung zu dominieren.
Theoretische Analyse: Bereitstellung einer probabilistischen Analyse (Satz 1), die die Wahrscheinlichkeit zufälliger Kollinearitäten in $GF(2^n)^2$ nach oben begrenzt. Dies liefert Design-Richtlinien für die Größe des endlichen Körpers und die Blocklänge, um False Positives zu minimieren.
Skalierbarkeit: Das Verfahren ist effizient und erfordert keine Modifikation des LLMs während des Trainings. Es kann auf längere Wasserzeichen erweitert werden, indem mehrere Linien oder Polynome höheren Grades verwendet werden.

4. Experimentelle Ergebnisse

Die Autoren haben das Verfahren an zwei Open-Source-LLMs (Llama 2, Mistral) getestet und mit fünf anderen State-of-the-Art-Methoden verglichen.

Match-Rate (Trefferquote): Bei einer Textlänge von ca. 200 Tokens und einem Bias von $\delta=6$ erreichte die Methode bei 16-Bit-Wasserzeichen eine Trefferquote von 98,6 %. Dies ist vergleichbar mit den besten bestehenden Methoden (z. B. Qu et al. mit 98,0 %).
Skalierung: Bei längeren Wasserzeichen (32 Bit) sank die Quote leicht auf 85,9 %, blieb aber hoch.
Effizienz: Die Extraktionszeit beträgt nur einen Bruchteil einer Sekunde auf einem Standard-PC, da der MCP-Algorithmus effizient (z. B. $O(N^2)$ ) lösbar ist. Im Gegensatz dazu skalieren einige andere Methoden exponentiell mit der Wasserzeichenlänge und werden unpraktisch.
Angriffstests:
- Substitution: Das System ist robust gegen Ersetzen von Tokens, da dies nur Rauschen in den Punkten erzeugt, das das MCP-Verfahren toleriert.
- Einfügen/Löschen: Diese Angriffe sind schädlicher, da sie die Synchronisation (Block-Ausrichtung) zerstören. Dennoch zeigt das System eine gewisse Toleranz gegenüber bis zu 10 % Manipulationen, wobei die Wiederherstellungsrate mit der Anzahl der Eingriffe abnimmt.

5. Bedeutung und Fazit

Das Paper stellt einen signifikanten Fortschritt im Bereich der LLM-Wasserzeichen dar, indem es Algebra und Geometrie nutzt, um Robustheit gegen Textmanipulationen zu erreichen.

Praktische Relevanz: Die Methode ist leichtgewichtig, erfordert kein Training und ist schnell in der Extraktion, was sie für den realen Einsatz geeignet macht.
Sicherheit: Die theoretische Analyse bietet Garantien gegen zufällige Kollisionen (False Positives).
Zukunftsausblick: Das Framework ist flexibel erweiterbar auf Polynome höheren Grades (Maximum Co-Polynomial Points Problem), was die Kapazität und potenzielle Robustheit weiter erhöhen könnte.

Zusammenfassend bietet dieser Ansatz einen flexiblen Kompromiss zwischen Effizienz, Sicherheit und Robustheit und eröffnet neue Paradigmen für die Nachverfolgung von KI-generierten Inhalten.