💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

Questo articolo introduce Sparse Roots of Unity (SPRU), un nuovo algoritmo di bootstrapping per lo schema di crittografia omomorfica CKKS che incorpora l'aritmetica modulare nelle radici dell'unità complesse per ridurre significativamente la profondità moltiplicativa e ottenere un miglioramento della latenza fino a 5 volte rispetto ai metodi tradizionali.

Autori originali: Jean-Sebastien Coron, Robin Koestler

Pubblicato 2026-07-31

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Jean-Sebastien Coron, Robin Koestler

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di voler inviare un messaggio segreto a un amico, ma di non poterti fidare dell'ufficio postale. Chiudi la tua lettera in una scatola, ma l'ufficio postale deve smistarla, impilarla e magari anche aprirla per controllare l'indirizzo senza mai vedere cosa c'è dentro. Questa è la magia della Crittografia Completamente Omomorfa (FHE). Permette ai computer di eseguire calcoli su dati che sono ancora sotto forma criptata. Immaginala come una cucina magica dove puoi preparare una torta usando ingredienti che sono ancora nelle loro confezioni sigillate e chiuse; il forno fa il lavoro, e quando finalmente apri la scatola alla fine, hai una torta fresca, ma il forno non ha mai saputo quali fossero gli ingredienti.

Tuttavia, c'è un problema. Ogni volta che il computer esegue un'operazione matematica su questi dati criptati, un po' di "rumore" o disturbo viene aggiunto alla scatola, come della polvere che si deposita su una lente. Se fai troppi calcoli, il rumore diventa così forte che il messaggio diventa confuso e illeggibile. Per risolvere questo problema, gli scienziati usano un processo chiamato bootstrapping. È come un pulsante di reset magico: il computer prende la scatola rumorosa e chiusa, esegue un trucco complesso per pulire la polvere e ripone il messaggio in una scatola nuova e pulita, in modo che i calcoli possano continuare. Il problema è che questo trucco di pulizia è incredibilmente lento e pesante, come cercare di lavare un'auto con uno spazzolino da denti. Richiede così tanta potenza di calcolo che rallenta tutto, facendo sembrare le applicazioni del mondo reale molto pigre.

È qui che entra in gioco un nuovo articolo di Jean-Sébastien Coron e Robin Köstler. Introducono un nuovo modo intelligente per eseguire questo processo di "pulizia", chiamato bootstrapping a Radici dell'Unità Sparse (SPRU). Invece del vecchio metodo pesante che cerca di approssimare una curva complessa (come un'onda sinusoidale) per pulire i dati, hanno trovato un modo per mappare i dati direttamente su un cerchio di numeri chiamati "radici dell'unità". Immagina invece di dover strofinare l'auto con uno spazzolino da denti, di far scivolare l'auto su una grande giostra rotante che pulisce naturalmente la polvere mentre gira. Il loro metodo è molto più veloce e leggero, specialmente quando si gestisce un piccolo numero di elementi di dati alla volta. Usando questo nuovo approccio, hanno dimostrato che il tempo necessario per resettare la crittografia può essere ridotto fino a 5 volte rispetto al metodo standard, rendendo la magia del calcolo segreto molto più simile a una realtà che a un sogno lontano.

Il Vecchio Modo: Il Grande Sforzo

Per capire perché questo nuovo trucco è così speciale, guardiamo come funzionava il vecchio metodo. Nello schema di crittografia CKKS standard (il più popolare per fare calcoli su numeri decimali), il processo di bootstrapping era come cercare di indovinare la forma di una montagna disegnando una linea morbida sopra di essa. Il computer doveva valutare un polinomio complicato (una formula matematica sofisticata) che approssimava una "riduzione modulare". Pensa alla riduzione modulare come a un modo per avvolgere una lunga linea numerica in un cerchio in modo che rientri in una piccola scatola. Il vecchio metodo cercava di disegnare un'onda sinusoidale (una linea ondulata) per imitare questo processo di avvolgimento.

Sebbene questo funzionasse, era uno sforzo enorme. Richiedeva una profonda pila di operazioni matematiche, il che significava che il computer doveva usare una "dimensione dell'anello" molto grande (una misura del parco giochi matematico). Era come cercare di correre una maratona portando uno zaino pesante; questo rallentava tutto e limitava quanto lavoro utile potesse essere svolto dopo il reset. Gli autori sottolineano che questa alta "profondità moltiplicativa" (il numero di strati di matematica che devi attraversare) era il collo di bottiglia principale, rendendo il processo troppo lento per un uso pratico, specialmente quando dovevi elaborare solo pochi numeri alla volta.

Il Nuovo Modo: La Giostra delle Radici

La nuova idea degli autori, il bootstrapping SPRU, cambia le regole del gioco saltando l'intera approssimazione pesante. Invece di cercare di disegnare una linea ondulata per imitare l'avvolgimento, hanno capito che potevano semplicemente incorporare i dati direttamente nelle "radici dell'unità".

Ecco un'analogia semplice: immagina che il vecchio metodo fosse come cercare di tradurre un codice segreto scrivendo una voce di dizionario lunga e complicata per ogni singola lettera. Ci voleva una eternità. Il nuovo metodo è come rendersi conto che il codice segreto è in realtà un insieme di chiavi che si adattano perfettamente a una specifica serratura. Invece di tradurre, giri la chiave.

In termini tecnici, mappano il gruppo additivo (il modo in cui i numeri si sommano) direttamente nelle radici dell'unità complessa (punti su un cerchio nel sistema numerico complesso). Poiché lo schema di crittografia CKKS comprende nativamente questi numeri complessi, il computer può eseguire l'operazione di "pulizia" direttamente, senza dover approssimare un'onda sinusoidale. È come passare dal costruire un ponte con singoli mattoni all'uso di un arco prefabbricato che si adatta perfettamente.

La Ricetta Segreta: Sparsità e Impacchettamento

L'articolo non si ferma alla nuova mappa; hanno anche introdotto due ottimizzazioni intelligenti per renderlo ancora più veloce, specialmente quando si gestisce un piccolo numero di slot di dati (come una breve lista di numeri).

Impacchettare i Bit: Nei vecchi tempi, se avevi una chiave segreta di 1.000 bit, il computer doveva gestire ogni bit uno alla volta. Gli autori hanno capito che potevano "impacchettare" questi bit negli slot della crittografia, come infilare 1.000 lettere in una singola cassetta delle lettere super efficiente. Questo ha ridotto il numero di calcoli pesanti necessari da una quantità massiccia a una quantità logaritmica (pensa a ridurre una lunga lista in un breve riassunto).
Il Trucco del Blocco Sparso: Hanno anche ipotizzato che la chiave segreta avesse una struttura speciale: invece di bit casuali, la chiave era divisa in blocchi dove solo un bit in ogni blocco era un "1" e gli altri erano "0". È come avere una fila di interruttori della luce dove solo uno è acceso in ogni gruppo di dieci. Usando questa struttura "sparsa", hanno potuto sostituire molti passaggi di moltiplicazione difficili con semplici passaggi di addizione. È la differenza tra moltiplicare una lunga lista di numeri e il semplice sommare pochi di essi. Questo ha ridotto ulteriormente la "profondità" del calcolo, trasformando una torre alta in una piccola scala.

I Risultati: Accelerare la Magia

Gli autori hanno testato il loro nuovo metodo utilizzando la libreria OpenFHE, uno strumento popolare per costruire software di crittografia. Hanno confrontato il loro bootstrapping SPRU con il metodo originale, più pesante.

I risultati sono stati sorprendenti per scenari specifici. Quando si effettuava il bootstrapping di ciphertext con un numero ridotto di slot (cosa comune in molte applicazioni del mondo reale), il loro nuovo metodo era fino a 5 volte più veloce (una riduzione della latenza di 5x). Questo è un grande passo avanti perché significa che il "pulsante di reset" non deve aspettare così tanto, permettendo al computer di tornare a fare lavoro utile molto più velocemente.

Tuttavia, l'articolo nota con cautela che questo non è un rimedio magico per ogni situazione. Se stai cercando di elaborare un numero enorme di slot (una lista di dati gigantesca), il metodo originale potrebbe essere ancora più efficiente. Ma per i molti casi in cui gestiamo piccoli lotti di dati, questo nuovo approccio offre un aumento di velocità significativo.

Perché è Importante

La bellezza di questo lavoro è che non si limita a ritoccare i numeri; cambia fondamentalmente il modo in cui pensiamo al processo di bootstrapping. Allontanandosi dalle pesanti approssimazioni polinomiali e abbracciando le capacità native dello schema di crittografia, gli autori hanno dimostrato che possiamo rendere la crittografia completamente omomorfa molto più pratica.

Hanno provato che usando queste "radici dell'unità" e tecniche di impacchettamento intelligente, possiamo ridurre significativamente il tempo e la potenza di calcolo necessari per mantenere i dati criptati utilizzabili. Sebbene l'articolo si concentri sui dettagli tecnici e sulla matematica dietro le quinte, il messaggio è chiaro: l'idea di eseguire calcoli complessi su dati segreti senza rallentare è diventata molto più vicina alla realtà. Gli autori hanno fornito un modo nuovo, più leggero e veloce per mantenere viva la magia, rendendo possibile immaginare un futuro in cui i tuoi dati privati possono essere elaborati nel cloud senza mai essere visti, e senza dover aspettare un'eternità per il risultato.

Sintesi Tecnica: Bootstrapping a Bassa Latenza per CKKS utilizzando le Radici dell'Unità

Definizione del Problema

Lo schema di crittografia omomorfica CKKS supporta l'aritmetica approssimativa su numeri complessi, rendendolo adatto al machine learning sicuro e al cloud computing. Tuttavia, un collo di bottiglia critico in CKKS è la procedura di bootstrapping, necessaria per aggiornare i ciphertext e abilitare una profondità di computazione illimitata.

Il metodo originale di bootstrapping per CKKS [CHK+18a] si basa sulla valutazione omomorfica di un'approssimazione polinomiale della funzione di riduzione modulare (specificamente, una funzione seno scalata). Questo approccio soffre di due svantaggi principali:

Alta Profondità Moltiplicativa: L'approssimazione polinomiale richiede un circuito profondo, rendendo necessario un modulo del ciphertext elevato.
Inefficienza per Piccoli Conteggi di Slot: La complessità del metodo originale scala con il numero di slot ( $n$ ) e la dimensione dell'anello ( $N$ ), richiedendo spesso $O(\log n + \log N)$ operazioni. Questa elevata profondità impone l'uso di dimensioni dell'anello maggiori per mantenere la sicurezza, aumentando di conseguenza la latenza.

Gli autori identificano la necessità di un algoritmo di bootstrapping che riduca la profondità moltiplicativa, permettendo così dimensioni dell'anello più piccole e una latenza significativamente inferiore, particolarmente per i ciphertext con un numero ridotto di slot.

Metodologia: Sparse Roots of Unity (SPRU)

Il documento introduce il bootstrapping Sparse Roots of Unity (SPRU), un nuovo algoritmo che cambia fondamentalmente il modo in cui viene eseguita la riduzione modulare in CKKS.

Concetto Core: Embedding Nativo

Inveve di approssimare la riduzione modulare tramite una funzione seno, il bootstrapping SPRU incorpora direttamente il gruppo additivo $\mathbb{Z}_q$ nel gruppo moltiplicativo delle radici dell'unità complesse. Gli autori utilizzano l'omomorfismo:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

Per un'equazione di decrittazione di tipo LWE $m = \langle s, c \rangle \pmod q$ , gli autori osservano che:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Poiché i bit della chiave segreta $s_k \in \{0, 1\}$ agiscono come selettori, questo prodotto può essere riscritto come:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
Isolando la parte immaginaria e applicando un fattore di scala lineare, il messaggio originale $m$ può essere recuperato. Questa equazione può essere valutata omomorficamente all'interno dello schema CKKS senza l'approssimazione polinomiale della funzione seno.

Ottimizzazioni Chiave

Per rendere pratico questo approccio, gli autori introducono due ottimizzazioni critiche:

Packing dei Bit della Chiave Segreta:
Invece di crittografare individualmente ogni bit della chiave segreta, i $N$ bit sono impacchettati nei $N/2$ slot di due ciphertext CKKS. Anche i termini $(\exp(2i\pi \cdot c_k/q) - 1)$ sono similmente impacchettati. Il prodotto di questi termini viene calcolato utilizzando l'Operatore di Prodotto ( $Pr_{N/2 \to 1}$ ), che riduce il numero di moltiplicazioni omomorfiche da $O(N)$ a $O(\log N)$ .
Sparse Block Secret Key:
Gli autori assumono una chiave segreta strutturata $s$ divisa in $h$ blocchi di dimensione $B = N/h$ , dove ogni blocco contiene esattamente un bit non nullo (un '1'). Questa struttura permette di sostituire il prodotto all'interno di ogni blocco con una somma.
- La somma all'interno dei blocchi è calcolata tramite l'Operatore di Traccia ( $Tr_{N/2 \to h}$ ), che coinvolge solo addizioni e automorfismi (senza profondità moltiplicativa).
- Il prodotto finale viene calcolato sui risultati dei blocchi $h$ .
- Risultato: La profondità moltiplicativa è ridotta da $\log_2 N + 2$ a $\log_2 h + 1$ . Poiché $h \ll N$ , ciò abbassa significativamente la dimensione del modulo richiesta.

Estensione a Molteplici Slot

Il metodo è generalizzato per gestire $n$ slot (dove $n \le N/2$ ). La matrice di decrittazione viene estratta e l'equazione di bootstrapping viene applicata in parallelo a ciascuna delle $n$ componenti del messaggio. La complessità è $O(n + \log N)$ , che è asintoticamente superiore al bootstrapping originale di CKKS ( $O(\log n + \log N)$ ). Tuttavia, per piccoli valori di $n$ , la ridotta profondità moltiplicativa garantisce prestazioni pratiche superiori.

Contributi Chiave

Algoritmo di Bootstrapping SPRU: Una nuova tecnica di bootstrapping per CKKS che sostituisce l'approssimazione della funzione seno con la valutazione nativa delle radici dell'unità.
Riduzione della Profondità Moltiplicativa: Sfruttando le chiavi segrete a blocchi sparsi e l'operatore di traccia, l'algoritmo raggiunge una profondità moltiplicativa di $O(\log h)$ , significativamente inferiore rispetto all' $O(\log N)$ del metodo originale.
Implementazione Ottimizzata: Gli autori forniscono un'implementazione open-source utilizzando la libreria C++ OpenFHE, dimostrando la compatibilità con l'aritmetica Residue Number System (RNS) e le ottimizzazioni esistenti delle trasformazioni lineari (SlotToCoeff).
Analisi della Sicurezza: Un'analisi formale della distribuzione della chiave binaria a blocchi, che mostra come questa non indebolisca la sicurezza del problema RLWE contro attacchi noti (attacchi ibridi dual e meet-in-the-middle), a condizione che i parametri siano regolati correttamente.

Risultati

Gli autori hanno confrontato il bootstrapping SPRU con il bootstrapping originale di CKKS utilizzando la libreria OpenFHE con parametri di sicurezza a 128 bit.

Riduzione della Latenza: Per i ciphertext con un piccolo numero di slot, il bootstrapping SPRU ottiene una riduzione della latenza fino a 5 volte.
Efficienza: La riduzione della profondità moltiplicativa permette l'uso di dimensioni dell'anello più piccole, contribuendo ulteriormente all'accelerazione.
Parallelismo: Il metodo è altamente parallelizzabile; con $n$ processori, può raggiungere una complessità $O(\log N)$ comparabile al metodo originale.

Significato e Rivendicazioni

Il documento sostiene che il bootstrapping SPRU offre un'alternativa pratica al bootstrapping originale di CKKS, mirando specificamente a scenari in cui la bassa latenza è critica e il numero di slot è ridotto. Evitando costose approssimazioni polinomiali e riducendo la profondità moltiplicativa, il metodo consente un aggiornamento dei ciphertext più efficiente.

Gli autori pongono il loro lavoro come un passo significativo verso la rendere l'omomorfismo completo più pratico per applicazioni reali che richiedono un bootstrapping frequente. Notano che, mentre il loro metodo è ottimizzato per piccoli conteggi di slot, esso integra il lavoro esistente (come il lavoro indipendente di Cheon et al. [CHKS25] focalizzato sul bootstrapping completo per $N/2$ slot) offrendo un diverso compromesso che privilegia la latenza rispetto al massic massiccio parallelismo per set di dati piccoli.

Il documento conclude che la ridotta profondità moltiplicativa è il principale motore dell'efficienza, liberando più livelli computazionali per operazioni utili dopo il bootstrapping e permettendo l'uso di dimensioni dell'anello più piccole e veloci.