💻 computer science

Withdrawability in Fiat-Shamir with aborts constructions

Dit artikel breidt het concept van withdrawable signatures uit naar het Fiat-Shamir with aborts-paradigma door een abstracte constructie met beveiligingsbewijzen voor te stellen en een concrete instantie te bieden gebaseerd op een no-hint Dilithium-stijl schema, terwijl wordt opgemerkt dat er kleine aanpassingen vereist zijn voor de productie-ML-DSA met hints.

Oorspronkelijke auteurs: Ramses Fernandez-Valencia

Gepubliceerd 2026-07-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ramses Fernandez-Valencia

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 speciale, onverwoestbare digitale stempel hebt. Zodra je deze stempel op een document zet, is hij meestal permanent. Je kunt hem niet meer terugnemen en niemand kan beweren dat je hem niet hebt gezet. Dit is hoe de meeste digitale handtekeningen vandaag de dag werken.

Maar wat als je een "zachte" handtekening wilde? Eén die je kunt terugnemen als je van gedachten verandert, voordat iemand anders het ziet, zonder je vermogen om andere dingen te ondertekenen te vernietigen?

Dit artikel introduceert een nieuw soort digitale handtekening genaamd een "Withdrawable Signature" (Intrekbare Handtekening). Het is ontworpen voor een toekomst waarin krachtige kwantumcomputers de huidige beveiliging kunnen breken, en maakt daarom gebruik van "lattice-gebaseerde" wiskunde (denk aan een complexe, meerdimensionale doolhof) in plaats van de oude wiskunde die kwantumcomputers gemakkelijk kunnen oplossen.

Hier is hoe het artikel dit uitlegt, met behulp van eenvoudige analogieën:

1. Het Probleem: De "Permanente Stempel"

Normaal gesproken, wanneer je een digitaal contract ondertekent, is dat als het zetten van een stempel op een document met natte inkt die direct opdroogt. Als de inkt eenmaal droog is, staat het voor altijd vast.

Het probleem: Soms moet je van gedachten veranderen. Misschien heb je een smart contract op een blockchain ondertekend, maar is de deal afgezwakt. Of misschien heb je een stem uitgebracht in een digitale verkiezing, maar besefte je dat je een fout had gemaakt voordat de stemmen werden geteld.
Het doel: Je hebt een manier nodig om te zeggen: "Ik heb dit ondertekend, maar ik neem het terug," zonder je geheim wachtwoord (private key) te onthullen of je andere handtekeningen te verstoren.

2. De Oplossing: De "Magische Dubbele Envelop"

De auteurs hebben een systeem gecreëerd waarbij een handtekening begint als een geheime, intrekbare notitie en later kan worden omgezet in een publieke, bevestigde stempel.

Denk er als volgt over na:

Stap 1: De Withdrawable Signature (De Geheime Notitie)
Stel je voor dat je een briefje schrijft en dit in een speciale, vergrendelde doos plaatst. Je geeft deze doos aan een specifiek persoon (de "designated verifier" of aangewezen controleur).
- Alleen die specifieke persoon heeft de sleutel om de doos te openen en de notitie te lezen.
- De Magische Truc: Voor iedereen anders (zelfs voor een spion die je in de gaten houdt) lijkt de doos op willekeurige ruis. Ze kunnen niet zien of jij de notitie in de doos hebt geplaatst, of dat de ontvanger de notitie zelf heeft geschreven en in de doos heeft geplaatst. Het is een perfecte "hij zei, zij zei"-situatie. Dit wordt Ambiguïteit genoemd.
- Vanwege deze ambiguïteit kun je zeggen: "Ik heb dat nooit ondertekend," en de ontvanger kan niet bewijzen dat je dat wel deed, tenzij je besluit het te bevestigen.
Stap 2: De Bevestiging (De Publieke Stempel)
Als je besluit dat je de handtekening wel permanent wilt maken, voer je een "Bevestigingsstap" uit.
- Je haalt de geheime notitie uit de doos en gebruikt je geheime sleutel om een standaard, publieke handtekening te genereren die bewijst: "Ja, ik heb dit echt geschreven."
- Nu kan iedereen het zien en kan niemand ontkennen dat je het gedaan hebt.

3. De "Kwantum-Proof" Doolhof (Fiat-Shamir met Aborts)

Het artikel boupt dit systeem op een specifiek type wiskunde genaamd Fiat-Shamir met Aborts.

De Analogie: Stel je voor dat je probeert een enorme, complexe doolhof op te lossen om te bewijzen dat je de weg weet.
Het "Abort" Deel: Soms sla je per ongeluk een verkeerde afslag in waardoor je onbedoeld een geheim over hoe je de doolhof hebt opgelost, prijsgeeft. Als dat gebeurt, zeg je simpelweg: "Abort! Ik maakte een fout," en begin je gewoon opnieuw vanaf het begin. Je blijft proberen totdat je een pad vindt dat bewijst dat je de weg weet zonder geheimen te lekken.
Deze "probeer en herhaal"-methode is wat de handtekening veilig maakt tegen kwantumcomputers.

4. Hoe ze het gebouwd hebben (De "No-Hint" Dilithium)

De auteurs hebben een beroemd bestaand kwantum-proof handtekeningschema genaamd Dilithium (dat lijkt op een standaard, hoogbeveiligde stempel) genomen en dit aangepast.

Ze hebben een klein "hint"-kenmerk verwijderd dat Dilithium normaal gesproken gebruikt om het sneller te maken.
Waarom? Het verwijderen van de hint maakt de wiskunde "perfect". Het zorgt ervoor dat de geheime notitie werkelijk ononderscheidbaar is van een valse notitie, zelfs voor een supercomputer.
Ze hebben deze aangepaste handtekening gewikkeld in een encryptielaag. Dit is als het plaatsen van de "Magische Dubbele Envelop" binnen een beveiligde koeriersdienst die alleen door de beoogde ontvanger en de verzender geopend kan worden.

5. Waarom dit ertoe doet (Volgens het artikel)

Het artikel beweert dat deze constructie twee hoofdzaken bereikt:

Onvervalsbaarheid: Zelfs als een hacker de geheime sleutel van de ontvanger steelt, kunnen ze nog steeds geen handtekening vervalsen die lijkt op de originele handtekening van de ondertekenaar. Alleen de oorspronkelijke ondertekenaar kan de "withdrawable" notitie omzetten in een "bevestigde" stempel.
Intrekbaarheid: Zolang je de handtekening niet hebt bevestigd, kan niemand (zelfs de ontvanger niet) bewijzen wie de notitie heeft geschreven. Het is een perfecte gelijkstand.

Samenvatting

Het artikel presenteert een nieuwe manier om digitale documenten te ondertekenen die het mogelijk maakt om je handtekening in te trekken voordat deze permanent wordt. Het gebruikt een "geheime notitie" die alleen een specifieke persoon kan lezen, die later kan worden omgezet in een "publieke stempel". Dit systeem is gebouwd op "kwantum-proof" wiskunde (lattices) en gebruikt een "probeer-en-herhaal"-methode om ervoor te zorgen dat er geen geheimen lekken.

Cruciaal is dat het artikel zich volledig richt op de wiskundige constructie en beveiligingsbewijzen. Het vermeldt dat dit nuttig zou kunnen zijn voor blockchain- of stemmenstelsels, maar het beweert niet dat het al een werkende blockchain of stem-app heeft gebouwd; het biedt enkel de veilige "motor" die dergelijke zaken in de toekomst zou kunnen aandrijven.

Technische Samenvatting: Intrekbaarheid in Fiat–Shamir met Abort-constructies

Probleemstelling
Digitale handtekeningen bieden traditioneel permanentie; eenmaal gegenereerd, kan een handtekening niet worden ingetrokken zonder de privésleutel van de ondertekenaar te compromitteren of andere handtekeningen ongeldig te maken. Deze beperking vormt uitdagingen in dynamische omgevingen zoals blockchain smart contracts, gedecentraliseerd stemmen en escrow-diensten, waar deelnemers hun verbintenissen kunnen intrekken op basis van veranderende omstandigheden. Liu, Baek en Susilo [LBS23] introduceerden "intrekbare handtekeningen" (withdrawable signatures), een primitief dat een ondertekenaar in staat stelt een handtekening te genereren die alleen verifieerbaar is door een aangewezen verifieerder, welke later kan worden getransformeerd in een publiekelijk verifieerbare handtekening. Hun constructie rust echter op klassieke aannames (Discrete Logaritme, Diffie-Hellman) die kwetsbaar zijn voor quantum-aanvallen.

De uitdaging die dit artikel aanpakt, is het uitbreiden van het concept van intrekbare handtekeningen naar de post-quantum setting, specifiek binnen het Fiat–Shamir met aborts paradigma. Dit paradigma vormt de basis voor leidende post-quantum handtekeningschema's zoals Dilithium (ML-DSA) en HAETAE. Er bestaat een specifieke structurele hindernis: de oorspronkelijke Liu–Baek–Susilo constructie vertrouwt op een "gratis" Diffie-Hellman gedeeld geheim om ambiguïteit tussen ondertekenaar/verifieerder en designatie gelijktijdig te bereiken. De lattice-gebaseerde cryptografie mist een goedkope, efficiënte analogon voor dit gedeelde geheim, wat een nieuwe architecturale aanpak noodzakelijk maakt.

Methodologie
Het artikel stelt een algemene abstracte constructie voor voor intrekbare handtekeningen gebaseerd op het Fiat–Shamir met aborts paradigma, gevolgd door een concrete instantiatie.

Abstracte Constructie:
De auteurs definiëren een framework bestaande uit vijf algoritmen: KeyGen, WSign (intrekbaar tekenen), WSVerify (intrekbare verificatie), Confirm, en CVerify.
- Kernmechanisme: Het schema maakt gebruik van een tweepartijdig Fiat–Shamir met aborts OR-bewijs. De intrekbare handtekening bestaat uit twee takken: één gegenereerd door de ondertekenaar (met behulp van hun geheime sleutel) en één gesimuleerd door de ondertekenaar om de tak van de verifieerder na te bootsen.
- Ambiguïteit: Omdat zowel de ondertekenaar als de aangewezen verifieerder een geldige tak kunnen genereren (de ondertekenaar door de verifieerder te simuleren, en de verifieerder door de ondertekenaar te simuleren), is de oorsprong van de handtekening ononderscheidbaar voor derde partijen.
- Bevestiging (Confirmation): Om de handtekening publiekelijk verifieerbaar te maken, voert de ondertekenaar het Confirm algoritme uit, dat een standaard, gewone handtekening genereert over de boodschap, de publieke sleutelset en de intrekbare handtekening zelf. Dit bindt de intrekbare handtekening aan de identiteit van de ondertekenaar zonder dat de gedeelde willekeur opnieuw afgeleid hoeft te worden (wat onhaalbaar is in lattice-gebaseerde FS-with-aborts vanwege rejection sampling).
Strong Designated-Verifier (SDVS) Variant:
Om ervoor te zorgen dat de intrekbare handtekening niet publiekelijk verifieerbaar is (overeenkomstigend met het Liu–Baek–Susilo model), versleutelen de auteurs de publieke kern van de handtekening met behulp van een Public Key Encryption (PKE) schema (specifiek de CPA-veilige module-LWE encryptie die ten grondslag ligt aan ML-KEM/Kyber).
- De handtekening wordt versleuteld naar zowel de publieke sleutel van de aangewezen verifieerder als de publieke sleutel van de ondertekenaar. Dit stelt de verifieerder in staat te ontsleutelen en te verifiëren, en stelt de ondertekenaar in staat te ontsleutelen en de Confirm operatie stateless uit te voeren.
- Deze aanpak vervangt het Diffie-Hellman gedeelde geheim door expliciete encryptie, in de erkenning dat lattice-gebaseerde Non-Interactive Key Exchange (NIKE) momenteel te inefficiënt is voor dit doel.
Concrete Instantiatie:
Het abstracte framework wordt geïnstantieerd met behulp van een no-hint, full- $t$ Dilithium-stijl constructie.
- De auteurs gebruiken een variant van Dilithium die geen "hints" gebruikt (de $t_1$ / $t_0$ splitsing), waardoor de simulator voor het zero-knowledge bewijs perfect is ( $\varepsilon_{zk} = 0$ ).
- Deze keuze vereenvoudigt de beveiligingsbewijzen, met name voor de intrekbaarheidseigenschap, door de kleine statistische fouten die bij hint-gebaseerde schema's horen te vermijden.

Belangrijkste Bijdragen

Algemeen Framework: Het artikel introduceert de eerste abstracte constructie voor intrekbare handtekeningen gebaseerd op het Fiat–Shamir met aborts paradigma, waarmee de kloof tussen het Liu–Baek–Susilo model en post-quantum lattice cryptografie wordt overbrugd.
Beveiligingsbewijzen:
- Onvervalsbaarheid: Het schema wordt bewezen onvervalsbaar onder insider corruptie (waarbij de tegenstander de geheime sleutel van de verifieerder bezit) in het (Quantum) Random Oracle Model (QROM). Het bewijs reduceert naar de EUF-CMA veiligheid van het onderliggende lattice handtekeningschema (SelfTargetMSIS/MSIS aannames).
- Intrekbaarheid (Withdrawability): Het schema wordt bewezen intrekbaar, wat betekent dat een tegenstander niet kan onderscheiden of een handtekening is gegenereerd door de ondertekenaar of de aangewezen verifieerder. Voor de no-hint instantiatie is deze eigenschap statistisch (informatie-theoretisch) met $\varepsilon_{zk} = 0$ , leunend op de perfecte naHVZK (non-abort honest-verifier zero-knowledge) van het onderliggende identificatieschema en de min-entropie van de commitments.
Aanpassing aan Post-Quantum Beperkingen: Het artikel adresseert expliciet het gebrek aan een lattice-gebaseerd Diffie-Hellman gedeeld geheim. Het demonstreert dat designatie kan worden bereikt via Public Key Encryption (PKE) in plaats van NIKE, en dat ondertekenaar-ambiguïteit kan worden bereikt via OR-bewijzen in plaats van algebraïsche symmetrie.

Resultaten

Concrete Beveiliging: Voor de no-hint Dilithium instantiatie biedt het artikel concrete beveiligingsgrenzen. Het onvervalsbaarheidsvoordeel wordt begrensd door de veiligheid van het onderliggende schema plus een verwaarloosbare term gerelateerd aan random oracle programming ( $2^{-1024}$ ). Het intrekbaarheidsvoordeel wordt begrensd door $1/2$ plus een verwaarloosbare statistische term, wat effectief perfecte ambiguïteit bereikt voor de aangewezen verifieerder in het no-hint geval.
Vergelijking: De auteurs bieden een gedetailleerde vergelijking met het Liu–Baek–Susilo schema (Tabel 2). Hoewel de lattice constructie extra sleutelmateriaal (encryptiesleutels) vereist en resulteert in grotere handtekeningen (vanwege de encryptie overhead), wint het twee belangrijke eigenschappen: de intrekbare handtekening is pseudowillekeurig (verbergt zijn bestaan voor derde partijen) en de non-transferability tegen de aangewezen verifieerder is perfect (statistisch) in plaats van computationeel.

Betekenis
Het artikel claimt significant te zijn als een noodzakelijke adaptatie van de intrekbare handtekening primitief naar het post-quantum tijdperk. Het stelt vast dat intrekbaarheid bereikbaar is in lattice-gebaseerde cryptografie zonder te vertrouwen op inefficiënte of niet-bestaande lattice-analoga van Diffie-Hellman. Door de mechanismen van designatie (encryptie) en ambiguïteit (OR-bewijzen) te scheiden, biedt de auteur een robuuste, bewezen veilige constructie die de beveiligingseigenschappen van onderliggende schema's zoals Dilithium behoudt terwijl het de cruciale flexibiliteit van handtekeningintrekking toevoegt. Het werk suggereert dat deze constructies de quantumresistentie in blockchain-systemen kunnen verbeteren waar transactie-intrekking gewenst is maar traditioneel moeilijk te implementeren is.