💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

Dieses Paper führt eine neue Konstruktion von pseudozufälligen Codes basierend auf der Permuted-Codes-Vermutung ein, die gleichzeitig subexponentielle Sicherheit, Robustheit gegenüber Worst-Case-Edits auf einem binären Alphabet und Resistenz gegen Angreifer erreicht, die über den Detektionsschlüssel verfügen, wodurch die kritischen Einschränkungen vorangegangener Wasserzeichenverfahren überwunden werden.

Ursprüngliche Autoren: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Veröffentlicht 2026-06-23

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

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

Stellen Sie sich vor, Sie sind ein berühmter Autor, der an einem Roman schreibt. Sie möchten beweisen, dass ein bestimmter Absatz von Ihnen geschrieben wurde und nicht von einem Imitator oder einer KI, aber Sie wollen die Geschichte nicht verändern oder seltsam wirken lassen. Sie brauchen eine Möglichkeit, ein geheimes „Signaturen-Merkmal“ in den Text einzubauen, das nur Sie finden können, selbst wenn jemand versucht, die Wörter zu bearbeiten, zu löschen oder zu vertauschen.

Dieses Papier beschäftigt sich mit dem Aufbau einer viel besseren Version dieses geheimen Signatursystems, einem sogenannten Pseudorandom Code (PRC). Stellen Sie sich einen PRC wie eine magische Verschlüsselungsmaschine vor, die Ihre geheime Nachricht in eine lange Kette aus Kauderwelsch verwandelt. Wenn Sie den Schlüssel haben, können Sie das Kauderwelsch wieder in die ursprüngliche Nachricht zurückverwandeln, selbst wenn jemand daran herumgespielt hat.

Hier ist die Aufschlüsselung der Errungenschaften des Papers unter Verwendung einfacher Analogien:

1. Das Problem: Die alten Signaturen waren zu leicht zu brechen

Zuvor hatten Forscher diese Signatursysteme entwickelt, aber sie hatten drei große Mängel:

Der „Quasipolynomielle“ Fehler: Stellen Sie sich ein Schloss vor, für das ein Computer etwa eine Million Jahre bräuchte, um es zu knacken. Das ist gut, oder? Aber diese alten Schlösser konnten tatsächlich in „quasipolynomieller“ Zeit geknackt werden – denken Sie an ein Schloss, das ein Computer in ein paar Tagen statt in einer Million Jahren knacken kann. Es war nicht sicher genug für die langfristige Nutzung.
Der „Alphabet“-Fehler: Die alten Systeme funktionierten gut, wenn man das gesamte Alphabet ändern konnte (wie das Ersetzen jedes „A“ durch ein „Z“). Aber echter Text (wie Englisch) hat ein kleines, festes Alphabet (26 Buchstaben). Die alten Systeme konnten nicht damit umgehen, nur ein paar Buchstaben zu ändern oder ein Wort zu löschen, ohne dass die Signatur kaputtging.
Der „Schlüssel“-Fehler: Wenn ein Hacker Ihren geheimen Schlüssel kannte, konnte er leicht winzige Änderungen vornehmen, um Ihre Signatur zu entfernen. Die alten Systeme gingen davon aus, dass der Hacker blind geflext war; sie funktionierten nicht, wenn der Hacker eine Brille trug.

2. Die Lösung: Das „Permutierte Puzzle“

Die Autoren entwickelten ein neues System basierend auf einem Konzept, das sie die „Permuted Codes Conjecture“ nennen.

Stellen Sie sich vor, Sie haben ein wunderschönes, komplexes Mosaik (den Code).

Die Kacheln mischen: Sie nehmen das Mosaik und mischen die Positionen der Kacheln zufällig (Index-Permutation).
Die Kacheln bemalen: Sie nehmen einen Pinsel und bemalen die Farbe jeder Kachel zufällig neu (Alphabet-Permutation).
Staub streuen: Sie streuen etwas zufälligen Staub über das Ganze (Rauschen/Noise).

Die Autoren behaupten, dass das Ergebnis nach Durchführung aller drei Schritte exakt wie ein Haufen zufälliger, bedeutungsloser Staub aussieht. Jemandem ohne den Schlüssel ist es unmöglich, den Unterschied zwischen dem „vermischten Mosaik“ und dem „zufälligen Staub“ zu erkennen. Dies macht die Signatur unentdeckbar (sie beeinträchtigt die Qualität des Textes nicht).

3. Die drei großen Erfolge

Das Paper behauptet, alle drei oben genannten Probleme gleichzeitig gelöst zu haben:

Super starke Sicherheit: Sie behaupten, ihr neues Schloss sei so stark, dass selbst ein Supercomputer, der über eine sehr lange Zeit läuft (subexponentielle Zeit), den Unterschied zwischen ihrem vermischten Mosaik und dem zufälligen Staub nicht erkennen könnte.
Robust gegenüber Bearbeitungen (Das „Edit“-Problem): Dies ist der größte Durchbruch. Ihr System kann Bearbeitungen überstehen. Wenn ein Hacker ein Wort löscht, einen Tippfehler einfügt oder einen Satz umstellt, kann das System die Signatur immer noch finden.
- Analogie: Stellen Sie sich eine Nachricht vor, die auf einem langen Papierstreifen geschrieben ist. Wenn jemand einige Wörter herausschneidet, neue einklebt oder die Reihenfolge vertauscht, würde das alte System versagen. Das neue System ist wie ein Puzzle, das auch dann noch gelöst werden kann, wenn die Teile leicht beschädigt oder verschoben sind.
Robust gegenüber dem „schlüsselwissenden“ Hacker: Ihr System funktioniert selbst dann, wenn der Hacker den geheimen Schlüssel kennt.
- Analogie: Normalerweise, wenn ein Dieb die Kombination Ihres Tresors kennt, kann er ihn öffnen und den Inhalt entfernen. Die Autoren haben einen Tresor gebaut, bei dem selbst wenn der Dieb die Kombination kennt, er das versteckte Objekt nicht entfernen kann, ohne den Tresor selbst zu zerstören. Dies ermöglicht es jedem, das Wasserzeichen zu verifizieren, nicht nur einer vertrauenswürdigen Partei, ohne das System zu brechen.

4. Wie sie es geschafft haben (Der „Falt“-Trick)

Um dies für echten Text (der eine geringe „Entropie“ oder Zufälligkeit pro Wort hat) umsetzbar zu machen, verwendeten sie eine spezielle Art von mathematischem Code namens Folded Reed-Solomon Codes.

Analogie: Stellen Sie sich vor, Sie versuchen, eine geheime Nachricht zu senden, aber Sie können nur kurze, abgehackte Datensätze senden. Der alte Weg war, einen Buchstaben nach dem anderen zu senden. Der neue Weg ist es, die Nachricht zu „falten“. Anstatt „A, B, C“ zu senden, senden Sie einen einzigen Block, der „A, B und C“ gleichzeitig repräsentiert. Dies ermöglicht es dem System, mehr Informationen in den Text zu packen, ohne dass der Text hochgradig zufällig oder chaotisch sein muss.

5. Der „Haken“ (Die Annahme)

Die Autoren geben zu, dass sie eine große Annahme treffen. Sie setzen darauf, dass das „permutierte Puzzle“ (das vermischte Mosaik) wirklich ununterscheidbar von zufälligem Staub ist.

Sie haben nicht bewiesen, dass dies mathematisch unmöglich zu brechen ist (niemand hat bisher bewiesen, dass dies für diese spezifische Art von Puzzle der Fall ist).
Sie haben jedoch gezeigt, dass:
1. Es durch eine andere berühmte, gut untersuchte Annahme in der Kryptographie impliziert wird (Permuted Puzzles).
2. Sie haben versucht, es mit vielen verschiedenen Arten von Angriffen zu brechen (wie etwa den Versuch, Muster im Staub zu finden), und sind gescheitert.
3. Sie haben bewiesen, dass das System leicht zu brechen wäre, wenn man auch nur einen der drei Schritte (Mischen, Neu-Bemalen oder Bestäuben) weglassen würde. Dies deutet darauf hin, dass alle drei Schritte notwendig sind und das System robust ist.

Zusammenfassung

Dieses Paper führt eine neue, super-sichere Methode zur Wasserzeichen-Versorgung von KI-generiertem Text ein. Es beansprucht für sich, das erste System zu sein, das:

Fast unmöglich zu entdecken ist (es sieht wie normaler Text aus).
Starke Bearbeitungen übersteht (Tippfehler, Löschungen, Umschreibungen).
Funktioniert, selbst wenn der Angreifer den geheimen Schlüssel kennt.

Dies erreichen sie, indem sie den Text in ein „vermischtes Puzzle“ verwandeln, das auf einer neuen mathematischen Annahme basiert, von der sie argumentieren, dass sie aufgrund umfangreicher Tests und Verbindungen zu anderen etablierten mathematischen Theorien sehr wahrscheinlich wahr ist.

Technisches Resümee: Verbesserte pseudozufällige Codes aus permutierten Rätseln

Problemstellung

Die Zunahme KI-generierter Inhalte macht robuste Wasserzeichenverfahren zur Identifizierung der Provenienz notwendig. Jüngste Arbeiten haben etabliert, dass pseudozufällige Codes (PRCs) äquivalent zu Wasserzeichenverfahren mit starken Robustheits- und Qualitätsgarantien sind. Ein PRC ist ein Geheimschlüssel-Verschlüsselungsverfahren, bei dem die Chiffretexte rechnerisch ununterscheidbar von gleichverteilt sind (was Unentdeckbarkeit/Qualität gewährleistet) und der Entschlüsselungsalgorithmus eine hohe Fehlerrate toleriert (was Robustheit gewährleistet).

Bestehende PRC-Konstruktionen leiden jedoch unter drei kritischen Einschränkungen:

Schwache Sicherheit: Alle bisherigen Konstruktionen sind anfällig für quasipolynomielle Distinguierungsangriffe. Sie beruhen darauf, $(\log n)$ -dünnbesetzte Strukturen zu verbergen, was Brute-Force-Suchangriffe ermöglicht.
Begrenzte Alphabet-Robustheit: Während einige Konstruktionen Editierfehler handhaben können, erfordern sie ein polynomialsicheres Alphabet. Realistischer Text (z. B. von Large Language Models) hat eine niedrige Entropie (ca. 1 Bit pro Wort), was einen PRC erfordert, der robust gegenüber Edits über einem konstanten Alphabet (idealerweise binär) ist.
Schwache Adversarielle Modelle: Vorherige Arbeiten gingen davon aus, dass Angreifer rechnerisch beschränkt sind oder nicht über den Detektionsschlüssel verfügen. Es war unklar, ob PRCs gleichzeitig gegen rechnerisch unbeschränkte Angreifer, die über den Detektionsschlüssel verfügen, robust bleiben können (stark-adaptive Robustheit).

Die zentrale offene Frage war, ob eine einzige Konstruktion gleichzeitig subexponentielle Sicherheit, Editier-Robustheit über ein binäres Alphabet und Robustheit gegen schlüsselerhaltende Angreifer erreichen kann.

Methodik

1. Die Vermutete Permutierte Codes (Permuted Codes Conjecture)

Die Autoren führen eine neue rechnerische Härteannahme ein, die Permuted Codes Conjecture. Diese Vermutung postuliert, dass eine Verteilung von „verschlüsselten“ verrauschten Codewörtern rechnerisch ununterscheidbar von einer Gleichverteilung ist.

Die Verteilung $D_{n,\Sigma,C,\eta,T}$ wird wie folgt generiert:

Ziehe eine zufällige Index-Permutation $\sigma \in S_n$ und Alphabet-Permutationen $\pi_1, \dots, \pi_n \in S_\Sigma$ .
Ziehe $T$ Codewörter $c_1, \dots, c_T$ gleichverteilt aus einem linearen Code $C \subseteq \Sigma^n$ .
Permutiere für jedes Codewort die Indizes via $\sigma$ und die Symbole an jeder Position via $\pi_j$ , was $\hat{c}$ ergibt.
Wende einen Substitutionskanal mit einer Rauschrate $\eta$ auf $\hat{c$ an.

Zentrale Erkenntnis: Die Autoren beweisen, dass diese Vermutung durch die Permuted Puzzles Conjecture (die zuvor für doppelt effiziente Private Information Retrieval verwendet wurde) impliziert wird. Sie liefern statistische Evidenz dafür, dass für konstante Alphabette und Codes mit hoher dualer Distanz eine logarithmische Anzahl von Stichproben statistisch gleichverteilt sind. Darüber hinaus zeigen sie, dass alle drei Komponenten (Index-Permutation, Alphabet-Permutation und Rauschen) notwendig sind; das Weglassen der Alphabet-Permutation (wie in einer „Toy“-Version) macht Reed-Solomon-Codes mittels Low-Degree-Polynomial-Angriffen unterscheidbar.

2. Konstruktion von Edit-robusten PRCs

Um Edit-Robustheit über einem binären Alphabet zu erreichen, konstruieren die Autoren einen PRC basierend auf Folded Reed-Solomon (FRS) Codes.

Kodierung: Der Geheimschlüssel besteht aus den Permutationen und einem One-Time-Pad. Zur Kodierung wird ein zufälliges Codewort aus dem zugrunde liegenden Code permutiert, verrauscht und anschließend wird eine Teilmenge der Symbole ausgewählt. Entscheidend ist, dass jedes ausgewählte Symbol als Binärstring ausgegeben wird, der sowohl den Symbolwert als auch seinen Index enthält.
Dekodierung: Der Decoder erhält einen String, der potenziell durch Edits (Einfügungen/Löschungen) korrumpiert wurde. Er scannt alle Substrings einer spezifischen Länge und versucht, die Edit-Distanz mittels „Brute-Force“ zu überwinden, um potenzielle $(index, symbol)$-Paare zu rekonstruieren. Diese Kandidaten bilden eine Liste für jede Position. Ein List-Recovery-Algorithmus für den zugrunde liegenden Code wird dann auf diese Listen angewendet, um das ursprüngste Codewort wiederherzustellen.
Robustheitsmechanismus: Durch die Einbeziehung der Indizes in die Ausgabe kann der Decoder das korrekte Symbol selbst dann wiederherstellen, wenn die Position durch Einfügungen oder Löschungen verschoben wurde, sofern die Anzahl der Edits begrenzt ist. Die Verwendung von FRS-Codes ermöglicht es dem System, einen konstanten Bruchteil an Edits zu tolerieren, selbst wenn das Alphabet effektiv binär ist (durch die Transformation).

3. Wasserzeichen-Transformation

Unter Verwendung des von Christ und Gunn (CRYPTO '24) etablierten Frameworks transformieren die Autoren ihren PRC in ein Wasserzeichenverfahren für autoregressive Sprachmodelle. Das Verfahren generiert wasserzeichenbasierten Text, indem die Token-Selektion zugunsten der PRC-Codewort-Bits verzerrt wird. Die Robustheit des PRC gegenüber Edits überträgt sich direkt auf die Fähigkeit des Wasserzeichens, adiabatische Textmodifikationen zu überstehen, vorausgesetzt, das Modell verfügt über ausreichende Pro-Token-Entropie.

Zentrale Beiträge und Ergebnisse

1. Neue PRC-Konstruktion mit drei Eigenschaften

Das Paper präsentiert die erste PRC-Konstruktion, die gleichzeitig folgende Eigenschaften erfüllt:

Plausible subexponentielle Sicherheit: Basierend auf der Permuted Codes Conjecture, welche die dünnen Strukturen vermeidet, die anfällig für quasipolynomielle Angriffe sind.
Binäre Alphabet-Edit-Robustheit: Die Konstruktion toleriert eine konstante Rate an Worst-Case-Edits (Einfügungen, Löschungen, Substitutionen) über einem binären Alphabet.
Stark-adaptive Robustheit: Das Schema bleibt robust, selbst gegen Angreifer, die über den geheimen Detektionsschlüssel verfügen und rechnerisch unbeschränkt sind.

2. Theoretische Garantien

Theorem 5.6: Unter der Permuted Codes Conjecture existiert ein binäres Alphabet-PRC, der stark-adaptiv gegenüber einer konstanten Rate von Edits mit subexponentieller Sicherheit ist.
Theorem 5.14: Unter einer Variante der Vermutung für Folded Reed-Solomon-Codes existiert ein unentdeckbares LLM-Wasserzeichen, das robust gegenüber einer konstanten Rate von Edits ( $\tilde{O}(\alpha^7)$ ) ist und nur eine konstante Pro-Token-Entropierate $\alpha$ erfordert. Dies ist das erste Wasserzeichen dieser Art, das sowohl unentdeckbar als auch robust gegenüber Worst-Case-Edits unter realistischen Entropie-Beschränkungen ist.

3. Kryptanalyse und Evidenz

Notwendigkeit der Alphabet-Permutation: Die Autoren beweisen, dass ohne Alphabet-Permutationen Reed-Solomon-Codes effizient von Zufall unterscheidbar sind, selbst mit Index-Permutationen und Rauschen.
Quasipolynomielle Angriffe auf Vorarbeiten: Sie zeigen, dass eine breite Klasse früherer PRC-Konstruktionen (die auf gepflanzten dünnbesetzten Strukturen oder rauschtoleranten Prädikaten basieren) inhärent anfällig für quasipolynomielle Zeitangriffe sind.
Statistische Gleichverteilung: Sie beweisen, dass für konstante Alphabette eine geringe Anzahl permutierter Codewörter statistisch ununterscheidbar von Gleichverteilung ist, was ein Beleg für die Gültigkeit der Vermutung gegen einfache Distinguierer ist.

Signifikanz

Das Paper behauptet, das Spannungsverhältnis zwischen den drei wünschenswerten Eigenschaften von PRCs gelöst zu haben, die zuvor als gegenseitig ausschließend oder unerreichbar galten. Durch die Formalisierung der Permuted Codes Conjecture und die Nutzung von Folded Reed-Solomon-Codes liefern die Autoren eine theoretische Grundlage für Wasserzeichenverfahren, die:

Unentdeckbar sind: Ununterscheidbar vom tatsächlichen Output des Sprachmodells.
Robust sind: In der Lage, adiabatische Edits (Einfügungen/Löschungen) am Text zu überstehen.
Sicher sind: Resilient gegen Angreifer, die über den Detektionsschlüssel verfügen, was eine öffentliche Verifizierung ermöglicht, ohne die Robustheit zu gefährden.

Die Arbeit etabliert, dass das Erreichen dieser Eigenschaften ein Übergehen von dünnen Strukturen und das Akzeptieren der Härte der Unterscheidung zwischen permutierten, verrauschten Codewörtern und Zufallsstrings erfordert. Während die Sicherheit auf einer neuen Vermutung beruht, liefern die Autoren starke Belege für deren Gültigkeit und demonstrieren die Existenz praktischer, robuster Wasserzeichen für KI-generierten Text.