La Fully Homomorphic Encryption: crittografia per la protezione del Cloud

Introduzione

Negli ultimi anni, il ricorso a soluzioni di Cloud Computing è cresciuto significativamente grazie ai vantaggi economici, prestazionali e di scalabilità offerti dai servizi dei principali provider internazionali. Tali piattaforme consentono di ridurre i costi di gestione delle infrastrutture on-premise, facilitando la condivisione e l’elaborazione di grandi quantità di dati e integrando strumenti avanzati basati su Machine Learning (ML). Tuttavia, l’affidamento dei dati a fornitori esterni può introdurre importanti rischi per la riservatezza, soprattutto in contesti sensibili (quali ad esempio la Difesa e la Sanità), nei quali la condivisione delle informazioni è limitata da stringenti vincoli normativi ed elevati requisiti di confidenzialità.

Dal punto di vista della sicurezza, è possibile distinguere tre stati in cui possono trovarsi i dati durante il loro ciclo di vita:

  • Data-in-transit: identifica i dati durante la trasmissione tra dispositivi, utenti o sistemi differenti.
  • Data-at-rest: rappresenta i dati conservati su supporti di memoria, fisici o virtuali, quali dischi locali, database e infrastrutture Cloud.
  • Data-in-use: comprende i dati durante la loro elaborazione da parte di applicazioni o sistemi informatici, ad esempio nell’esecuzione di algoritmi di Machine Learning.

Mentre i primi due possono essere protetti efficacemente mediante tecniche crittografiche consolidate, come Diffie-Hellman per lo scambio delle chiavi e AES per la cifratura, la protezione dei dati in uso rappresenta ancora una sfida significativa, poiché le elaborazioni tradizionali richiedono generalmente la disponibilità dei dati in chiaro. Per affrontare tale problematica, sono state sviluppate diverse tecniche crittografiche, tra cui la Multi-Party Computation (MPC), che consente a più partecipanti di calcolare congiuntamente una funzione sui rispettivi input privati, preservandone la riservatezza attraverso un protocollo interattivo, e la Functional Encryption (FE), che permette a un utente in possesso di una specifica chiave di decifratura di ottenere il risultato della valutazione di una determinata funzione sui dati cifrati, senza accedere direttamente al messaggio in chiaro. Tra le tecniche volte a garantire la riservatezza dei data-in-use assume particolare rilevanza anche la Homomorphic Encryption (HE), o cifratura omomorfica, una tecnica crittografica che consente di eseguire operazioni direttamente su dati cifrati, senza doverli decifrare durante l’elaborazione.

La Fully Homomorphic Encryption

Il termine Homomorphic Encryption deriva dal concetto matematico di omomorfismo, che descrive la proprietà di preservare determinate operazioni tra due strutture. Nel contesto crittografico, tale proprietà consente di eseguire operazioni sui dati cifrati ottenendo un risultato che, una volta decifrato, corrisponde a quello che si otterrebbe applicando le medesime operazioni ai dati in chiaro. Formalmente, dato un algoritmo di cifratura Enc() e due operazioni \ast_1 e \ast_2, uno schema crittografico è detto omomorfo rispetto a tali operazioni se, per ogni coppia di messaggi m_1 e m_2 appartenenti allo spazio dei messaggi, vale la relazione:

 

Enc(m_1) \ast_2 Enc(m_2) = Enc(m_1 \ast_1 m_2)

 

Questa proprietà consente di eseguire operazioni direttamente sui dati cifrati, ottenendo un cifrato corrispondente al risultato dell’operazione sui messaggi in chiaro. Combinando più operazioni omomorfe è quindi possibile valutare funzioni più complesse senza decifrare i dati.

In base alle operazioni supportate e ai limiti di valutazione, gli schemi di cifratura omomorfica si distinguono in tre categorie principali:

  • PHE (Partially Homomorphic Encryption): consente di eseguire un’unica tipologia di operazione omomorfa, come l’addizione o la moltiplicazione, un numero arbitrario di volte;
  • SHE (Somewhat Homomorphic Encryption): supporta più tipologie di operazioni omomorfe, ma entro determinati limiti sul numero di valutazioni eseguibili;
  • FHE (Fully Homomorphic Encryption): permette di valutare circuiti computazionali arbitrari sui dati cifrati, senza limiti intrinseci alla profondità del calcolo.

Storia

Le prime idee relative alla possibilità di eseguire operazioni direttamente su dati cifrati risalgono al 1978 con l’articolo “On data banks and privacy homomorphisms” di Rivest, Adleman e Dertouzos. Nei decenni successivi, la ricerca crittografica ha portato allo sviluppo di numerosi schemi di PHE e SHE, mentre la realizzazione di uno schema di FHE sembrava irraggiungibile. Una svolta fondamentale si è verificata nel 2009, quando Craig Gentry ha presentato, nella sua tesi di dottorato, il primo schema di FHE che dimostrava la fattibilità di una cifratura in grado di supportare elaborazioni arbitrariamente complesse sui dati cifrati. Il suo lavoro ha inoltre introdotto il concetto di bootstrapping, un meccanismo fondamentale per la costruzione di schemi omomorfici completi, che ha costituito la base per i successivi sviluppi e che verrà descritto più in dettaglio nel seguito.

Negli anni seguenti, la ricerca ha portato a un progressivo miglioramento delle prestazioni, dando origine a diverse generazioni di schemi di FHE. Ciò che Gentry ha proposto nel 2009 viene solitamente identificato come la prima generazione degli schemi di FHE, mentre la seconda generazione è composta da schemi quali BGV e BFV, che hanno introdotto significativi miglioramenti in termini di efficienza, favorendo le prime applicazioni pratiche. La terza generazione, comprendente schemi come FHEW e TFHE, ha ulteriormente ottimizzato le operazioni omomorfe e il processo di bootstrapping. Infine, lo schema CKKS, introdotto nel 2016 e che si identifica con la cosiddetta quarta generazione, ha ampliato le possibilità applicative della FHE, soprattutto grazie al supporto di operazioni su valori reali e approssimati, risultando particolarmente adatto all’elaborazione di dati in algoritmi di Machine Learning.

Learning With Error (LWE) e Bootstrapping

La maggior parte degli schemi di Fully Homomorphic Encryption (FHE) basano la propria sicurezza computazionale sul problema del Learning With Errors (LWE), la cui difficoltà deriva dalla presenza di un vettore di errore introdotto durante la cifratura, che rende computazionalmente difficile recuperare il messaggio in chiaro o la chiave segreta. Sebbene tale errore sia fondamentale per la sicurezza dello schema, esso tende ad aumentare durante l’esecuzione di operazioni omomorfe, con una crescita che dipende dal tipo e dal numero di operazioni effettuate. Quando l’errore supera una determinata soglia, legata ai parametri crittografici scelti, non è più possibile garantire la correttezza della decifratura. Per consentire un numero arbitrario di operazioni omomorfe è quindi necessario un meccanismo che riduca l’errore accumulato senza compromettere la correttezza delle elaborazioni.

A tale scopo, Craig Gentry ha introdotto nel 2009 il concetto di bootstrapping, una procedura che consente di ridurre l’errore di un ciphertext valutando omomorficamente la funzione di decifratura. L’idea consiste nel partire da un ciphertext c_1 = Enc_{k_1}(m), il cui errore si avvicina alla soglia critica, e utilizzare una seconda chiave k_2 per cifrare nuovamente il ciphertext, ottenendo c_2 = Enc_{k_2}(c_1). Il server può quindi valutare omomorficamente la funzione di decifratura utilizzando il ciphertext e una bootstrapping key, che contiene la chiave k_1 cifrata mediante k_2. Il risultato è un nuovo ciphertext che cifra lo stesso messaggio m sotto la chiave k_2, ma con un livello di errore sufficientemente ridotto da consentire ulteriori elaborazioni omomorfe. Ripetendo questa procedura quando necessario, è possibile costruire schemi FHE capaci di supportare calcoli di profondità arbitraria.

In Fig. è illustrato il processo di bootstrapping: i rettangoli azzurro e verde rappresentano rispettivamente le cifrature sotto le chiavi k_1 e k_2, mentre i termometri illustrano graficamente il livello di errore associato a ciascun ciphertext.

 

Rappresentazione del processo di bootstrapping
Rappresentazione del processo di bootstrapping (da TFHE Deep Dive with Ilaria Chillotti).

 

Sebbene il bootstrapping consenta di controllare la crescita dell’errore e di eseguire quindi un numero arbitrario di operazioni omomorfe, il suo costo computazionale rappresenta una delle principali criticità degli schemi di FHE. Più in generale, le elaborazioni su dati cifrati richiedono risorse e tempi di esecuzione significativamente superiori rispetto alle operazioni equivalenti sui dati in chiaro. L’ottimizzazione delle prestazioni dei principali schemi di FHE è quindi un obiettivo centrale della ricerca nel settore e un requisito importante per favorire l’impiego di tale tecnologia in scenari applicativi reali.

L’accelerazione hardware per la FHE

Il significativo overhead computazionale che caratterizza gli schemi di Fully Homomorphic Encryption (FHE) deriva principalmente dalla necessità di eseguire operazioni su polinomi, utilizzati per rappresentare i ciphertext. In particolare, le moltiplicazioni polinomiali risultano più onerose rispetto alle operazioni aritmetiche effettuate sui dati in chiaro. Per ridurne la complessità, si ricorre a tecniche quali la Fast Fourier Transform (FFT) e una sua variante applicabile su campi finiti, denominata Number Theoretic Transform (NTT). Nonostante queste ottimizzazioni, tali operazioni vengono eseguite molto frequentemente durante i calcoli omomorfi e possono rappresentare una quota significativa del costo computazionale complessivo.

Un secondo fattore critico è rappresentato dal bootstrapping, necessario per contenere la crescita dell’errore accumulato durante le elaborazioni e preservare la correttezza della decifratura. Questa procedura richiede un elevato numero di operazioni sui ciphertext e può arrivare a occupare oltre il 90% del tempo di calcolo in determinati scenari applicativi. Poiché FFT e NTT costituiscono componenti fondamentali di numerose operazioni negli schemi FHE e possono rappresentare una parte consistente del carico computazionale, la loro accelerazione costituisce una delle principali strategie per migliorare le prestazioni complessive della cifratura omomorfica.

Per affrontare queste criticità e migliorare le prestazioni degli schemi di FHE, negli ultimi anni sono stati sviluppati, sia in ambito accademico sia industriale, acceleratori hardware dedicati, basati principalmente su tre tecnologie: GPU, FPGA e ASIC. Ciascuna di queste soluzioni presenta caratteristiche specifiche in termini di flessibilità, prestazioni ed efficienza energetica:

  • Graphics Processing Unit (GPU): processori caratterizzati da un elevato parallelismo, particolarmente adatti ad accelerare operazioni ripetitive e computazionalmente intensive, come le trasformate FFT e NTT.
  • Field-Programmable Gate Array (FPGA): dispositivi hardware riconfigurabili che consentono di progettare architetture specializzate per le operazioni di FHE, offrendo un compromesso tra flessibilità ed efficienza.
  • Application-Specific Integrated Circuit (ASIC): circuiti integrati progettati per eseguire specifiche operazioni, capaci di offrire elevate prestazioni ed efficienza energetica, a fronte di costi di sviluppo maggiori e di una minore flessibilità rispetto alle altre soluzioni.

Conclusioni

La Fully Homomorphic Encryption rappresenta una tecnologia dalle enormi potenzialità per la protezione dei dati in Cloud, poiché consente di delegare elaborazioni a infrastrutture esterne senza dover rivelare le informazioni in chiaro, contribuendo così a superare uno dei principali limiti delle soluzioni crittografiche tradizionali. L’importanza di questa tecnologia è testimoniata dal crescente numero di studi e progetti dedicati alla sua ottimizzazione, nonché dal forte interesse congiunto della comunità accademica e del settore industriale. Nonostante le prestazioni degli schemi attuali non siano ancora sufficienti a consentirne un impiego efficiente in molti contesti applicativi, i progressi compiuti negli ultimi anni, sia a livello algoritmico sia attraverso lo sviluppo di acceleratori hardware dedicati, stanno progressivamente riducendo tale divario. La FHE sta quindi iniziando a risultare praticabile in scenari specifici, nei quali i requisiti di riservatezza possono giustificare il maggiore costo computazionale, e si configura come una tecnologia promettente per la futura evoluzione dei servizi Cloud sicuri.


 

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

 

Gli autori

Marco Rinaudo, laureato triennale in Matematica presso l’Università degli Studi di Torino e laureato magistrale con specializzazione in Crittografia presso l’Università di Trento. In seguito ad uno stage curricolare svolto nel 2022 in Telsy, da gennaio 2023 è parte del Gruppo di Ricerca in Crittografia.