💻 computer science

Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

Dit paper introduceert het eerste transparante, op codes gebaseerde post-kwantum sanitiseerbare signatuurschema, dat gebruikmaakt van een McEliece-gebaseerde chameleon-hash met een Goppa-code-valstrik om geautoriseerde berichtmodificaties mogelijk te maken terwijl de onveranderlijkheid en onopspoorbaarheid van de originele handtekening worden gewaarborgd.

Oorspronkelijke auteurs: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Gepubliceerd 2026-02-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

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 heel belangrijk, digitaal document hebt ondertekend, zoals een medisch dossier of een juridisch contract. Normaal gesproken is zo'n document "vergrendeld": als je er ook maar één letter in verandert, is de handtekening ongeldig en wordt het document ongeloofwaardig.

Maar wat als je die documenten moet aanpassen? Stel, een arts moet een patiëntennaam uit een medisch dossier halen voor privacy, of een bank moet de vervaldatum van een certificaat updaten. In de oude wereld zou je het hele document opnieuw moeten laten ondertekenen, wat veel tijd kost en de integriteit van het document in gevaar brengt.

Sanitizable Signatures (of "reinigbare handtekeningen") zijn een slimme oplossing hiervoor. Ze staan toe dat een bevoegde persoon (de "sanitiser") specifieke delen van een document mag wijzigen, zonder de handtekening te breken. Het probleem? De huidige technologieën die dit mogelijk maken, zijn gebaseerd op wiskundige problemen die door toekomstige kwantumcomputers binnen no-time kunnen worden opgelost.

Deze paper introduceert een nieuwe, toekomstbestendige manier om dit te doen, gebaseerd op een heel oude en sterke wiskundige techniek: de McEliece-cryptografie.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. De "Magische Sleutel" (De Chameleon Hash)

In de wereld van deze paper gebruiken ze iets dat een Chameleon Hash heet.

De Analogie: Stel je voor dat je een brief in een speciale, onbreekbare koffer doet en deze verzegelt met een handtekening. Normaal is die koffer onopendoorbaar. Maar een Chameleon Hash is als een koffer met een geheime magische sleutel.
Hoe het werkt: Iedereen kan de koffer zien en de handtekening controleren (de "publieke sleutel"). Maar alleen de persoon met de geheime sleutel (de "sanitiser") kan de koffer openen, een stukje van de brief vervangen, en de koffer weer zo dichtdoen dat het er precies hetzelfde uitziet als voorheen. Voor een buitenstaander is het alsof de brief nooit is veranderd.

2. Waarom is dit nu "Post-Quantum"?

Tot nu toe werden deze magische sleutels gemaakt met wiskunde die kwantumcomputers kunnen kraken (zoals het ontbinden in priemfactoren).
De auteurs gebruiken hier een McEliece-systeem.

De Analogie: Stel je voor dat je een enorme doos met duizenden gekleurde knopen hebt. Je moet een specifiek patroon van knopen vinden dat een bepaalde vorm maakt. Voor een gewone computer is dit al heel lastig. Voor een kwantumcomputer is het ook lastig, omdat de wiskunde hier heel anders in elkaar zit dan de oude methoden. Het is als het proberen te vinden van één specifieke druppel water in een oceaan, terwijl je blind bent.
Dit systeem is al 45 jaar oud en heeft nog nooit een kwantumcomputer overleefd. Dat maakt het extreem veilig voor de toekomst.

3. Het Grote Geheim: "Perfecte Transparantie"

Dit is misschien wel het coolste deel van het onderzoek.
Bij eerdere versies van dit idee kon een slimme buitenstaander soms raden: "Hé, dit document is aangepast door de sanitiser, het is niet origineel!" Dat is alsof je ziet dat een schilderij is gerestaureerd; je ziet de nieuwe verf.

De auteurs hebben een slimme truc bedacht om dit te voorkomen:

De Truc: Ze dwingen de persoon die het document tekent (de "signer") om bij het maken van de handtekening een heel specifiek type "willekeurige ruis" te gebruiken.
De Analogie: Stel je voor dat de signer en de sanitiser beiden een doos met rode en blauwe balletjes hebben.
- De signer pakt willekeurig balletjes, maar zorgt ervoor dat hij altijd precies 64 rode balletjes pakt.
- De sanitiser gebruikt zijn magische sleutel om de knopen te veranderen. Door de wiskunde van het McEliece-systeem komt hij er altijd ook uit met precies 64 rode balletjes.
Het Resultaat: Omdat beide partijen exact dezelfde verdeling van balletjes gebruiken, is het voor een buitenstaander onmogelijk om te zien wie het document heeft aangeraakt. Het is alsof je twee identieke kopieën van een schilderij ziet; je kunt niet zeggen welke het origineel is en welke de restauratie. Ze noemen dit "Perfecte Transparantie".

4. Hoe werkt het in de praktijk?

Het team heeft een prototype gebouwd (in Python) om te bewijzen dat dit echt werkt.

Snelheid: Het duurt ongeveer 8 milliseconden om één blok van een document aan te passen. Dat is razendsnel.
Grootte: De sleutels zijn wel wat groot (ongeveer 655 KB), wat vergelijkbaar is met andere moderne beveiligingssystemen. Het is niet klein, maar het is een kleine prijs om je data voor de komende 100 jaar veilig te houden tegen kwantumcomputers.

Samenvattend

Deze paper presenteert de eerste manier om documenten veilig en toekomstbestendig te kunnen aanpassen zonder de handtekening te breken.

Het gebruikt een oude, sterke wiskundige basis (McEliece) die kwantumcomputers niet kunnen kraken.
Het maakt gebruik van een magische sleutel (Patterson decoding) om delen van documenten te vervangen.
Het is perfect onzichtbaar: niemand kan zien of een document is aangepast of origineel is.

Het is een belangrijke stap voor het beveiligen van medische dossiers, juridische contracten en overheidsdocumenten in een wereld waar kwantumcomputers binnen een paar jaar een realiteit worden. Het zorgt ervoor dat we documenten kunnen "reinigen" zonder dat we ooit hoeven te twijfelen aan hun echtheid.

Titel: Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

Auteurs: Shahzad Ahmad, Stefan Rass, en Zahra Seyedi.

1. Het Probleem

Sanitiseerbare handtekeningen (Sanitizable Signatures) zijn cryptografische primitieven die het mogelijk maken om een gesigneerd document door een gemachtigde "sanitiseerder" te laten aanpassen zonder de geldigheid van de handtekening te verbreken. Dit is essentieel voor toepassingen zoals het anonimiseren van medische dossiers of het updaten van vervaldatums in X.509-certificaten.

De huidige uitdagingen zijn:

Quantum-bedreiging: Bestaande schema's vertrouwen op cryptografische primitieven zoals RSA, Discrete Logarithmen of Pairings. Deze zijn kwetsbaar voor Shor's algoritme op een kwantumcomputer.
Gebrek aan code-based oplossingen: Hoewel er recent lattice-gebaseerde post-quantum oplossingen zijn ontwikkeld, bestond er tot nu toe geen post-quantum sanitiseerbaar handtekeningsschema gebaseerd op code-cryptografie (zoals McEliece).
Transparantie: Een cruciale privacy-eis is dat een waarnemer niet kan onderscheiden of een handtekening door de oorspronkelijke ondertekenaar is gemaakt of door de sanitiseerder. Bestaande post-quantum schema's bieden vaak slechts een zwakke vorm van transparantie.

2. Methodologie

De auteurs introduceren het eerste transparante, post-quantum sanitiseerbare handtekeningsschema dat gebaseerd is op de McEliece-cryptosysteem en Goppa-codes.

Kerncomponenten:

McEliece-gebaseerde Chameleon Hash:
- De kern van het schema is een chameleon hash-functie: $H_{pk}(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$ .
- Random Oracle (ROM): Om een triviaal aanvalspunt (lineaire botsing) te voorkomen, wordt het bericht $m$ eerst verwerkt door een random oracle $G$ (geïmplementeerd als SHA-3). Zonder $G$ zou een aanvaller eenvoudig een botsing kunnen vinden door $r$ te manipuleren.
- Valstrik (Trapdoor): De sanitiseerder bezit de geheime sleutel van een Goppa-code (de trapdoor). Hiermee kan hij via Patterson-decodering een nieuwe randomizer $r'$ vinden voor een gewijzigd bericht $m'$ , zodat de hash-waarde identiek blijft. Dit is een gecontroleerde botsing.
Handtekeningsschema:
- Het schema gebruikt twee onafhankelijke McEliece-chameleon hashes: één voor onwijzigbare blokken ( $H_{non}$ ) en één voor aanpasbare blokken ( $H_{san}$ ).
- De berichtenblokken worden in een hash-keten verwerkt.
- De uiteindelijke digest wordt ondertekend met een bestaand post-quantum handtekeningsschema (gebaseerd op Dilithium2).
Transparantie-mechanisme:
- Om perfecte transparantie te bereiken, beperken de auteurs de signer om randomizers te kiezen met een exacte Hamming-gewicht $t$ .
- Omdat Patterson-decodering ook altijd een foutvector met exact gewicht $t$ teruggeeft, zijn de verdelingen van de randomizers van de signer en de sanitiseerder statistisch identiek.

3. Belangrijkste Bijdragen

Eerste Code-based Post-Quantum Schema: Het is het eerste post-quantum sanitiseerbare handtekeningsschema dat gebruikmaakt van syndrome decoding (McEliece) in plaats van lattice-problemen.
ROM-veilige Chameleon Hash: Een nieuwe constructie die botsingsbestendigheid garandeert in het Random Oracle Model, gebaseerd op de hardheid van het Syndrome Decoding-probleem.
Perfecte Transparantie: Door het opleggen van een gewichtsbeperking ($wt(r)=t$) op de randomizers, bereiken de auteurs een statistische afstand van $\delta = 0$ . Dit betekent dat een gesignaleerde handtekening en een gesaniteerde handtekening ononderscheidbaar zijn, ongeacht het aantal gewijzigde blokken.
Formele Bewijzen: De auteurs leveren formele bewijzen voor existentiële onvervalsbaarheid (EUF-CMA) en onwrikbaarheid (Immutability) in het Random Oracle Model, gebaseerd op de hardheid van Syndrome Decoding.
Implementatie en Benchmarking: Een Python-prototype is ontwikkeld en getest met parameters die overeenkomen met NIST Category 1 (Classic-McEliece: $n=3488, k=2720, t=64$ ).

4. Resultaten en Prestaties

Veiligheid: Het schema is veilig tegen kwantum-aanvallen. De hardheid rust op het Syndrome Decoding-probleem, een probleem dat al 45 jaar als moeilijk wordt beschouwd (in tegenstelling tot lattice-problemen die ~15 jaar oud zijn).
Transparantie:
- Zonder beperking: $\delta \approx 0.0187$ (statistische afstand).
- Met gewichtsbeperking ($wt=t $):$ \delta = 0$ (perfecte transparantie).
Grootte:
- Publieke sleutel: ~~655,3 KB (voor NIST Cat. 1). Dit is kleiner dan het vergelijkbare lattice-gebaseerde schema (~~850 KB).
- Handtekening: ~6,75 KB voor een document met 10 blokken.
Snelheid:
- De theoretische tijd voor Patterson-decodering (voor het vinden van een botsing) is ongeveer 8 ms per gewijzigd blok voor de veilige parameters.
- De implementatie toont lineaire schaalbaarheid met het aantal blokken.

5. Betekenis en Toepassingen

Dit werk vult een cruciale lacune in de post-quantum cryptografie op door een robuust alternatief voor lattice-gebaseerde oplossingen te bieden.

Toepassingsgebieden:
- Medische dossiers: Anonimiseren van patiëntgegevens terwijl de arts-handtekening geldig blijft.
- Certificaten: Updaten van vervaldatums in X.509-certificaten zonder de hele keten opnieuw te hoeven ondertekenen.
- Supply Chain: Verbergen van gevoelige prijsinformatie in goedgekeurde documenten.
Voordeel: Het schema biedt een "conservatievere" veiligheidsbasis (McEliece) en perfecte transparantie, wat essentieel is voor privacy in langdurige archiveringssystemen.
Beperkingen:
- De publieke sleutel is nog steeds groot vergeleken met klassieke RSA-sleutels (hoewel kleiner dan lattice-opties).
- De veiligheid van de chameleon hash rust op het Random Oracle Model (ROM); een bewijs in het standaardmodel ontbreekt nog.
- Er is geen "exposure-freeness" (herhaald sanitiseren kan theoretisch informatie over de trapdoor lekken) en het beleid (welke blokken aanpasbaar zijn) is niet verborgen.

Conclusie: De auteurs hebben een baanbrekend post-quantum schema gepresenteerd dat code-cryptografie succesvol toepast op sanitiseerbare handtekeningen, met een sterke focus op privacy (perfecte transparantie) en theoretische robuustheid.