Schemi BGV e BFV per operazioni su interi

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) è uno schema FHE a livelli basato su RLWE. Supporta somme e moltiplicazioni arbitrarie su testi in chiaro interi impacchettati. «A livelli» significa che gestisce circuiti fino a una profondità fissa L senza bootstrapping.

BGV e BFV codificano i testi in chiaro come polinomi in Z_t[x]/(x^n+1), dove t è un piccolo modulo del testo in chiaro (ad esempio, t=65537). Ogni polinomio codifica n valori interi, uno per coefficiente. Le operazioni sui testi cifrati vengono eseguite simultaneamente su tutti gli n valori: parallelismo SIMD.

BGV riduce il rumore tramite il cambio di modulo: dopo ogni moltiplicazione, il modulo del testo cifrato q viene ridotto da Q_L a Q_{L-1}. In questo modo il rumore viene diviso per Q_L/Q_{L-1}, mantenendolo entro i limiti che consentono la decifratura. La profondità del circuito L corrisponde a L livelli di modulo.

BFV (Brakerski/Fan-Vercauteren, 2012) è simile a BGV, ma utilizza una strategia diversa per la gestione del rumore: l'invarianza della scala. BFV non richiede il cambio di modulo; invece, ridimensiona il testo cifrato dopo la moltiplicazione. È più semplice da implementare ed è utilizzato in Microsoft SEAL.

Tramite il teorema cinese del resto applicato all'anello dei testi in chiaro, ogni testo cifrato può contenere n/2 valori interi indipendenti (slot). Un'operazione di addizione sui testi cifrati somma in parallelo tutte le n/2 coppie. Una moltiplicazione moltiplica tutte le coppie. Velocità: n/2 operazioni su interi per ogni operazione sui testi cifrati.

Dopo aver moltiplicato due testi cifrati di grado 1, il risultato ha grado 2 (3 componenti). La relinearizzazione utilizza chiavi di valutazione (chiavi relin) per tornare al grado 1 al costo di rumore aggiuntivo. Questo passaggio è richiesto dopo ogni moltiplicazione.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

La rotazione del testo cifrato sposta ciclicamente gli n/2 slot del testo in chiaro. È utile per: riduzione tramite somma (accumulare tutti gli slot in uno), moltiplicazione matrice-vettore (ruotare e accumulare), convoluzioni (spostare e moltiplicare). Richiede chiavi di Galois (chiavi di rotazione precalcolate).

BFV con n=8192: addizione ~10 µs, moltiplicazione ~5 ms (con relinearizzazione). Bootstrapping, se necessario: 30-60 secondi. Batch di 4096 interi: circa ~1 µs per intero per moltiplicazione, in termini ammortizzati. Non è pratico per il tempo reale, ma è utilizzabile per l'analisi offline.

Scelta di n e q: SEAL raccomanda n=4096 per una sicurezza di 128 bit con Q < 2^109; n=8192 per circuiti più grandi. Lo standard HE (homomorphicencryption.org) fornisce tabelle dei parametri. Utilizzi sempre i parametri raccomandati: scelte personalizzate possono compromettere facilmente la sicurezza.

Query su database cifrati (cercare record cifrati senza decifrarli). Analisi genomica privata (calcolare statistiche su DNA cifrato). Aggregazioni finanziarie cifrate (sommare i saldi dei conti cifrati senza vedere i singoli individui). Valutazione sicura dei modelli.

Quale tecnica utilizza BGV per gestire la crescita del rumore dopo le moltiplicazioni?

BGV e BFV eseguono operazioni aritmetiche cifrate su interi utilizzando RLWE. La codifica batch fornisce parallelismo SIMD. BGV utilizza il cambio di modulo; BFV utilizza l'invarianza della scala. La relinearizzazione ripristina il grado dopo la moltiplicazione. Prossimo argomento: CKKS per l'aritmetica approssimata e il machine learning.