Lattice-based extended withdrawability

Technische Samenvatting: Lattice-gebaseerde Uitgebreide Terugroepbaarheid

Probleemstelling
Digitale handtekeningen bieden traditioneel permanentie: eenmaal ondertekend, blijft een bericht onbeperkt verifieerbaar onder de publieke sleutel van de ondertekenaar. Veel gedecentraliseerde applicaties (bijv. tijdelijke toegang, herroepbare overeenkomsten, gedecentraliseerde escrow) vereisen echter de mogelijkheid om een handtekening terug te trekken zonder de geheime sleutel te onthullen of andere handtekeningen ongeldig te maken. Liu, Susilo en Baek introduceerden extended withdrawable signatures (EWS) om dit aan te pakken, waarbij een handtekening ambigu is binnen een verzameling potentiële ondertekenaars totdat de werkelijke ondertekenaar deze "bevestigt". Hun constructie steunt op discrete-logaritme primitieven (Schnorr-handtekeningen en 1-uit-N-handtekeningen).

Dit artikel behandelt de "post-quantum kloof": het algoritme van Shor doorbreekt de fundamenten van de discrete-logaritme die ten grondslag liggen aan bestaande EWS-schema's. Hoewel lattice-gebaseerde handtekeningen (bijv. Dilithium) bestaan, faalt een directe "letterlijke transcriptie" van de Liu-Susilo-Baek (LSB) constructie naar lattices vanwege structurele obstructies. Specifiek steunt het LSB-schema op het publiceren van multiplicatieve verschuivingen van publieke sleutels om de bijdrage van de ondertekenaar te her-randomiseren. In de lattice-setting (Fiat-Shamir met aborts) nemen dergelijke verschuivingen de vorm aan van $As_1 s_j$, die een gemeenschappelijke factor $As_1$ delen met de publieke sleutel van de ondertekenaar $t_i = As_1 + s_2$. Het publiceren van deze verschuivingen lekt de identiteit van de ondertekenaar, wat de vereiste ambiguïteit doorbreekt.

Methodologie
De auteurs stellen een nieuwe constructie voor voor lattice-gebaseerde EWS die afwijkt van de LSB-aanpak door het schema te behandelen als een claimable ring signature (Park en Sealfon). In plaats van te proberen publieke sleutels in het openbaar te her-randomiseren, scheidt de constructie de twee kernfuncties van EWS:

1. Ambiguïteit: Wordt geboden door een anonieme 1-uit-N (ring) handtekening, gebruikt als een black box.
2. Bevestiging: Wordt geboden door de claim van de ondertekenaar, bestaande uit een bindende handtekening op het terugroepbare object en het openen van een hiding commitment naar de index van de ondertekenaar.

De constructie werkt volgens het Fiat-Shamir met aborts paradigma en steunt op drie modulaire ingrediënten:

• Een basis-handtekeningschema (bijv. een no-hint, full-$t$ Dilithium-stijl schema).
• Een anonieme 1-uit-N handtekening (geïnstantieerd via een lattice one-out-of-many bewijs).
• Een hiding-and-binding commitment-schema (Ajtai-stijl).

De withdrawable handtekening $\sigma$ bestaat uit een ring-handtekening $\sigma_r$ op het bericht en een commitment $C$ naar de index van de ondertekenaar, samen met de verzameling publieke sleutels. Om te bevestigen, onthult de ondertekenaar de opening $(i, \rho)$ van $C$ en ondertekent het gehele withdrawable object $\langle \mu, \pi, \sigma \rangle$ met hun eigen basis-geheime sleutel.

Belangrijkste Bijdragen

1. Verfijning van het Beveiligingsmodel: De auteurs verfijnen het beveiligingsmodel van LSB.

   • Ze vervangen de LSB "volledigheid" definitie van uitgebreide terugroepbaarheid door een anonymity-until-claim ononderscheidbaarheidsspel (Definitie 14), dat de hiding-garantie expliciet vastlegt.
   • Ze introduceren claimability soundness (Definitie 16), wat ervoor zorgt dat een bevestigde handtekening bindt aan een unieke ondertekenaar-index, waardoor wordt voorkomen dat een tegenstander dezelfde handtekening aan verschillende ringleden toeschrijft.
   • Ze formaliseren unforgeability under insider corruption met een vaste doel-index, waarbij het verlies door de multiplicatieve $q_H$ (hash query) reductie die aanwezig is in het LSB-bewijs wordt vermeden.

2. Generieke Constructie: Een generieke constructie van EWS over het Fiat-Shamir met aborts paradigma wordt gepresenteerd. Cruciaal is dat er geen ondertekenaar-afgeleide waarde in het openbaar wordt gepubliceerd. Ambiguïteit wordt uitsluitend afgeleid van de zero-knowledge eigenschappen van de ring-handtekening, en traceerbaarheid wordt afgeleid van de bindingseigenschap van de commitment.

3. Onmogelijkheidsresultaat: Het artikel bewijst (Propositie 2) dat een letterlijke lattice-transcriptie van de LSB 1-uit-N handtekening (gebruikmakend van additive challenge splitting) onveilig is. In de lattice-setting met sparse challenges is de waarschijnlijkheid dat een eerlijke ondertekenaar een geldige challenge split produceert verwaarloosbaar ($2^{-\Omega(n)}$), en zelfs als volledigheid zou worden gepatcht, zou anonimiteit falen omdat het gesimuleerde transcript niet ononderscheidbaar zou zijn van een echt transcript.

4. Volledige Beveiligingsbewijzen: De auteurs leveren expliciete game-gebaseerde reducties in het (Quantum) Random Oracle Model (QROM) voor:

   • Correctheid: Reductie naar de correctheid van de onderliggende primitieven.
   • Uitgebreide Terugroepbaarheid: Reductie naar de hiding van de commitment (Decisional MLWE) en de anonimiteit van de 1-uit-N handtekening.
   • Onvervalsbaarheid: Reductie naar de EUF-CMA veiligheid van de basis-handtekening (zonder rewinding en zonder $q_H$ verlies).
   • Claimability Soundness: Reductie naar de binding van de commitment (MSIS).

5. Instantiatie: Het schema wordt geïnstantieerd met een no-hint, full-$t$ Dilithium-stijl basis-handtekening en een gevestigd lattice one-out-of-many bewijs. Het artikel bespreekt parameterkeuzes en merkt op dat HAETAE als alternatief voor de basis kan dienen.

Resultaten
Het artikel stelt vast dat de voorgestelde constructie:

• Correct is: Eerlijke handtekeningen verifiëren met een overweldigende waarschijnlijkheid.
• Uitgebreid Terugroepbaar is: Een tegenstander die alle geheime sleutels bezit, kan niet onderscheiden welk lid van een ring een withdrawable handtekening heeft geproduceerd totdat de ondertekenaar deze bevestigt.
• Onvervalsbaar is: Zelfs met toegang tot ondertekenings-oracles en de geheime sleutels van alle ringleden behalve de doelwit, kan een tegenstander geen bevestigde handtekening vervalsen voor een nieuw bericht.
• Sound is: Een bevestigde handtekening kan niet aan twee verschillende ondertekenaars worden toegeschreven.

De beveiliging rust op standaard module-lattice aannames: Decisional MLWE, MSIS en SelfTargetMSIS, naast de zero-knowledge eigenschap van het 1-uit-N bewijs.

Significantie
Het artikel claimt significantie door de eerste veilige, post-quantum realisatie van uitgebreide terugroepbare handtekeningen te bieden. Het demonstreert dat de discrete-logaritme constructie van LSB niet direct naar lattices kan worden overgebracht vanwege het gebrek aan "vrije re-randomisatie" van gedeelde waarden. Door het probleem te herformuleren als een claimable ring signature en een commitment-gebaseerd bevestigingsmechanisme te gebruiken, bereiken de auteurs een schema dat:

• Post-Quantum Veilig is: Bestand tegen quantum-tegenstanders via lattice-aannames.
• Publiekelijk Verifieerbaar is: In tegen tegenstelling tot designated-verifier varianten, kan elke partij de withdrawable handtekening verifiëren.
• Modulair is: De beveiligingsbewijzen rusten alleen op de interfaces van de onderliggende primitieven, wat het mogelijk maakt om verschillende lattice-gebaseerde componenten (bijv. verschillende basis-handtekeningen of ring-bewijzen) te vervangen zonder het hele systeem opnieuw te bewijzen.
• Getrouw is aan de Oorspronkelijke Doelen: Het ontwerp behoudt de functionele doelen en intuïtie van het oorspronkelijke LSB-schema, terwijl het de structurele gebreken in de lattice-setting corrigeert.