Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

Riepilogo Tecnico: Trasformazione Lineare con Passo-Bambino e Passo-Gigante Triplicamente Sollevata su Crittografia Omomorfica CKKS e Acceleratore Hardware

Enunciato del Problema
La Crittografia Omomorfica (HE), in particolare lo schema CKKS, abilita calcoli che preservano la privacy su dati cifrati, aspetto critico per applicazioni come diagnosi medica, analisi finanziaria e sequenziamento genomico. Un'operazione fondamentale nelle reti neurali e nei transformer basati su HE è la Trasformazione Lineare (HE-LT). Sebbene il metodo diagonale consenta l'HE-LT impacchettando le diagonali della matrice in polinomi, richiede un numero proibitivo di rotazioni dei ciphertext per matrici ad alta dimensionalità. Queste rotazioni coinvolgono operazioni complesse di automorfismo e switching delle chiavi, portando a un significativo sovraccarico computazionale e a un massiccio accesso alla memoria fuori chip. Gli acceleratori hardware esistenti, anche quelli che utilizzano la decomposizione Passo-Bambino e Passo-Gigante (BSGS) e tecniche a doppio sollevamento, soffrono ancora di latenza sostanziale e colli di bottiglia nella larghezza di banda della memoria, richiedendo spesso centinaia di gigabyte di trasferimento dati fuori chip per set di parametri tipici.

Metodologia
Il documento propone una soluzione completa che affronta sia la complessità algoritmica sia il flusso dei dati hardware:

1. Algoritmo BSGS Triplicemente Sollevato (TH-BSGS):
   Gli autori estendono l'esistente algoritmo BSGS a doppio sollevamento decomponendo ulteriormente il "passo-bambino" in due livelli, creando una struttura a tre livelli ($n = n'_1 n'_2 n'_3$).

   • Triplo Sollevamento: La tecnica è applicata attraverso tutti e tre i livelli di rotazioni. Riordinando i calcoli e applicando automorfismi inversi alle chiavi di switching, l'algoritmo garantisce che l'operazione Decompose (un costoso passaggio di switching delle chiavi) venga eseguita una sola volta per tutte le rotazioni interne in un livello.
   • ModDown Ritardato: Similmente ai precedenti metodi di sollevamento, le operazioni ModDown vengono ritardate e combinate. Nel design proposto, ModDown viene applicato solo alle somme accumulate e non ai prodotti intermedi, riducendo significativamente il numero di operazioni modulari richieste.
   • Flessibilità del Trade-off: Sintonizzando i fattori di decomposizione $n'_1, n'_2, n'_3$, l'algoritmo consente trade-off flessibili tra il numero di chiavi di switching richieste (memoria) e la complessità computazionale.

2. Percorso Dati Ottimizzato per la Memoria:
   Per affrontare la latenza causata dall'accesso alla memoria fuori chip, l'algoritmo TH-BSGS è partizionato in sei fasi distinte.

   • Partizionamento delle Fasi: L'algoritmo è ristrutturato in modo che i dati vengano letti dalla memoria fuori chip, elaborati con risultati intermedi memorizzati e riutilizzati on-chip, e riscritti solo alla fine di ogni fase.
   • Riutilizzo dei Dati: Il design massimizza il riutilizzo della memoria on-chip schedulando attentamente il caricamento delle chiavi di switching e dei lembi polinomiali. Ad esempio, nei livelli intermedi, le chiavi di switching vengono caricate nella memoria on-chip e riutilizzate attraverso più iterazioni per minimizzare il traffico.
   • Sintonizzazione del Parallelismo: Vengono introdotti sei parametri di parallelismo ($m_1$ attraverso $m_6$) per bilanciare l'elaborazione delle chiavi di switching, dei lembi polinomiali e dei ciphertext, garantendo che il design rientri nei vincoli della memoria on-chip FPGA (ad esempio, 43 MB su Xilinx U280).

3. Architettura dell'Acceleratore Hardware:
   È stato progettato un efficiente acceleratore basato su FPGA per implementare l'algoritmo proposto.

   • Circuito di Permutazione Ottimizzato: È stato introdotto un nuovo circuito di permutazione per implementare l'automorfismo $\phi_r$. Sfruttando le proprietà specifiche dell'automorfismo nel dominio NTT e l'ordine di memorizzazione a bit invertito dei coefficienti, il design riduce il numero di multiplexer della metà rispetto allo stato dell'arte e elimina la necessità di buffer di memoria scratchpad. Ciò dimezza la latenza dell'operazione di permutazione.
   • Componenti Modulari: L'architettura include una matrice di Elementi di Elaborazione (PE) che supporta NTT, INTT e operazioni coefficiente per coefficiente; una matrice di Addizionatori ad Albero (TA) per le somme; e una matrice di Circuiti di Permutazione (PC).

Contributi Chiave

• Innovazione Algoritmica: La proposta dell'algoritmo BSGS Triplicemente Sollevato, che decomponendo ulteriormente il passo-bambino riduce il numero di rotazioni dei ciphertext e di operazioni Decompose rispetto all'approccio a doppio sollevamento.
• Ottimizzazione del Percorso Dati: Una strategia di ottimizzazione della memoria basata su fasi che riduce drasticamente il traffico di memoria fuori chip massimizzando il riutilizzo dei dati on-chip, specificamente adattata ai calcoli riordinati dell'algoritmo TH-BSGS.
• Efficienza Hardware: Lo sviluppo di un acceleratore hardware dotato di un circuito di permutazione semplificato che riduce la latenza di automorfismo del 50% ed elimina la memorizzazione tampone aggiuntiva.

Risultati Sperimentali
Il design è stato sintetizzato su dispositivi Xilinx Virtex UltraScale+ (U280) e valutato rispetto agli acceleratori hardware più avanzati (inclusi FAME, CHAM e design da [25]) sotto tre diversi set di parametri HE (Set-A, Set-B, Set-C) che supportano una sicurezza a 128 bit.

• Accesso alla Memoria Fuori Chip: Il design proposto riduce l'accesso alla memoria fuori chip di 2,9× fino a 4,2× rispetto al miglior design precedente (FAME) nelle stesse impostazioni dei parametri. Rispetto al metodo diagonale, i miglioramenti raggiungono fino a 10,6× nella riduzione dell'accesso alla memoria.
• Latenza Computazionale: L'acceleratore proposto ottiene una riduzione della latenza computazionale da 2,9× a 10,6× rispetto ai precedenti acceleratori hardware.
• Utilizzo delle Risorse: Il design mantiene requisiti di risorse hardware (LUT, FF, DSP, BRAM) comparabili o leggermente migliori rispetto alle soluzioni esistenti, nonostante i significativi guadagni prestazionali.
• Confronto Algoritmico: Sebbene l'algoritmo TH-BSGS riduca il requisito di memoria per le chiavi di switching di circa 3,65× rispetto all'algoritmo BSGS a doppio sollevamento (DH-BSGS), la complessità computazionale complessiva rimane simile a quella di DH-BSGS e BSGS, poiché le moltiplicazioni polinomiali dominano la complessità totale.

Significato
Il documento afferma che l'algoritmo TH-BSGS proposto e il relativo acceleratore hardware rappresentano un avanzamento significativo nell'efficienza dell'HE-LT. Affrontando simultaneamente il sovraccarico algoritmico dello switching delle chiavi e il collo di bottiglia hardware dell'accesso alla memoria fuori chip, il design abilita trasformazioni lineari che preservano la privacy più rapide e scalabili. La riduzione del traffico di memoria fuori chip è particolarmente critica, poiché i trasferimenti di dati costituiscono la maggior parte della latenza nelle operazioni HE-LT. Il lavoro dimostra che un'ulteriore decomposizione del passo-bambino, combinata con un'ottimizzazione rigorosa del percorso dati e hardware specializzato, può produrre miglioramenti prestazionali sostanziali senza aumentare i costi delle risorse hardware. Si nota che il lavoro futuro si concentrerà sull'ulteriore ottimizzazione delle trasformazioni lineari per applicazioni specifiche.