Hierarchical Identity-Based Signature with Designated Aggregator from Lattices

Sintesi Tecnica: Firma basata su Identità Gerarchica con Aggregatore Designato da Reticoli

Enunciato del Problema
Nelle organizzazioni gerarchiche su larga scala (ad esempio, università, agenzie governative, corporazioni), l'autenticazione di dati provenienti da molteplici utenti attraverso diversi livelli presenta sfide significative. La tradizionale Infrastruttura a Chiave Pubblica (PKI) si affida alle Autorità di Certificazione (CA), creando un overhead di gestione considerevole. Mentre l'Idendity-Based Cryptography (IBC) elimina i certificati utilizzando le identità come chiavi pubbliche, gli standard degli schemi di Identity-Based Signature (IBS) tipicamente si basano su un singolo Generatore di Chiavi Private (PKG). Questa centralizzazione crea un collo di bottiglia nelle prestazioni e un singolo punto di guasto, rendendolo inadatto per gerarchie ampie e distribuite. Inoltre, quando numerosi utenti in una gerarchia devono firmare dati, la memorizzazione e la verifica delle singole firme per ogni utente risultano inefficienti in termini di tempo, spazio e larghezza di banda. Gli esistenti schemi di Hierarchical Identity-Based Signature (HIBS) spesso si basano su assunzioni teorico-numeriche (come il problema del Logaritmo Discreto) che sono vulnerabili agli attacchi quantistici, o mancano della capacità di aggregare le firme di più rami in una singola prova compatta.

Metodologia
Gli autori propongono uno schema di Hierarchical Identity-Based Signature with Designated Aggregator (HIBS-DA) costruito su reticoli, fornendo sicurezza post-quantistica. La metodologia integra tre componenti fondamentali:

1. Delega di Chiavi Gerarchica: Il sistema utilizza una struttura ad albero in cui un Root PKG delega la generazione delle chiavi verso il basso attraverso $t$ livelli. Un'entità figlia deriva la propria chiave segreta dalla chiave segreta del genitore utilizzando l'algoritmo BasisDelegation (specificamente BasisDel), garantendo che la struttura della trapdoor sia preservata senza rivelare la trapdoor del genitore.
2. Crittografia basata su Reticoli: Lo schema si basa sulla difficoltà del problema Short Integer Solution (SIS). Impiega algoritmi quali TrapGen per la generazione di matrici pubbliche e basi trapdoor corte, SamplePre per la generazione di firme (vettori brevi) e SampleRwithBasis per la generazione di matrici invertibili.
3. Aggregazione Designata: Per affrontare l'inefficienza della verifica di molteplici firme, lo schema introduce un aggregatore designato. Questa entità raccoglie le singole firme da $N$ utenti a un livello gerarchico specifico $k$. Utilizzando il Teorema Cinese del Resto (CRT), l'aggregatore combina queste firme in una singola firma aggregata compatta. Un passaggio cruciale consiste nel proiettare il vettore combinato sull'intersezione dei reticoli associati ai $N$ utenti per garantire che la firma aggregata risultante rimanga breve e valida.

Contributi Chiave

• Prima Costruzione HIBS-DA basata su Reticoli: Il documento sostiene di presentare la prima costruzione di uno schema HIBS-DA basato su assunzioni di reticoli, colmando una lacuna nella letteratura dove non esisteva precedentemente tale schema.
• Sintassi Formale e Modello di Sicurezza: Gli autori definiscono formalmente il framework HIBS-DA, composto da sei algoritmi: Setup, Derive, Sign, Verify, Aggregate e AggregateVerify. Stabiliscono un modello di sicurezza basato sulla Existential Unforgeability under Adaptive Identity and Chosen Message Attack (EUF-ID-CMA).
• Prova di Sicurezza: Lo schema è dimostrato sicuro sotto l'assunzione che il problema SIS sia computazionalmente intrattabile. La prova utilizza un approccio riduzionista, mostrando che qualsiasi avversario probabilistico in tempo polinomiale (PPT) capace di falsificare una firma aggregata può essere utilizzato per risolvere il problema SIS.
• Analisi dell'Efficienza: Il documento fornisce un'analisi completa della complessità, dimostrando che lo schema è non interattivo (complessità di round zero) e offre riduzioni significative nei costi di comunicazione e verifica rispetto alla verifica delle singole firme.

Risultati

• Correttezza: Lo schema garantisce che le singole firme siano valide e che la firma aggregata autentichi correttamente tutti i messaggi e le identità sottostanti del livello gerarchico specifico.
• Sicurezza: La costruzione raggiunge la sicurezza EUF-ID-CMA, resistendo alla falsificazione anche quando un avversario ha accesso a oracoli di estrazione chiavi e di firma per varie identità e messaggi.
• Metriche di Complessità:
  • Comunicazione: La complessità totale della comunicazione è approssimativamente $O((tm^2 + Nm)\lceil \log_2 q \rceil)$ bit, dove $t$ è la profondità della gerarchia, $N$ è il numero di firmatari, e $m, n, q$ sono i parametri del reticolo. Ciò rappresenta una riduzione significativa rispetto alla trasmissione di $N$ singole firme.
  • Computazione: La fase di Setup ha una complessità di $\tilde{O}(n^2)$, Derive è $\tilde{O}(k \cdot m^3)$, Sign e Verify sono rispettivamente $\tilde{O}(m^2)$ e $O(m^2)$, e Aggregate comporta $O(Nm)$ per il CRT e $\tilde{O}(m^2)$ per il campionamento. AggregateVerify richiede $O(Nm^2)$.
  • Complessità di Round: Lo schema è non interattivo, richiedendo zero round di comunicazione per i processi core di firma e aggregazione.

Significatività
Il documento posiziona lo schema HIBS-DA come una soluzione pratica per i moderni sistemi decentralizzati su larga scala che richiedono un'autenticazione strutturata di dati da molteplici fonti. Combinando la gestione gerarchica delle chiavi con l'aggregazione delle firme, lo schema affronta i problemi di scalabilità della tradizionale IBS e l'overhead dei certificati della PKI. Fondamentalmente, basando la costruzione sui reticoli, lo schema offre sicurezza post-quantistica, rendendolo adatto a proteggere le infrastrutture critiche in settori come l'e-governance, la condivisione sicura dei dati e la gestione aziendale. Gli autori sottolineano che lo schema consente l'autenticazione efficiente di documenti provenienti da più rami di una gerarchia utilizzando una singola firma compatta, minimizzando così l'overhead computazionale e di comunicazione.