💻 computer science

Improved Pseudorandom Codes from Permuted Puzzles

Dit artikel introduceert een nieuwe constructie van pseudorandom codes gebaseerd op de permuted codes conjecture die gelijktijdig subexponentiële beveiliging, robuustheid tegen worst-case bewerkingen op een binair alfabet en weerstand tegen tegenstanders die over de detectiesleutel beschikken bereikt, waardoor de kritieke beperkingen van eerdere watermerkregelingen worden overwonnen.

Oorspronkelijke auteurs: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Gepubliceerd 2026-06-23

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een beroemde auteur bent die aan een roman schrijft. Je wilt bewijzen dat een specifieke paragraaf door jou is geschreven en niet door een imitator of een AI, maar je wilt de tekst niet veranderen of vreemd laten lijken. Je hebt een manier nodig om een geheim "handtekening" in de tekst te verbergen die alleen jij kunt vinden, zelfs als iemand probeert de woorden te bewerken, te verwijderen of te husselen.

Dit artikel gaat over het bouwen van een veel betere versie van dat geheime handtekeningsysteem, een Pseudorandom Code (PRC). Denk aan een PRC als een magische encryptiemachine die jouw geheime boodschap verandert in een lange reeks onzin. Als je de sleutel hebt, kun je de onzin weer terugveranderen in de boodschap, zelfs als iemand ermee heeft geknoeid.

Hier is de uitsplitsing van de prestaties van het artikel met behulp van eenvoudige analogieën:

1. Het Probleem: De oude handtekeningen waren te makkelijk te breken

Voorheen bouwden onderzoekers deze handtekeningsystemen, maar ze hadden drie grote gebreken:

De "Quasipolynomial" Fout: Stel je een slot voor dat een computer ongeveer een miljoen jaar kost om te kraken. Dat is goed, toch? Maar deze oude sloten konden eigenlijk worden gekraakt in een "quasipolynomiale" tijd—denk aan een slot dat een computer een paar dagen kost in plaats van een miljoen jaar. Het was niet veilig genoeg voor de lange termijn.
De "Alfabet" Fout: De oude systemen werkten goed als je het volledige alfabet kon veranderen (zoals elke 'A' vervangen door een 'Z'). Maar echte tekst (zoals Engels) heeft een klein, vast alfabet (26 letters). De oude systemen konden het niet aan om slechts een paar letters te veranderen of een woord te verwijderen zonder dat de handtekening brak.
De "Sleutel" Fout: Als een hacker jouw geheime sleutel kende, konden ze gemakkelijk kleine wijzigingen aanbrengen om je handtekening te verwijderen. De oude systemen gingen ervan uit dat de hacker een blinddoek droeg; ze werkten niet als de hacker een bril op had.

2. De Oplossing: De "Gepermuteerde Puzzel"

De auteurs creëerden een nieuw systeem gebaseerd op een concept dat ze de "Permuted Codes Conjecture" noemen.

Stel je voor dat je een prachtige, complexe mozaïek hebt (de code).

Hussel de Tegels: Je neemt de mozaïek en husselt willekeurig de posities van de tegels (Index Permutatie).
Schilder de Tegels: Je neemt een penseel en schildert de kleur van elke tegel willekeurig over (Alfabet Permutatie).
Strooi Stof: Je strooit wat willekeurig stof over het geheel (Ruis).

De auteurs beweren dat als je al deze drie stappen uitvoert, het resultaat precies lijkt op een hoop willekeurig, betekenisloos stof. Voor iemand zonder de sleutel is het onmogelijk om het verschil te zien tussen de "gehusselde mozaïek" en "willekeurig stof". Dit maakt de handtekening ondetecteerbaar (het verpest de kwaliteit van de tekst niet).

3. De Drie Grote Winsten

Het artikel beweert alle drie de eerder genoemde problemen tegelijkertijd op te lossen:

Super Sterke Beveiliging: Ze beweren dat hun nieuwe slot zo sterk is dat zelfs een supercomputer die een zeer lange tijd draait (sub-exponentiële tijd) het verschil niet kan zien tussen hun gehusselde mozaïek en willekeurig stof.
Robuust tegen Bewerkingen (Het "Edit" Probleem): Dit is de grootste doorbraak. Hun systeem kan bewerkingen overleven. Als een hacker een woord verwijdert, een typefout toevoegt of een zin rondschuift, kan het systeem de handtekening nog steeds vinden.
- Analogie: Stel je een boodschap voor geschreven op een lange strook papier. Als iemand een paar woorden eruit knipt, er nieuwe bij plakt of de volgorde verandert, zou het oude systeem falen. Het nieuwe systeem is als een puzzel die nog steeds opgelost kan worden, zelfs als de stukjes licht beschadigd of verplaatst zijn.
Robuust tegen de "Sleutel-kennende" Hacker: Hun systeem werkt zelfs als de hacker de geheime sleutel kent.
- Analogie: Normaal gesproken, als een dief jouw kluiscombinatie weet, kan hij de kluis openen en de inhoud verwijderen. De auteurs hebben een kluis gebouwd waar zelfs als de dief de combinatie weet, hij het verborgen item niet kan verwijderen zonder de kluis zelf te vernietigen. Dit stelt iedereen in staat om het watermerk te verifiëren, niet alleen een vertrouwde partij, zonder het systeem te breken.

4. Hoe ze het deden (De "Folded" Truc)

Om dit werkend te krijgen voor echte tekst (die een lage "entropie" of willekeur per woord heeft), gebruikten ze een speciaal type wiskundige code genaamd Folded Reed-Solomon codes.

Analogie: Stel je voor dat je probeert een geheime boodschap te versturen, maar je kunt alleen korte, schokkerige bursts van data versturen. De oude manier was om één letter tegelijk te versturen. De nieuwe manier is om de boodschap te "vouwen". In plaats van "A, B, C" te versturen, verstuur je een enkele blok die "A, B en C" tegelijkertijd vertegenwoordigt. Dit stelt het systeem in staat om meer informatie in de tekst te verpakken zonder dat de tekst zeer willekeurig of chaotisch hoeft te zijn.

5. De "Catch" (De Aanname)

De auteurs geven toe dat ze een grote aanname doen. Ze wedden erop dat de "gepermuteerde puzzel" (de gehusselde mozaïek) werkelijk ononderscheidbaar is van willekeurig stof.

Ze hebben niet bewezen dat dit wiskundig onmogelijk te breken is (niemand heeft nog niet bewezen dat dit voor dit specifieke type puzzel geldt).
Echter, ze hebben aangetoond dat:
1. Het wordt geïmpliceerd door een andere beroemde, goed bestudeerde aanname in de cryptografie (Permuted Puzzles).
2. Ze hebben geprobeerd het te breken met vele verschillende soorten aanvallen (zoals het zoeken naar patronen in het stof) en gefaald.
3. Ze hebben bewezen dat als je ook maar één van de drie stappen weglaat (husselen, overschilderen of stoffen), het systeem gemakkelijk te breken is. Dit suggereert dat alle drie de stappen noodzakelijk zijn en het systeem robuust is.

Samenvatting

Dit artikel introduceert een nieuwe, superveilige manier om AI-gegenereerde tekst te watermerken. Het beweert het eerste systeem te zijn dat:

Bijna onmogelijk te detecteren is (het ziet eruit als normale tekst).
Zware bewerkingen overleeft (typefouten, verwijderingen, herschrijvingen).
Werkt zelfs als de aanvaller de geheime sleutel kent.

Ze bereiken dit door de tekst te veranderen in een "gehusselde puzzel" die rust op een nieuwe wiskundige aanname, die zij naar verluidt zeer waarschijnlijk waar is op basis van uitgebreid testen en connecties met andere gevestigde wiskundige theorieën.

Technische Samenvatting: Verbeterde Pseudorandom Codes uit Gepermuteerde Puzzels

Probleemstelling

De proliferatie van door AI gegenereerde inhoud vereist robuuste watermerk-schema's om herkomst te identificeren. Recent werk heeft vastgesteld dat Pseudorandom Codes (PRC's) equivalent zijn aan watermerk-schema's met sterke garanties voor robuustheid en kwaliteit. Een PRC is een geheim-sleutel encryptie-schema waarbij ciphertexten computationeel ononderscheidbaar zijn van uniform (wat ondetecteerbaarheid/kwaliteit waarborgt) en het decryptie-algoritme een hoog aantal fouten kan tolereren (wat robuustheid waarborgt).

Echter, bestaande PRC-constructies lijden onder drie kritieke beperkingen:

Zwakke Beveiliging: Alle voorgaande constructies zijn kwetsbaar voor quasi-polynomiale onderscheidingsaanvallen. Ze vertrouwen op het verbergen van $(\log n)$ -ijle (sparse) structuren, wat brute-force zoekaanvallen mogelijk maakt.
Beperkte Alfabet-robuustheid: Hoewel sommige constructies edit-fouten kunnen afhandelen, vereisen ze een polynomiaal groot alfabet. Realistische tekst (bijv. van Large Language Models) heeft een lage entropie (ongeveer 1 bit per woord), wat een PRC vereist die robuust is tegen edits over een constant-groot (bij voorkeur binair) alfabet.
Zwakke Adversariële Modellen: Voorgaande werken gaan ervan uit dat tegenstanders computationeel begrensd zijn of de detectiesleutel missen. Het was onduidelijk of PRCs robuust konden blijven tegen computationeel onbegrensde tegenstanders die de detectiesleutel bezitten (sterk-adaptieve robuustheid).

De centrale openstaande vraag was of één enkele constructie tegelijkertijd subexponentiële beveiliging, edit-robuustheid over een binair alfabet en robuustheid tegen sleutel-bezittende tegenstanders kon bereiken.

Methodologie

1. De Permuted Codes Conjecture

De auteurs introduceren een nieuwe computationele hardheidsaanname, de Permuted Codes Conjecture. Deze conjectuur stelt dat een distributie van "gescrambelde" ruisige codewoorden computationeel ononderscheidbaar is van een uniforme distributie.

De distributie $D_{n,\Sigma,C,\eta,T}$ wordt als volgt gegenereerd:

Sample een willekeurige index-permutatie $\sigma \in S_n$ en alfabet-permutaties $\pi_1, \dots, \pi_n \in S_\Sigma$ .
Sample $T$ codewoorden $c_1, \dots, c_T$ uniform uit een lineaire code $C \subseteq \Sigma^n$ .
Permuteer voor elk codewoord de indices via $\sigma$ en de symbolen op elke positie via $\pi_j$ , resulterend in $\hat{c}$ .
Pas een substitutie-kanaal toe met een ruisrate $\eta$ op $\hat{c}$ .

Kerninzicht: De auteurs bewijzen dat deze conjectuur wordt geïmpliceerd door de Permuted Puzzles Conjecture (voorheen gebruikt voor dubbel-efficiënte Private Information Retrieval). Ze leveren statistisch bewijs dat voor constant-grote alfabetten en codes met een hoge duale afstand, een logaritmisch aantal samples statistisch uniform is. Bovendien demonstreren ze dat alle drie de componenten (index-permutatie, alfabet-permutatie en ruis) noodzakelijk zijn; het weglaten van de alfabet-permutatie (zoals in een "toy"-versie) maakt Reed-Solomon codes onderscheidbaar via low-degree polynomial attacks.

2. Constructie van Edit-Robuuste PRCs

Om edit-robuustheid over een binair alfabet te bereiken, construeren de auteurs een PRC gebaseerd op Folded Reed-Solomon (FRS) codes.

Encoding: De geheime sleutel bestaat uit de permutaties en een one-time pad. Om te encoderen, wordt een willekeurig codewoord uit de onderliggende code gepermuteerd, voorzien van ruis, en vervolgens wordt een subset van symbolen geselecteerd. Cruciaal is dat elk geselecteerd symbool wordt uitgegeven als een binaire string die zowel de symboolwaarde als de index bevat.
Decoding: De decoder ontvangt een string die potentieel gecorrumpeerd is door edits (inserties/deleties). De decoder scant alle substrings van een specifieke lengte en probeert de "brute-force" edit-afstand te berekenen om potentiële $(index, symbool)$ paren te herstellen. Deze kandidaten vormen een lijst voor elke positie. Een list-recovery algoritme voor de onderliggende code wordt vervolgens toegepast op deze lijsten om het oorspronkelijke codewoord te herstellen.
Robuustheidsmechanisme: Door indices in de output op te nemen, kan de decoder het correcte symbool herstellen, zelfs als de positie verschoven is door inserties of deleties, mits het aantal edits begrensd is. Het gebruik van FRS-codes maakt het systeem in staat om een constante fractie van edits te tolereren, zelfs wanneer het alfabet effectief binair is (via de transformatie).

3. Watermarking Transformatie

Gebruikmakend van het framework gevestigd door Christ en Gunn (CRYPTO '24), transformeren de auteurs hun PRC naar een watermerk-schema voor autoregressieve taalmodellen. Het schema genereert watermerk-tekst door de token-selectie te biasen richting de PRC-codewoordbits. De robuustheid van de PRC tegen edits vertaalt zich direct naar het vermogen van het watermerk om adiërs-wijzigingen aan de tekst te overleven, mits het model voldoende per-token entropie heeft.

Belangrijkste Bijdragen en Resultaten

1. Nieuwe PRC-constructie met Drie Eigenschappen

Het artikel presenteert de eerste PRC-constructie die gelijktijdig voldoet aan:

Plausibele Subexponentiële Beveiliging: Gebaseerd op de Permuted Codes Conjecture, die de ijle structuren vermijdt die kwasi-polynomiale aanvallen kwetsbaar maken.
Binair Alfabet Edit-Robuustheid: De constructie tolereert een constante rate van worst-case edits (inserties, deleties, substituties) over een binair alfabet.
Sterk-Adaptieve Robuustheid: Het schema blijft robuust, zelfs tegen tegenstanders die de geheime detectiesleutel kennen en computationeel onbegrensd zijn.

2. Theoretische Garanties

Theorem 5.6: Onder de Permuted Codes Conjecture bestaat er een binair-alfabet PRC die sterk-adaptief is aan een constante rate van edits met subexponentiële beveiliging.
Theorem 5.14: Onder een variant van de conjectuur voor Folded Reed-Solomon codes bestaat er een ondetecteerbaar LLM-watermerk dat robuust is tegen een constante rate van edits ( $\tilde{O}(\alpha^7)$ ) waarbij slechts een constante per-token entropie rate $\alpha$ nodig is. Dit is het eerste dergelijke watermerk dat zowel ondetecteerbaar als robuust is tegen worst-case edits onder realistische entropie-beperkingen.

3. Cryptanalyse en Bewijs

Noodzaak van Alfabet-permutatie: De auteurs bewijzen dat zonder alfabet-permutaties, Reed-Solomon codes efficiënt onderscheidbaar zijn van random, zelfs met index-permutaties en ruis.
Quasi-polynomiale Aanvallen op Voorgaand Werk: Ze tonen aan dat een brede klasse van voorgaande PRC-constructies (die vertrouwen op geplante ijle structuren of ruis-tolerante predicaten) inherent kwetsbaar zijn voor quasi-polynomiale-tijd aanvallen.
Statistische Uniformiteit: Ze bewijzen dat voor constant-grote alfabetten een klein aantal gepermuteerde codewoorden statistisch ononderscheidbaar is van uniform, wat bewijs levert voor de geldigheid van de conjectuur tegen eenvoudige distinguishers.

Betekenis

Het artikel beweert de spanning tussen de drie gewenste eigenschappen van PRCs op te lossen die voorheen als wederzijds uitsluitend of onbereikbaar werden beschouwd. Door de Permuted Codes Conjecture te formaliseren en Folded Reed-Solomon codes te benutten, bieden de auteurs een theoretische fundering voor watermerk-schema's die:

Ondetecteerbaar zijn: Ononderscheidbaar van de werkelijke output van het taalmodel.
Robuust zijn: In staat om adiërs-wijzigingen (inserties/deleties) aan de tekst te weerstaan.
Veilig zijn: Veerkrachtig tegen aanvallers die de detectiesleutel bezitten, wat publieke verificatie mogelijk maakt zonder de robuustheid in gevaar te brengen.

Het werk stelt vast dat het bereiken van deze eigenschappen vereist dat men verder kijkt dan ijle structuren en de hardheid omarmt van het onderscheiden van gepermuteerde, ruisige codewoorden van willekeurige strings. Hoewel de beveiliging rust op een nieuwe conjectuur, bieden de auteurs sterk bewijs voor de geldigheid ervan en demonstreren ze dat dit de existentie van praktische, robuuste watermerken voor AI-gegenereerde tekst impliceert.