💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

Questo articolo presenta un'implementazione accelerata tramite GPU di un meccanismo di incapsulamento delle chiavi basato su Learning with Errors (LWE) utilizzando OpenACC, dimostrando incrementi di velocità significativi (fino a 208×) e una migliore efficienza energetica sulle GPU NVIDIA, in particolare sul Grace Hopper Superchip, rispetto ai sistemi tradizionali basati su CPU e H100.

Autori originali: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Pubblicato 2026-06-02

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di chiudere un baule del tesoro con una chiave così complessa che nemmeno un robot super intelligente dal futuro (un computer quantistico) riuscirebbe a scassinare. Questo è l'obiettivo della Crittografia Post-Quantistica. Il "lucchetto" specifico su cui si concentra questo articolo è chiamato Learning With Errors (LWE).

Pensa a LWE come al tentativo di risolvere un enorme puzzle matematico dove qualcuno ha intenzionalmente aggiunto un po' di "statico" o "rumore" al segnale. È facile creare il rumore, ma è incredibilmente difficile filtrarlo per trovare il messaggio originale senza la chiave segreta. Il problema è che risolvere questo puzzle su un computer standard è come cercare di spostare una montagna un granello di sabbia alla volta: richiede un tempo infinito.

Ecco cosa hanno fatto i ricercatori per velocizzare le cose, spiegato in modo semplice:

1. Il Problema: La CPU è un Camion Lento

Gli autori sono partiti con una versione di questa crittografia che gira su un normale processore di un computer (la CPU). Hanno scoperto che la CPU faceva fatica. Era come un singolo camion che cercava di spostare migliaia di scatole. Ogni volta che doveva spostare una scatola (un pezzo di dato) dal magazzino (memoria) al cassone del camion, doveva fermarsi, caricarla e guidare. Il camion passava la maggior parte del tempo ad aspettare, non a lavorare.

2. La Soluzione: La GPU è una Flotta di Droni

Per risolvere questo problema, hanno spostato il lavoro pesante su una GPU (Graphics Processing Unit). Se la CPU è un singolo camion da consegna, la GPU è una flotta di migliaia di piccoli droni velocissimi.

L'Analogia: Invece di un solo camion che trasporta una scatola alla volta, la GPU può trasportare migliaia di scatole simultaneamente.
Lo Strumento: Hanno usato un linguaggio di programmazione chiamato OpenACC. Immaginatelo come un telecomando universale. Invece di riscrivere l'intero manuale di istruzioni per i droni (il che sarebbe difficile e soggetto a errori), hanno semplicemente puntato il telecomando verso le istruzioni esistenti del camion e detto: "Ehi, fai anche questo, ma più velocemente!". Questo ha reso facile aggiornare il software senza romperlo.

3. Il Collo di Bottiglia: Il Generatore di "Rumore"

In questa crittografia, è necessario molto "rumore" casuale per rendere il puzzle difficile.

Il Vecchio Metodo: La CPU generava il rumore, lo scriveva e poi lo guidava verso la GPU. Era come se il camionista si fermasse per scrivere una lista della spesa, guidasse fino al negozio, comprasse gli articoli e tornasse indietro. Era uno spreco di tempo enorme.
La Soluzione: Hanno installato un "generatore di rumore" direttamente all'interno del magazzino della GPU. Ora, i droni possono generare il proprio rumore casuale sul posto. Non devono aspettare che il camion porti loro i rifornimenti. Questo ha ridotto drasticamente i tempi di attesa.

4. Il Trucco del "Batching" (Lavorazione a Blocchi)

Il processo di crittografia comporta la risoluzione di 256 piccoli puzzle contemporaneamente (uno per ogni bit di un messaggio).

Il Vecchio Metodo: La GPU risolveva un puzzle, si fermava, aspettava le istruzioni, risolveva il successivo, si fermava, aspettava... come uno chef che cuoce un uovo alla volta e aspetta che il fornello si raffreddi tra un uovo e l'altro.
La Soluzione: Hanno utilizzato una strategia chiamata Intra-Operation Batching. Questo è come lo chef che mette tutti i 256 uova in una padella gigante e le cuoce tutte insieme. La GPU esegue un unico grande "lancio" per risolvere tutti i 256 puzzle simultaneamente, risparmiando una quantità massiccia di tempo.

5. I Risultati: Velocità ed Energia

I ricercatori hanno testato questo sistema su diversi tipi di computer super veloci (GPU) e lo hanno confrontato con il vecchio metodo della CPU.

Velocità: Sul computer più nuovo e potente che hanno testato (il Grace Hopper Superchip), il loro nuovo metodo è stato 208 volte più veloce del vecchio metodo della CPU.
- Analogia: Se il vecchio camion impiegava 3 ore per consegnare un pacco, la nuova flotta di droni lo fa in meno di un minuto.
- Sono stati persino in grado di risolvere dimensioni di puzzle così enormi che la vecchia CPU sarebbe andata in crash per mancanza di memoria.
Energia: Il nuovo metodo utilizza anche meno energia. Il computer Grace Hopper ha utilizzato circa metà dell'energia per fare lo stesso lavoro rispetto a un computer standard con un altro tipo di GPU veloce.
- Analogia: È come fare la stessa consegna usando un'auto ibrida invece di un camion che consuma tantissima benzina.

6. Perché è Importante

L'articolo dimostra che usando questi "droni" (GPU) e trucchi di gestione intelligente (OpenACC, batching e rumore on-device), possiamo rendere pratici questi lucchetti super sicuri e resistenti ai computer quantistici. Senza questi aumenti di velocità, la matematica sarebbe troppo lenta per essere utile nel mondo reale. Con loro, possiamo proteggere i nostri dati contro i futuri computer quantistici senza dover aspettare giorni per sentire il clic di un singolo lucchetto.

In breve: Hanno preso un metodo di crittografia lento e pesante e gli hanno dato una spinta enorme alla velocità usando migliaia di piccoli lavoratori (GPU) che lavorano insieme, generano i propri rifornimenti e smettono di aspettare istruzioni. Il risultato è un sistema centinaia di volte più veloce e molto più efficiente dal punto di vista energetico.

Sintesi Tecnica: Accelerazione tramite GPU di KEM basati su Learning With Errors utilizzando OpenACC

Problematica
L'avvento di computer quantistici su larga scala minaccia gli attuali protocolli crittografici asimmetrici (ad esempio, RSA, ECC) tramite l'algoritmo di Shor. La Crittografia Post-Quantistica (PQC) è emersa come soluzione, con gli schemi basati su reticoli, in particolare quelli che si affidano al problema del Learning With Errors (LWE), che ne sono al centro per i Meccanismi di Incapsulamento delle Chiavi (KEM). Tuttavia, gli schemi basati su LWE introducono un carico computazionale significativo a causa delle operazioni matriciali su larga scala e della generazione di casualità, rendendoli spesso impraticabili per applicazioni lato server ad alto throughput su architetture CPU standard. Sebbene l'accelerazione tramite GPU sia stata esplorata per la PQC, la maggior parte delle implementazioni esistenti si affida a ottimizzazioni specifiche per CUDA, limitando la portabilità e la produttività degli sviluppatori. Inoltre, il porting ingenuo spesso non affronta colli di bottiglia come la latenza di trasferimento della memoria host-device e la serializzazione della generazione di numeri casuali.

Metodologia
Gli autori propongono un Meccanismo di Incapsulamento delle Chiavi (KEM) basato su LWE "plain" (evitando strutture algebriche aggiuntive come Ring-LWE) e sviluppano un'implementazione orientata alla GPU utilizzando il modello di programmazione basato su direttive OpenACC. Il lavoro procede attraverso i seguenti passaggi metodologici:

Implementazione Baseline: Un'implementazione C++ dell'LWE-KEM è stata parallelizzata utilizzando OpenMP per CPU multicore. Lo schema utilizza la trasformata di Fujisaki-Okamoto (FO) per ottenere la sicurezza IND-CCA2, che coinvolge le fasi di KeyGen, Encaps e Decaps.
Porting e Ottimizzazione OpenACC: Il codice CPU è stato portato sulle GPU utilizzando OpenACC. Per superare i colli di bottiglia delle prestazioni, gli autori hanno implementato tre strategie primarie:
- Batching Intra-Operazione: Inveve di elaborare 256 bit di messaggio indipendenti sequenzialmente (scatenando lanci di kernel e trasferimenti di memoria separati), l'implementazione fonde tutte le 256 cifrature in un singolo lancio di kernel GPU. Ciò espone un parallelismo fine-grained ( $256 \times n$ elementi di lavoro) e ammortizza l'overhead di invocazione.
- Generazione di Numeri Casuali Residente sul Dispositivo (RNG): Riconoscendo che il trasferimento di vettori di rumore pre-generati tramite PCIe crea un collo di bottiglia critico, gli autori hanno integrato la libreria RNGonGPU. Questa libreria implementa un generatore di bit deterministici (DRBG) basato su AES-256 direttamente sulla GPU. Solo un seed a 64 bit viene trasferito dall'host al device, riducendo il volume di trasferimento dati di circa sei ordini di grandezza rispetto al trasferimento di vettori di rumore pre-generati.
- Gestione Esplicita dei Dati: Gli autori hanno evitato la Unified Memory di CUDA a favore di direttive esplicite enter data ed exit data per controllare deterministicamente i trasferimenti host-device, minimizzando le comunicazioni non necessarie e garantendo la coerenza dei dati solo in punti di sincronizzazione specifici (ad esempio, prima dell'hashing).
Parallelizzazione dei Kernel: Le moltiplicazioni matrice-vettore, che rappresentano il costo computazionale dominante, sono state parallelizzate gerarchicamente. Per la cifratura/decifratura, le cifrature di messaggi indipendenti sono state assegnate a gang OpenACC, mentre i componenti del ciphertext sono stati calcolati concorrentemente attraverso i lane vettoriali.

Contributi Chiave

Implementazione Open-Source: Gli autori forniscono un'implementazione open-source di un KEM basato su LWE "plain" sia per CPU (OpenMP) che per GPU (OpenACC), consentendo benchmark riproducibili.
Ottimizzazione Basata su Direttive: Un insieme di ottimizzazioni orientate alla GPU applicabili a una vasta classe di schemi LWE, dimostrando che i modelli basati su direttive (OpenACC) possono raggiungere alte prestazioni senza una profonda competenza in CUDA.
Valutazione Completa: Uno studio dettagliato delle prestazioni, dell'efficienza energetica e della scalabilità su più generazioni di GPU NVIDIA (Volta, Ampere, Hopper) e architetture (x86 + Hopper vs. l'hyperchip basato su ARM Grace Hopper).

Risultati
La valutazione è stata condotta su varie piattaforme, tra cui l'NVIDIA GH200 Grace Hopper Superchip, A100 e V100S.

Speedup: L'implementazione OpenACC ottimizzata ha ottenuto speedup significativi rispetto alla baseline multithread della CPU. Sulla piattaforma GH200, gli speedup hanno raggiunto fino a 208× per dimensioni di problemi elevate ( $n=4096$ ). L'implementazione GPU ha iniziato a superare la baseline della CPU per $n \ge 256$ .
Scalabilità: L'implementazione GPU ha dimostrato una scalabilità superiore rispetto alla versione CPU all'aumentare delle dimensioni del problema, gestendo efficacemente set di parametri (ad esempio, $n=32768$ ) che risultavano impraticabili da elaborare sulle CPU a causa della contesa della memoria e dell'overhead di sincronizzazione.
Efficienza Energetica: Sul Superchip GH200, l'implementazione ha ottenuto una riduzione di 1,78× nell'energia per soluzione rispetto a un sistema x86 + H100, guidata principalmente dal minor consumo energetico della CPU ARM-based Grace. Il miglioramento del tempo per soluzione su GH200 rispetto a x86+Hopper è stato più modesto (1,19×).
Scalabilità Architetturale: L'analisi inter-generazionale (V100S $\to$ A100 $\to$ GH200) ha rivelato che la scalabilità delle prestazioni è guidata principalmente dalla larghezza di banda della memoria HBM (High Bandwidth Memory). Tuttavia, man mano che la larghezza di banda aumenta, l'overhead relativo della generazione on-demand degli elementi della matrice (costo aritmetico) e i costi fissi della trasformata FO lato CPU iniziano a limitare la scalabilità, spostando il collo di bottiglia da puramente legato alla memoria a un mix di vincoli computazionali e di sincronizzazione.
Impatto dell'Ottimizzazione: Il profiling ha mostrato che l'implementazione ingenua era dominata dal calcolo lato host e dai trasferimenti PCIe (starvation della GPU). L'implementazione ottimizzata ha spostato il collo di bottiglia sulla sincronizzazione, con un'attività della GPU sostenuta al ~98% del tempo di iterazione.

Significatività
Il paper sostiene che i suoi risultati evidenziano l'efficacia dell'accelerazione tramite GPU per carichi di lavoro crittografici LWE computazionalmente impegnativi. Sfruttando OpenACC, gli autori dimostrano una strada verso una PQC ad alte prestazioni che bilancia programmabilità e prestazioni, evitando la necessità di codifica a basso livello in CUDA. Il lavoro suggerisce che, con le opportune ottimizzazioni (specificamente il batching intra-operazione e l'RNG residente sul dispositivo), gli schemi LWE "plain" — che offrono assunzioni di sicurezza più conservative ma costi computazionali più elevati — possono diventare pratici sulle moderne piattaforme eterogenee. Il lavoro propone inoltre di estendere questo approccio ad ambienti multi-GPU e altre architetture di acceleratori (AMD, Intel).