Che cos'è la cifratura omomorfica?

La crittografia omomorfica (HE) consente di eseguire calcoli direttamente su dati cifrati, producendo un risultato cifrato che, una volta decifrato, coincide con il risultato delle stesse operazioni eseguite sul testo in chiaro. «Eseguire calcoli sul ciphertext senza decrittarlo.»

Immagini di mettere dei numeri dentro una scatola chiusa a chiave, con speciali guanti integrati nei lati. Può manipolare i numeri attraverso i guanti (sommarli, moltiplicarli) senza mai aprire la scatola. Solo il proprietario della chiave può vedere il risultato quando la apre.

La crittografia parzialmente omomorfica supporta illimitatamente un solo tipo di operazione: RSA (textbook) è omomorfica rispetto alla moltiplicazione: Enc(m1)*Enc(m2) = Enc(m1*m2). Paillier è omomorfica rispetto all'addizione: Enc(m1)*Enc(m2) = Enc(m1+m2). Utilizzata nell'e-voting e nel private information retrieval.

La crittografia somewhat homomorphic supporta sia l'addizione sia la moltiplicazione, ma solo per un numero limitato di moltiplicazioni (profondità del circuito). Il rumore cresce a ogni moltiplicazione; dopo una certa soglia, la decifratura fallisce. Prima costruzione realizzata da Gentry (2009).

La crittografia completamente omomorfica supporta calcoli arbitrari (qualsiasi circuito booleano/aritmetico) su dati cifrati. Gentry (2009) ha dimostrato che la FHE è possibile tramite il «bootstrapping», cioè valutando omomorficamente il circuito di decifratura per aggiornare il ciphertext e azzerare il rumore.

La maggior parte degli schemi HE si basa su reticoli (BGV, BFV, CKKS). La cifratura aggiunge rumore al testo cifrato. Addizione: il rumore cresce in modo additivo. Moltiplicazione: il rumore cresce in modo moltiplicativo. Bootstrapping: decifra omomorficamente il testo cifrato, riportando il rumore al livello iniziale. Il bootstrapping è costoso.

La FHE è ancora 10^6 volte più lenta dei calcoli su testo in chiaro. Cifrare un intero a 32 bit richiede kilobyte di testo cifrato. Il bootstrapping richiede secondi per ogni porta. La FHE pratica si rivolge a carichi di lavoro specifici: inferenza di machine learning, query su database, analisi del genoma.

La maggior parte degli schemi HE si basa sul problema computazionalmente difficile Learning With Errors (LWE) o Ring-LWE (RLWE), ritenuto resistente ai computer quantistici. Per violare la HE è necessario risolvere RLWE: non esiste alcun algoritmo quantistico noto che offra un'accelerazione significativa per risolverlo.

SEAL (Microsoft, supporta BFV/CKKS), HEAAN (Seoul National University, CKKS), OpenFHE (open source, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). Tutte sono di livello di ricerca; le implementazioni in produzione sono rare e specifiche del dominio.

Genomica medica: interrogare un database genetico senza rivelare il proprio genoma. Inferenza ML cifrata: il cloud esegue una rete neurale sui propri dati senza poterli vedere. Analisi private: aggregare statistiche su dati cifrati degli utenti. Calcolo del rischio finanziario su portafogli riservati.

HE: una singola parte esegue calcoli su dati cifrati da un'altra parte. MPC: più parti eseguono calcoli congiuntamente senza rivelarsi reciprocamente i propri input. Ibrido: utilizzare HE per la preelaborazione offline e MPC per i protocolli interattivi. Compromessi: HE = latenza elevata; MPC = overhead di comunicazione.

Qual è il limite principale della Somewhat Homomorphic Encryption (SHE)?

La Homomorphic Encryption consente di eseguire calcoli sul testo cifrato. La PHE supporta una sola operazione; la SHE supporta una profondità limitata; la FHE supporta circuiti arbitrari tramite bootstrapping. Si basa sui problemi difficili LWE/RLWE. Prossimo argomento: i fondamenti matematici di LWE.