Hierarchical Identity-Based Signature with Designated Aggregator from Lattices

Technische Samenvatting: Hiërarchische Identiteitsgebaseerde Signatuur met een Gedesigneerde Aggregator gebaseerd op Lattices

Probleemstelling
In grootschalige hiërarchische organisaties (bijv. universiteiten, overheidsinstanties, bedrijven) vormt de authenticatie van gegevens van meerdere gebruikers over verschillende niveaus heen aanzienlijke uitdagingen. Traditionele Public Key Infrastructure (PKI) vertrouwt op Certificate Authorities (CA's), wat voor een substantiële beheerslast zorgt. Hoewel Identity-Based Cryptography (IBC) certificaten elimineert door identiteiten als publieke sleutels te gebruiken, vertrouwen standaard Identity-Based Signature (IBS) schema's doorgaans op een enkele Private Key Generator (PKG). Deze centralisatie creëert een prestatiebottleneck en een single point of failure, waardoor het ongeschikt is voor grote, gedistribueerde hiërarchieën. Bovendien, wanneer talloze gebruikers in een hiërarchie gegevens moeten ondertekenen, is het opslaan en verifiëren van individuele signaturen voor elke gebruiker inefficiënt qua tijd, ruimte en bandbreedte. Bestaande Hierarchical Identity-Based Signature (HIBS) schema's vertrouwen vaak op getaltheoretische aannames (zoals het discrete logaritme probleem), die kwetsbaar zijn voor quantum-aanvallen, of ze missen de mogelijkheid om signaturen van meerdere takken in een enkele compacte bewijsvoering te aggregeren.

Methodologie
De auteurs stellen een Hierarchical Identity-Based Signature with Designated Aggregator (HIBS-DA) schema voor, geconstrueerd op lattices (roosters), wat zorgt voor post-quantum beveiliging. De methodologie integreert drie kerncomponenten:

1. Hiërarchische Sleuteldelegatie: Het systeem maakt gebruik van een boomstructuur waarbij een Root PKG de sleutelgeneratie naarentoe $t$ niveaus delegeert. Een kind-entiteit afleidt zijn geheime sleutel uit de geheime sleutel van zijn ouder met behulp van het BasisDelegation algoritme (specifiek BasisDel), waardoor de trapdoor-structuur behouden blijft zonder de trapdoor van de ouder te onthullen.
2. Lattice-gebaseerde Cryptografie: Het schema berust op de hardheid van het Short Integer Solution (SIS) probleem. Het maakt gebruik van algoritmen zoals TrapGen voor het genereren van publieke matrices en korte trapdoor-bases, SamplePre voor het genereren van signaturen (korte vectoren), en SampleRwithBasis voor het genereren van inverseerbare matrices.
3. Gedesigneerde Aggregatie: Om de inefficiëntie van het verifiëren van meerdere signaturen aan te pakken, introduceert het schema een gedesigneerde aggregator. Deze entiteit verzamelt individuele signaturen van $N$ gebruikers op een specifiek hiërarchisch niveau $k$. Met behulp van de Chinese Reststelling (CRT) combineert de aggregator deze signaturen tot een enkele, compacte geaggregeerde signatuur. Een cruciale stap is het projecteren van de gecombineerde vector op de intersectie van de lattices geassocieerd met de $N$ gebruikers om ervoor te zorgen dat de resulterende geaggregeerde signatuur kort en geldig blijft.

Belangrijkste Bijdragen

• Eerste Lattice-gebaseerde HIBS-DA Constructie: De paper claimt de eerste constructie van een HIBS-DA schema te presenteren gebaseerd op lattice-aannames, waarmee een gat in de literatuur wordt opgevuld waar voorheen geen dergelijk schema bestond.
• Formele Syntaxis en Beveiligingsmodel: De auteurs definiëren formeel het HIBS-DA framework, bestaande uit zes algoritmen: Setup, Derive, Sign, Verify, Aggregate, en AggregateVerify. Ze stellen een beveiligingsmodel vast gebaseerd op Existential Unforgeability under Adaptive Identity and Chosen Message Attack (EUF-ID-CMA).
• Beveiligingsbewijs: Het schema wordt bewezen veilig onder de aanname dat het SIS-probleem computationeel onhaalbaar is. Het bewijs maakt gebruik van een reductie-benadering, waarbij wordt aangetoond dat elke probabilistische polynomiale tijd (PPT) tegenstander die in staat is tot het vervalsen van een geaggregeerde signatuur, gebruikt kan worden om het SIS-probleem op te lossen.
• Efficiëntieanalyse: De paper biedt een uitgebreide complexiteitsanalyse en demonstreert dat het schema niet-interactief is (nul rondte-complexiteit) en significante reducties biedt in communicatie- en verificatiekosten vergeleken met het verifiëren van individuele signaturen.

Resultaten

• Correctheid: Het schema garandeert dat individuele signaturen geldig zijn en dat de geaggregeerde signatuur correct alle onderliggende berichten en identiteiten van het specifieke hiërarchische niveau authenticeert.
• Beveiliging: De constructie bereikt EUF-ID-CMA beveiliging, waarbij weerstand wordt geboden tegen vervalsing, zelfs wanneer een tegenstander toegang heeft tot key extraction en signing oracles voor diverse identiteiten en berichten.
• Complexiteitsmetrieken:
  • Communicatie: De totale communicatiecomplexiteit is ongeveer $O((tm^2 + Nm)\lceil \log_2 q \rceil)$ bits, waarbij $t$ de hiërarchie-diepte is, $N$ het aantal signers, en $m, n, q$ de lattice-parameters zijn. Dit vertegenwoordigt een significante reductie vergeleken met het verzenden van $N$ individuele signaturen.
  • Computation: De Setup fase heeft een complexiteit van $\tilde{O}(n^2)$, Derive is $\tilde{O}(k \cdot m^3)$, Sign en Verify zijn respectievelijk $\tilde{O}(m^2)$ en $O(m^2)$, en Aggregate omvat $O(Nm)$ voor CRT en $\tilde{O}(m^2)$ voor sampling. AggregateVerify vereist $O(Nm^2)$.
  • Rondte-complexiteit: Het schema is niet-interactief, waarbij nul rondtes van communicatie vereist zijn voor de kernprocessen van het ondertekenen en aggregeren.

Betekenis
De paper positioneert het HIBS-DA schema als een praktische oplossing voor moderne, grootschalige gedecentraliseerde systemen die een gestructureerde, multi-source data-authenticatie vereisen. Door hiërarchisch sleutelbeheer te combineren met signatuur-aggregatie, adresseert het schema de schaalbaarheidsproblemen van traditionele IBS en de certificaatoverhead van PKI. Cruciaal is dat het door de constructie op lattices te baseren, het schema post-quantum beveiliging biedt, wat het geschikt maakt voor de toekomstbestendigheid van kritieke infrastructuur in sectoren zoals e-governance, veilige gegevensdeling en bedrijfsmanagement. De auteurs benadrukken dat het schema de efficiënte authenticatie van documenten van meerdere takken van een hiërarchie mogelijk maakt met behulp van een enkele compacte signatuur, waardoor de computationele en communicatieve overhead wordt geminimaliseerd.