La Crittografia Omomorfica (Homomorphic Encryption, HE) è un tipo di crittografia che consente di eseguire operazioni matematiche su dati criptati.
In questo post introdurremmo le ragioni che hanno stimolato lo sviluppo di una simile tecnologia, studiandone le caratteristiche, e valutandone le applicazioni reali.
Questo è l’inizio di un entusiasmante viaggio alla scoperta dei segreti nascosti della Crittografia Omomorfica!
Introduzione | Homomorphic Encryption
Ogni giorno, le organizzazioni si trovano a gestire informazioni sensibili, come personally identifiable information (PII) e dati finanziari, che devono essere protetti quando salvati (i.e. data at rest) o trasferiti (i.e. data in transit).
Per garantire tale necessaria protezione si è soliti ricorrere a una tecnologia sicura e affidabile: la crittografia.
Tuttavia, sebbene i moderni algoritmi crittografici siano virtualmente inattaccabili, l’operazione apparentemente semplice di criptare le informazioni ha un grande difetto.
A un certo punto, prima o poi, i dati criptati devono essere decifrati per poterli usare.
È proprio questo il punto in cui introduciamo una vulnerabilità nel nostro altrimenti perfetto sistema di gestione delle informazioni sensibili.
Lascia che mi confidi con te: è una vulnerabilità che non mi piace, e non penso piaccia nemmeno a te.
Possiamo tenere i nostri dati, salvati in cloud, crittograficamente codificati attraverso chiavi segrete, ma nel momento in cui abbiamo il bisogno di effettuare delle operazioni, dalla modifica di un documento di testo alla ricerca su un database, occorre decifrare i dati e renderli vulnerabili.
Come eliminiamo questa debolezza?
La soluzione si chiama crittografia omomorfica.
Cos’è la crittografia omomorfica
Lo scopo dell’Homomorphic Encryption (HE) è consentire l’esecuzione di funzioni arbitrarie su dati cifrati (seppur con qualche limitazione), assicurando la validità del risultato ottenuto.
In questo modo i dati sono protetti e mantenuti privati persino durante le operazioni computazionali eseguite in ambienti poco sicuri o inaffidabili, come il cloud pubblico.
Un crittosistema con omomorfismo è analogo ad altre forme di crittografia a chiave pubblica, permettendo:
- A chiunque di cifrare il dato, l’informazione, con la chiave pubblica
- Solamente agli individui in possesso della chiave privata di decifrare il dato criptato.
Contrariamente ad altre forme di crittografia, quella omomorfica adotta però un sistema algebrico tale da permetterci di eseguire operazioni sui dati cifrati.
Siamo così in grado di ricevere i dati codificati, svolgere operazioni arbitrarie su di essi senza avere la chiave di decodifica, e ottenere un risultato coerente: quando il dato codificato è decifrato, esso corrisponde al risultato delle stesse operazioni svolte sui dati in chiaro.
Tieniti forte.
Stiamo per proseguire il nostro, sempre più interessante, viaggio.
Come funziona la crittografia omomorfica?
Il concetto di omomorfismo è prettamente matematico.
Il algebra astratta, un omomorfismo è un’applicazione tra due strutture algebriche dello stesso tipo che conserva le operazioni in esse definite.
In altri termini, l’omomorfismo descrive una trasformazione applicata a una struttura dati che ne produce una nuova, preservando la relazione tra gli elementi in entrambi i set.
Il termine deriva da un parola greca che significa “stessa struttura”.
Poiché la trasformazione applicata al set di dati mantiene la stessa struttura originaria, due identiche operazioni matematiche effettuare su dati in chiaro e su dati cifrati attraverso tale trasformazione, produrranno risultati equivalenti.
Nella pratica, quasi tutti gli schemi di Homomorphic Encryption (HE) lavorano meglio quando i dati sono interi e le operazioni coinvolte sono addizioni o moltiplicazioni.
Ciò consente di elaborare dati criptati e ottenere un risultato anch’esso criptato, benché decifrabile solamente da te.
Spiegazione tecnica
Contrariamente ad altri sistemi di computazione sicura, la Crittografia omomorfica richiede alcuni cicli iterativi per essere applicata efficacemente e sfrutta operazioni aritmetiche anziché booleane.
Più tecnicamente, un crittosistema ε è dotato di tre algoritmi:
- KeyGenε
- Encryptε
- Decryptε
Nei crittosistemi simmetrici KeyGenε genera una singola chiave che viene utilizzata dagli altri due algoritmi.
Nei crittosistemi asimmetrici KeyGenε genera due chiavi:
- pk una chiave pubblica (publick-key)
- sk una chiave segreta (secret-key)
Un crittosistema omomorfo può essere simmetrico o asimmetrico.
Inoltre la crittografia può essere di tipo:
- Probabilistico, in cui la codifica dello stesso messaggio svolta in momenti diversi produce testi cifrati differenti, grazie all’uso di un fattore aleatorio, che chiamiamo rumore, nella fase di codifica
- Deterministico, per cui messaggi in chiaro uguali producono lo stesso testo cifrato
Noi consideriamo crittosistemi asimmetrici di tipo probabilistico, a cui però dobbiamo aggiungere un algoritmo.
In crittografia omomorfa abbiamo infatti un algoritmo Evaluateε associato a un insieme Fε di funzioni permesse.
Dunque, per ogni funzione f nell’insieme Fε e per ogni testo cifrato c1 … ct con ci←Encryptε(mi) l’algoritmo Evaluateε (f, c1 … ct) fornice come output un testo cifrato c tale che Decryptε(c) = f(m1 … mt).
La ricerca di un metodo generico per effettuare operazioni su dati cifrati iniziò nel 1978, con il documento proposto da Rivest, Adleman and Dertouzos.
Da allora sono stati sviluppati diversi sistemi che possiamo raggruppare in tre grandi gruppi.
Tipologie di Homomorphic Encryption (HE)
Ora, devi sapere che esistono diverse tipologie di crittografia omomorfica.
La differenza primaria riguarda il tipo e la frequenza di operazioni matematiche che è possibile effettuare sui dati cifrati.
Distinguiamo allora:
- Partially Homomorphic Encryption (PHE)
- Somewhat Homomorphic Encryption (SHE)
- Fully Homomorphic Encryption (FHE)
Partially Homomorphic Encryption
La crittografia omomorfica parziale supporta un numero selezionato di operazioni matematiche.
Questo significa che una sola operazione, addizione o moltiplicazione, può essere eseguita un numero illimitato di volte sui testi cifrati.
Per darti un riferimento, un esempio di crittografia omomorfica parziale con supporto a operazioni moltiplicative è la crittografia RSA a chiave asimmetrica.
RSA non è quindi omomorfo alla somma.
Trovi un esempio interattivo qui.
Nonostante questa sua particolarità l’RSA è oggi ampiamente usato per definire connessioni sicure con il protocollo SSL/TSL
Somewhat Homomorphic Encryption
La crittografia “ un po’ ” omomorfica si differenzia dalla precedente perché supporta operazioni selezionate fino a una certa complessità, e un numero limitato di volte.
Fully Homomorphic Encryption
Considerato da alcuni l’Holy Grail crittografico, la crittografia totalmente omomorfica intende mantenere consistente la privacy dell’informazione, tenendola sicura e accessibile al tempo stesso.
Sviluppata a partire dalla precedente tipologia, FHE supporta sia la moltiplicazione che la somma, un numero illimitato di volte, aumentando l’efficienza della computazione a parti multiple sicura (SMPC).
Contrariamente ad altre forme di crittografia omomorfica, questa è in grado di gestire computazioni arbitrarie su testi cifrati.
L’obiettivo della Fully Homomorphic Encryption è permettere a chiunque di usare dati criptati per eseguire operazioni utili, senza decifrare l’informazione.
Tra i casi d’uso più intriganti, vi è la possibilità di aumentare la sicurezza della Cloud Computing.
Possiamo infatti salvare dati criptati in cloud, ed eseguire operazioni su tali dati, sempre in cloud, evitando il rischio che malintenzionati possano accedere al nostro account.
Siamo così in grado di raccogliere, fare ricerche e trasformare i dati senza mai permettere al cloud provider di accedere in chiaro ai dati.
Tecnicamente un crittosistema è pienamente omomorfico se a prescindere dalla complessità della funzione f ∈ Fε, non viene inficiata la correttezza della decodifica e non varia il tempo di decifratura dell’output finale di Evaluateε
Per stimare la complessità della funzione f possiamo usare il tempo di esecuzione Tf di una macchina di Turing che computi f. Usiamo quindi una misura a esso correlato, ovvero la dimensione Sf di un circuito booleano, data dal numero di porte AND, OR e NOT, che calcoli la funzione f.
Limitazioni della Fully Homomorphic Encryption
Richiedere che il crittosistema sia al tempo stesso probabilistico e pienamente omomorfo genera un conflitto.
I testi cifrati con un processo di codifica probabilistico sono infatti contaminati da un rumore che, pur rendendoli meno attaccabili, viene amplificato a ogni operazione sino a inquinare a tal punto il risultato da renderlo inutilizzabile.
Ciò si verifica quando la funzione f è troppo complessa.
Sicurezza della crittografia omomorfica
La sicurezza degli schemi di HE si basa sul problema definito Ring-Learning With Errors (RLWE).
È un problema matematico complesso, legato ai reticoli multidimensionali (high-dimensional lattices).
La difficoltà del problema RLWE è stata confermata da numeroso studi e possiamo quindi confidare che schemi basati su tale sistema siano sicuri quanto altre forme di crittografia.
Inoltre, RLWE e molti schemi di crittografia omomorfica sono considerati sicuri contro i computer quantici, poiché i problemi matematici a fondamento sono più complessi della fattorizzazione e dei logaritmi discreti sui cui si basano sistemi odierni come la RSA o molte forme di crittografia a curva ellittica.
Infatti un progetto organizzato dal National Institute of Standards and Technology (NIST) atto a definire gli standard crittografici posteriori al mondo dei computer quantistici, ha preso in considerazione proprio tale sistema.
Qualora intendessi approfondire l’argomento, ti rimando ad A guide to fully homomorphic encryption.
Per avere una raccolta di casi d’uso, con applicazioni finanziarie e mediche, puoi invece consultare il documento della Homomorphic Encryption Standardization Consortium.
Potrai infatti trovare le descrizioni, corredate di problemi e attuali limitazioni, per applicare la crittografia omomorfica nel
- Condivisione dati finalizzata alla ricerca medica
- Protezione strutture critiche e di sicurezza nazionale
- Settore educativo, per ridurre il tasso di abbandono scolastico
- Settore medico, per diagnosi puntuali e precise
- Protezione di sistemi di controllo, riducendo il rischio di attacchi hacker a sistemi vitali (e.g. centralina di controllo di un autoveicolo, o attuatore idraulico di sistemi di sicurezza, etc.)
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
