Hardware-Friendly Randomization: Enabling Random-Access and Minimal Wiring in FHE Accelerators with Low Total Cost

Titolo: Randomizzazione Hardware-Friendly: Abilitazione dell'Accesso Casuale e del Cablaggio Minimo negli Acceleratori FHE con Basso Costo Totale

1. Il Problema

L'articolo affronta le sfide ingegneristiche critiche nell'implementazione hardware di acceleratori ASIC per la Crittografia Omomorfica Completa (FHE), basata sul problema RLWE (Ring-Learning With Errors).

• Overhead di Comunicazione: I cifrari RLWE e le chiavi di switching (Key-Switching Keys) contengono polinomi uniformemente casuali ($\mathbf{a}$) che possono raggiungere dimensioni enormi (es. 130 MB per le chiavi, GB per applicazioni complesse). Trasmettere questi dati dal client al server crea un collo di bottiglia significativo.
• Generazione On-the-Fly: Per ridurre l'overhead, si utilizza una tecnica nota in cui il client invia solo un "seed" piccolo e l'acceleratore rigenera i polinomi $\mathbf{a}$ in tempo reale tramite un PRNG (Pseudo-Random Number Generator).
• Sfide Hardware:
  • Cablaggio e Potenza: Gli acceleratori FHE possiedono migliaia di unità di calcolo parallele. Generare i dati casuali in un'unica unità centrale e distribuirli a tutte le unità di calcolo richiede un cablaggio globale massiccio, costoso in termini di energia e di utilizzo degli strati metallici spessi (thick metal layers).
  • Dipendenza Seriale: Gli algoritmi di hashing standard (XOF come SHAKE128 o BLAKE2) sono seriali. Per generare l'$k$-esimo campione, è necessario calcolare tutti i precedenti ($0$a$k-1$). Questo limita la flessibilità di scheduling e impedisce l'accesso casuale (random-access) ai "limbs" (i componenti RNS) dei polinomi senza memorizzare risultati intermedi.
  • Non Determinismo: Le tecniche di rejection sampling introducono incertezza sul numero di bit necessari per generare campioni validi, complicando lo scheduling statico richiesto dagli acceleratori hardware.

2. Metodologia

Gli autori propongono uno schema di generazione distribuita e randomizzabile che risolve i problemi di cablaggio e scheduling mantenendo la sicurezza e l'efficienza.

• Generazione Distribuita (Distributed PRNG):

  • Invece di un'unica unità centrale, il polinomio viene suddiviso in segmenti indipendenti.
  • Ogni gruppo di risorse di calcolo ha un proprio motore PRNG locale.
  • L'input per la funzione hash è "domain-separated" (separato per dominio) utilizzando tre componenti: il seed comune, l'indice del modulo RNS ($q$) e l'indice del segmento ($id_{seg}$).
  • Questo permette a ogni motore locale di generare i propri campioni senza dover comunicare con un centro, eliminando il traffico di dati a lunga distanza.

• Accesso Casuale (Random-Access):

  • Grazie alla separazione dei domini basata sul modulo e sull'indice del segmento, l'acceleratore può generare direttamente qualsiasi "limb" RNS specifico richiesto dal calcolo, senza dover generare sequenzialmente i precedenti.
  • Questo elimina la necessità di memorizzare grandi quantità di dati intermedi in memoria o registri.

• Scheduling Deterministico e Rejection Sampling Ottimizzato:

  • Viene proposto un algoritmo (Algoritmo 2) che genera un segmento di valori accettati con una probabilità di fallimento controllata.
  • Il client valida i parametri (seed, moduli, lunghezza del segmento) per garantire che la probabilità di fallimento nella generazione dell'intero polinomio multi-residuo (MRP) sia inferiore a una soglia (es. 3%).
  • Se il client fallisce, riprova con un nuovo seed; il server, invece, riceve sempre parametri garantiti per il successo, assicurando un'esecuzione deterministica senza stalli.

• Supporto per Moduli Limitati:

  • Lo schema limita l'insieme dei moduli primi supportati a quelli con caratteristiche specifiche (es. basso peso di Hamming nella forma NAF) per ottimizzare l'hardware di riduzione modulare, bilanciando la flessibilità con l'efficienza dell'area e della potenza.

3. Contributi Chiave

1. Riduzione Drastica del Cablaggio: Spostando la generazione dei dati casuali vicino alle unità di calcolo, si eliminano le lunghe linee di trasmissione globale. Questo riduce il consumo energetico del cablaggio e la necessità di strati metallici spessi.
2. Accesso Casuale ai Limbs RNS: Per la prima volta in questo contesto, si permette l'accesso diretto a specifici componenti del polinomio senza dipendenze seriali, abilitando uno scheduling più flessibile ed efficiente.
3. Scheduling Deterministico: Risolvendo il problema della non-deterministica del rejection sampling tramite validazione lato client, si garantisce che l'acceleratore non subisca stalli o ritardi imprevisti durante l'esecuzione.
4. Basso Overhead Client: Il costo computazionale aggiuntivo per il client (dovuto al possibile riprovare la generazione se i parametri non sono ottimali) è minimo (< 3%).
5. Efficienza Energetica: Lo studio stima che per un acceleratore tipico (15mm x 15mm, 16k moltiplicatori), l'approccio centralizzato consumerebbe circa 19.7 Watt solo per il cablaggio dei dati casuali. L'approccio distribuito elimina quasi completamente questo consumo.

4. Risultati

• Analisi dei Parametri: Gli autori hanno identificato parametri pratici (es. dimensione del seed di 288 bit, dimensione della parola di 32 bit, uso di SHAKE128/KangarooTwelve) che permettono di supportare basi RNS sufficienti per la sicurezza a 128 bit (con $N=2^{16}$).
• Probabilità di Fallimento: Con una lunghezza di segmento ($len$) di 32, la probabilità di rifiuto per campione ($p_r$) è molto bassa per moduli fino a 27 bit, mantenendo la probabilità totale di fallimento della generazione MRP sotto il 3%.
• Risparmio Energetico: L'eliminazione del cablaggio globale per la distribuzione della casualità porta a un risparmio di potenza significativo (decine di Watt per chip in configurazioni ad alto throughput) e riduce la densità di potenza richiesta.
• Flessibilità: Il sistema supporta la generazione parallela di campioni uniformemente distribuiti e permette di saltare direttamente ai limb necessari per operazioni come lo switching delle chiavi.

5. Significato

Questo lavoro rappresenta un passo avanti cruciale verso l'adozione pratica e su larga scala degli acceleratori FHE.

• Scalabilità: Man mano che le applicazioni FHE diventano più complesse e richiedono acceleratori con più risorse parallele, i problemi di cablaggio e distribuzione dei dati diventano il collo di bottiglia principale. Questa soluzione rende scalabile l'architettura hardware senza penalizzare eccessivamente la potenza o l'area.
• Ecosistema FHE: L'adozione di questo schema (o dei suoi principi) da parte di fornitori di hardware e librerie FHE permetterebbe di eseguire applicazioni crittografate su larga scala con un overhead energetico e hardware molto ridotto.
• Ottimizzazione Hardware-Software: Dimostra come una stretta collaborazione tra la progettazione degli algoritmi crittografici (scelta dei moduli, gestione del seed) e l'architettura hardware (distribuzione PRNG, scheduling) possa risolvere problemi ingegneristici fondamentali che altrimenti limiterebbero le prestazioni.

In sintesi, il paper propone una soluzione elegante che trasforma un vincolo di comunicazione e cablaggio in un'opportunità di ottimizzazione distribuita, rendendo gli acceleratori FHE più veloci, meno costosi in termini energetici e più flessibili nello scheduling.