Technische Samenvatting: Cryptanalyse van LDPC-gebaseerde Pseudorandom Error-Correcting Codes

Probleemstelling

Pseudorandom Error-Correcting Codes (PRC's), geïntroduceerd op CRYPTO 2024, vertegenwoordigen een nieuw cryptografisch primitief dat is ontworpen om ondetecteerbare watermerken voor Large Generative Models (LLM's) en Generative Image Models (GIM's) mogelijk te maken. De primaire instantie van PRC's, bekend als LDPC-PRC, rust op Low-Density Parity-Check codes en claimt veiligheid op basis van de hardheid van de Learning Parity with Noise (LPN) en de planted XOR-problemen.

Ondanks sterke theoretische asymptotische garanties, blijft de concrete veiligheid van LDPC-PRC onder praktische parameterinstellingen onverkend. Bestaande literatuur suggereert dat PRC's kwetsbaar kunnen zijn voor quasipolynomiale tijd onderscheidingsaanvallen, maar er is nog geen rigoureuze analyse uitgevoerd om deze kwetsbaarheden in real-world deployment scenario's te kwantificeren. Dit gat laat de ondetecteerbaarheid en robuustheid van op PRC gebaseerde watermerkregelingen ongeverifieerd tegen praktische tegenstanders.

Methodologie

Dit werk presenteert de eerste concrete cryptanalyse van LDPC-PRC, met een focus op twee specifieke watermerkregelingen: $\Pi_{LLM}$ (voor tekstgeneratie) en $\Pi_{GIM}$ (voor beeldgeneratie). De auteurs stellen drie nieuwe aanvallen voor die gericht zijn op de ondetecteerbaarheid en robuustheid van het schema, waarbij zij de complexiteit analyseren onder realistische parameterconfiguraties afgeleid van state-of-the-art modellen (DeepSeek en Stable Diffusion).

1. Nieuwe Cryptografische Aanvallen

De auteurs ontwerpen drie aanvallen met variërende doelen:

• Attack-I (Partiële Secret Key Recovery): Deze aanval richt zich op de ondetecteerbaarheidseigenschap. Door Information Set Decoding (ISD) algoritmen aan te passen met een Meet-in-the-Middle (MITM) benadering, herstelt de tegenstander een subset van de rijvectoren van de geheime sleutel uit de publieke sleutel. Deze herstelde vectoren stellen de tegenstander in staat om met een overweldigende waarschijnlijkheid onderscheid te maken tussen PRC-gecodeerde codewoorden en willekeurige vectoren, wat de ondetecteerbaarheid effectief doorbreekt.
• Attack-II (Weak Key Distinguisher): Deze aanval exploiteert een kwetsbaarheid in de sleutelgeneratieprocedure ($KeyGen$). De auteurs observeren dat de publieke sleutelmatrix $G$ in huidige implementaties met een niet-verwaarloosbare waarschijnlijkheid identieke rijen kan bevatten (een "weak key"). Een tegenstander kan deze statistische niet-uniformiteiten detecteren om watermerkgecodeerde inhoud van willekeurige ruis te onderscheiden in lineaire tijd, waarbij de noodzaak voor complexe sleutelherstel wordt omzeild.
• Attack-III (Noise Overlay Attack): Deze aanval richt zich op de robuustheidseigenschap. Door de originele Bernoulli-ruisvector $e$ te herstellen via Syndrome Decoding, construeert een tegenstander een kwaadaardige overlay-vector $e'$. Deze vector is zodanig ontworpen dat wanneer deze aan het codewoord wordt toegevoegd, de totale ruisgewicht de decoder-correctiedrempel overschrijdt, wat leidt tot een decoderingsfout (verwijdering van het watermerk). Cruciaal is dat deze aanval het gat tussen theoretische ruisbounds en de lagere concrete ruisrates geobserveerd in praktische implementaties exploiteert.

2. Concrete Complexiteitsanalyse

De auteurs analyseren de tijd- en datacomplexiteit van deze aanvallen met behulp van specifieke parametersets voor $\Pi_{LLM}$ en $\Pi_{GIM}$. Zij leiden theoretische bounds af (Theorema 1–3) en valideren deze tegen concrete parameters, waarbij zij bit-beveiligingsniveaus berekenen (bijv. $2^{46}$, $2^{60}$) in plaats van uitsluitend te vertrouwen op asymptotische notatie.

3. Real-World Evaluatie

Om praktische dreigingen te valideren, hebben de auteurs $\Pi_{LLM}$ en $\Pi_{GIM}$ geïmplementeerd op DeepSeek (LLM) en Stable Diffusion (GIM). Zij evalueerden de succespercentages van de aanvallen en de impact op de inhoudskwaliteit. Opvallend genoeg vonden zij dat voor $\Pi_{LLM}$, het bereiken van detecteerbare watermerken een hoge token-entropie vereist, wat de leesbaarheid van tekst ernstig verslechtert, waardoor het schema onpraktisch is voor hoogwaardige tekstgeneratie.

Belangrijkste Bijdragen en Resultaten

1. Het Breken van Ondetecteerbaarheid

• Attack-I: Demonstreerde dat partiële geheime sleutelherstel haalbaar is. Voor $\Pi_{GIM}$ blijft het beveiligingsniveau onder de 46 bits over alle parameterkeuzes. Voor $\Pi_{LLM}$ slaagt de aanval met een overweldigende waarschijnlijkheid.
• Attack-II: Onthulde dat "weak keys" met bijna 100% waarschijnlijkheid voorkomen voor specifieke parameters (bijv. $t=3, 4$) in zowel LLM- als GIM-schema's. Dit maakt polynomiale-tijd onderscheidingsaanvallen mogelijk, wat de ondetecteerbaarheid in deze regimes volledig ondermijnt.

2. Het Breken van Robuustheid

• Attack-III: Bewezen dat het beveiligingsniveau van $\Pi_{LLM}$ de 75 bits niet kan overschrijden voor $n \le 2^{17}$ onder noise overlay aanvallen. Voor $\Pi_{GIM}$ ligt het concrete beveiligingsniveau onder de 60 bits vanwege de lage concrete ruisrate ($\eta \ll \rho$).
• Experimentele Validatie: Op Stable Diffusion bereikten de auteurs succespercentages voor watermerkverwijdering van 67% tot 96%, afhankelijk van de perturbatiebound ($\delta$), wat aantoont dat robuustheid gemakkelijk gecompromitteerd kan worden.

3. Praktische Beperkingen van $\Pi_{LLM}$

De evaluatie op DeepSeek onthulde een fundamentele trade-off: om aan de foutcorrectiebounds van LDPC-PRC te voldoen, moet de LLM tokens met een hoge entropie (lage betrouwbaarheid) genereren. Dit resulteert in tekst die ofwel ondetecteerbaar is (lage entropie) of onleesbaar is (hoge entropie). Bijgevolg concluderen de auteurs dat $\Pi_{LLM}$ onpraktisch is voor real-world watermarking van hoogwaardige tekst.

4. Voorgestelde Defensies

Het paper stelt drie mitigatiestrategieën voor:

• Parameter Aanbevelingen: Het verhogen van de codelengte $n$ en de rij-gewicht $t$ kan de aanvalcomplexiteit verhogen. Echter, het bereiken van 128-bits beveiliging vereist $n > 2^{24}$, wat de maximale outputlengte van huidige state-of-the-art LLM's ($2^{15}$) overschrijdt.
• Herziene Sleutelgeneratie: Een aangepast $KeyGen$ algoritme (Algoritme 2) dat gebruikmaakt van Gaussische eliminatie wordt voorgesteld om de kans op het genereren van "weak keys" te elimineren, ter mitigatie van Attack-II.
• Implementatie Aanpassingen: Voor GIM's wordt gesuggereerd om het gewicht van de toegevoegde ruisvector te verhogen om het gat tussen theoretische en concrete ruisrates te dichten, waardoor de complexiteit van Attack-III wordt vergroot.

Betekenis en Claims

Het paper claimt de eerste systematische beveiligingsevaluatie van PRC's te bieden, waarmee de kloof tussen asymptotische theorie en praktische inzet wordt overbrugd. De auteurs stellen dat:

1. Beveiligingsgaranties worden ondermijnd: De geclaimde veiligheid van LDPC-PRC is onvoldoende in alle praktisch haalbare regimes. Aanvallen kunnen watermerken detecteren met een overweldigende waarschijnlijkheid tegen kosten die aanzienlijk lager zijn dan 128 bits.
2. Praktische Onmogelijkheid voor LLM's: Vanwege inherente beperkingen van grote generatieve modellen (specifiek outputlengte en token-entropie), is het bereiken van 128-bits beveiliging voor LLM-watermarking via LDPC-PRC momenteel onpraktisch.
3. Noodzaak voor Rigoureuze Evaluatie: Het werk benadrukt dat theoretische hardheidsaannames (LPN/planted XOR) niet automatisch vertalen naar concrete beveiliging wanneer specifieke implementatiedetails (zoals heuristieken voor sleutelgeneratie en ruisrates) in overweging worden genomen.

De auteurs concluderen dat hoewel PRC-gebaseerde beeldwatermarking nog steeds praktische instanties kan toestaan met aanvaardbare kwaliteit, de huidige staat van PRC's voor LLM's een significante herwaardering van parameters en implementatiestrategieën vereist voordat brede inzet mogelijk is.