💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Questo documento propone un metodo ottimizzato di moltiplicazione di cifrati a multipli ingressi per la Crittografia Omomorfica che estende il supporto oltre due ingressi attraverso computazioni riformulate, chiavi di valutazione aggiuntive e un approccio di ridimensionamento multilivello, risultando in architetture hardware che riducono significativamente l'area logica e la latenza rispetto a progetti precedenti.

Autori originali: Sajjad Akherati, Xinmiao Zhang

Pubblicato 2026-05-19

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Sajjad Akherati, Xinmiao Zhang

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 essere uno chef esperto che cerca di preparare una torta, ma c'è un ostacolo: devi fare tutto l'impasto e la cottura indossando guanti da forno spessi e pesanti che ti impediscono di sentire gli ingredienti o di vedere la ciotola. Questo è la Crittografia Omomorfica (HE). Consente ai computer di eseguire calcoli matematici su dati "crittografati" (l'impasto della torta nei guanti) senza mai decifrarli (togliere i guanti). Questo mantiene al sicuro i segreti, siano essi i tuoi cartelle cliniche o il tuo saldo bancario.

Tuttavia, fare calcoli con questi "guanti" è incredibilmente lento e disordinato. Il collo di bottiglia più grande è la moltiplicazione. Nella crittografia standard, puoi moltiplicare solo due ingredienti alla volta. Ma molti compiti moderni, come addestrare un'intelligenza artificiale a riconoscere una malattia o analizzare tendenze finanziarie complesse, richiedono di moltiplicare molti ingredienti (testi cifrati) insieme contemporaneamente.

Questo articolo introduce un nuovo metodo super-efficiente per moltiplicare questi ingredienti crittografati, specificamente per un metodo di crittografia popolare chiamato CKKS. Ecco la spiegazione della loro svolta utilizzando semplici analogie:

1. Il Problema: La "Cucina Disordinata"

Quando moltiplichi numeri crittografati, il "rumore" (il disordine creato dai guanti da forno) diventa sempre più forte. Se moltiplichi troppi numeri contemporaneamente senza fare pulizia, il rumore copre i dati reali e il risultato diventa inutilizzabile.

Per risolvere questo problema, il sistema di crittografia deve eseguire un passaggio di "pulizia" chiamato Ricalibrazione (Rescaling) dopo ogni moltiplicazione. Pensa a questo come fermarsi per pulire il piano di lavoro e rimettere in ordine gli ingredienti.

Il Vecchio Metodo: Se dovevi moltiplicare 10 ingredienti, il vecchio metodo era come un nastro trasportatore dove moltiplicavi due, ti fermavi per pulire, moltiplicavi altri due, ti fermavi per pulire, e così via. Era lento e richiedeva molti prodotti per la pulizia (risorse hardware).
Il Precedente Tentativo "a Tre Ingredienti": Il lavoro precedente degli autori mostrava che potevi moltiplicare tre ingredienti alla volta, il che era più veloce. Ma aveva ancora molti passaggi di pulizia non necessari.

2. La Soluzione: La "Linea di Assemblaggio Intelligente"

Gli autori propongono due importanti aggiornamenti per rendere questo processo più veloce e più compatto:

A. La "Pulizia in Un Passaggio" (Miglioramento della Moltiplicazione a 3 Input)

Nel loro nuovo design per moltiplicare tre ingredienti, hanno realizzato che stavano eseguendo la pulizia (Ricalibrazione) e il riordinamento (Rilinearizzazione) in modo goffo e indiretto.

L'Analogia: Immagina di avere tre ciotole di impasto. Il vecchio metodo consisteva nel mescolarli, versare il composto in una nuova ciotola, pulire le vecchie ciotole, versare di nuovo il composto e pulire ancora.
La Soluzione: Hanno ridisegnato il processo in modo da poter mescolare e pulire in un unico movimento fluido. Hanno capito come combinare i passaggi di pulizia in modo da non dover fermarsi e pulire il piano di lavoro tante volte.
Il Risultato: Il loro nuovo "mescolatore a tre ciotole" è 50% più veloce (latenza) e occupa il 15% in meno di spazio sul chip (area) rispetto al loro precedente miglior design.

B. La "Pulizia di Gruppo" (Moltiplicazione Multi-Input)

Cosa succede se devi moltiplicare quattro, cinque o addirittura dodici ingredienti alla volta?

Il Vecchio Metodo: Costruivi una lunga fila di "mescolatori a due ciotole". Mescolavi due, pulivi, mescolavi altri due, pulivi, poi mescolavi i risultati, pulivi di nuovo. Questo creava una fila molto lunga (alta "profondità moltiplicativa"), il che significava che il rumore si accumulava troppo velocemente.
La Nuova Strategia: Gli autori hanno realizzato che se raggruppi gli ingredienti in modo diverso, puoi eseguire una "Pulizia di Gruppo".
- Invece di pulire dopo ogni singolo passaggio, hanno sviluppato un trucco matematico (chiamato Multi-Ricalibrazione) che ti permette di aspettare e pulire multiple strati di disordine contemporaneamente.
- L'Analogia: Immagina di lavare i piatti. Invece di lavare un piatto, asciugarlo e riporlo, poi lavare una tazza, asciugarla e riporla, lavi un intero mucchio di piatti, poi asciugi l'intero mucchio, poi li riponi tutti. Fai l'"asciugatura" (la parte costosa e lenta) solo una volta per l'intero gruppo.
Il Risultato: Riorganizzando il modo in cui raggruppano gli ingredienti (la "partizione"), possono combinare questi passaggi di pulizia. Per la moltiplicazione tra 4 e 12 ingredienti, il loro nuovo metodo risparmia il 32% dello spazio e dimezza il tempo (45% più veloce) rispetto alla vecchia linea "due per due".

3. Perché Questo è Importante (Secondo l'Articolo)

L'articolo si concentra strettamente sull'architettura hardware — il design fisico del chip del computer che esegue questi calcoli.

Hanno dimostrato che cambiando come la matematica è organizzata (l'algoritmo) e come è costruito il chip (l'architettura), è possibile eseguire calcoli crittografati complessi molto più velocemente.
Menzionano specificamente che questo aiuta applicazioni come l'apprendimento automatico, la diagnosi medica e l'analisi finanziaria, perché questi campi richiedono spesso di moltiplicare molti punti dati crittografati insieme.

Riepilogo

Pensa a questo articolo come all'invenzione di una nuova cucina super-efficiente per uno chef che non può togliersi i guanti da forno.

Hanno capito come mescolare tre ingredienti alla volta senza fare disordine.
Hanno inventato un modo per pulire multiple strati di disordine contemporaneamente, invece che uno alla volta.
Il risultato è una cucina che è più piccola, più veloce e richiede meno energia per mantenere al sicuro i segreti mentre esegue calcoli complessi.

Gli autori non hanno testato questo su pazienti reali o conti bancari reali in questo articolo; hanno solo dimostrato che la macchina progettata per fare questo lavoro è significativamente migliore delle macchine che avevamo prima.

Riepilogo Tecnico: Moltiplicazione di Cifratari a Multipli Input per la Crittografia Omomorfica

Enunciato del Problema
La crittografia omomorfica (HE), in particolare lo schema RNS-CKKS, consente operazioni aritmetiche su dati cifrati, aspetto critico per applicazioni di tutela della privacy come l'apprendimento automatico e la diagnosi medica. Tuttavia, gli schemi HE standard definiscono la moltiplicazione di cifratari solo per due input. Molte applicazioni pratiche, come le approssimazioni polinomiali di ordine elevato per le funzioni di attivazione delle reti neurali (ad esempio ReLU), gli alberi decisionali e il sequenziamento del genoma, richiedono la moltiplicazione di più cifratari ( $n > 2$ ).

Gli approcci esistenti per gestire la moltiplicazione a multipli input collegano tipicamente più moltiplicatori a due input in una struttura ad albero binario. Questo metodo soffre di due principali inefficienze:

Alta Latenza e Area: La moltiplicazione sequenziale di $n$ cifratari utilizzando unità a due input comporta un significativo sovraccarico hardware e latenza.
Crescita del Rumore e Sovraccarico di Ridimensionamento: Ogni moltiplicazione aumenta il livello di rumore, rendendo necessaria un'operazione di ridimensionamento (rescaling) per ripristinare la scala del messaggio. In un albero binario standard, il ridimensionamento deve avvenire dopo ogni passo di moltiplicazione per prevenire una crescita esponenziale del rumore. Ciò comporta un gran numero di unità di ridimensionamento, ognuna delle quali richiede costose operazioni di Trasformata Numerica Teorica (NTT) e Inversa NTT (INTT), aumentando significativamente la complessità computazionale e l'utilizzo delle risorse hardware.

Metodologia
Il documento propone un framework per la moltiplicazione diretta di cifratari a $n$ input che minimizza la profondità moltiplicativa e la complessità hardware. La metodologia è suddivisa in due contributi principali:

Moltiplicatore a Tre Input Migliorato:
Gli autori riformulano inizialmente il processo di moltiplicazione a tre input. Nel lavoro preliminare [26], la rielinearizzazione e il ridimensionamento venivano eseguiti separatamente, richiedendo multiple operazioni ModUp/ModDown e numerosi blocchi (I)NTT. Il nuovo design:
- Riformula la Rielinearizzazione: Spostando il fattore di scala $P^{-1}$ nella conversione di base (BConv) e nella moltiplicazione della chiave di valutazione, il design elimina i passi di scala separati.
- Ottimizza il Ridimensionamento: Gli autori ristrutturano il percorso dati per eseguire il ridimensionamento nel dominio originale prima della NTT finale, piuttosto che nel dominio NTT. Ciò consente di eliminare le operazioni (I)NTT ridondanti.
- Risultato: Queste modifiche riducono il numero di blocchi (I)NTT nel percorso dati da otto a quattro, dimezzando efficacemente la lunghezza del percorso dati.
Estensione a Multipli Input con Ridimensionamento Combinato:
Per estendere la moltiplicazione a $n > 3$ input senza aumentare la profondità moltiplicativa, il documento introduce:
- Chiavi di Valutazione Generalizzate: Vengono introdotte nuove chiavi di valutazione ( $ek_t$ ) per rielinearizzare i termini polinomiali di grado superiore ( $d_t s^t$ ) generati dalla moltiplicazione di $n$ cifratari, riducendo il risultato a un formato a due polinomi.
- Algoritmo Multi-Ridimensionamento (Multi-RS): Un'analisi teorica identifica le condizioni in cui più operazioni di ridimensionamento possono essere ritardate e combinate. Gli autori propongono un algoritmo che esegue $\mu$ operazioni di ridimensionamento concatenate utilizzando lo stesso numero di operazioni (I)NTT di un singolo ridimensionamento. Ciò è ottenuto trasformando l'input nel dominio INTT, eseguendo ridimensionamenti iterativi nel dominio dei coefficienti e trasformando nuovamente, utilizzando costanti precalcolate per unire le operazioni.
- Linee Guida per la Partizione degli Input: Il documento fornisce linee guida per partizionare $n$ input in gruppi (ad esempio, $(n_1, n_2, \dots, n_m)$ ) per massimizzare il numero di operazioni di ridimensionamento combinate mantenendo la profondità moltiplicativa ottimale di $\lceil \log_2 n \rceil$ . Ciò comporta la creazione di strutture ad albero sbilanciate quando possibile, per raggruppare più input prima di un passo di ridimensionamento.

Contributi Chiave

Riformulazione Algoritmica: Una nuova formulazione per la moltiplicazione a tre input che combina i calcoli intermedi, riducendo il numero di operazioni (I)NTT e accorciando il percorso dati.
Framework a Multipli Input: Un'estensione della moltiplicazione di cifratari a $n$ input arbitrari utilizzando chiavi di valutazione generalizzate e un moltiplicatore strutturato ad albero.
Ridimensionamento Combinato: Un nuovo algoritmo di multi-ridimensionamento che riduce la complessità dell'esecuzione di multipli ridimensionamenti a quella di un singolo ridimensionamento, indipendentemente dal numero di passi combinati ( $\mu$ ).
Architettura Hardware: Progettazione di architetture hardware completamente pipeline per i moltiplicatori proposti, incluse unità ModUp, ModDown e di ridimensionamento ottimizzate.

Risultati
I design proposti sono stati sintetizzati utilizzando il processo GlobalFoundries 22FDX con parametri $N=2^{16}$ , $L=K=24$ e $w=64$ .

Moltiplicatore a Tre Input: Rispetto al lavoro precedente [26], il moltiplicatore a tre input migliorato ottiene una riduzione del 15% dell'area logica e una riduzione del 50% della latenza. Riduce inoltre i requisiti di memoria di circa il 20% grazie a un minor numero di unità (I)NTT.
Moltiplicatori a Multipli Input ( $n=4$ a $12$): Rispetto a un'implementazione di base che utilizza un albero binario di moltiplicatori a due input, il metodo proposto ottiene una riduzione media del 32% dell'area totale e una riduzione del 45% della latenza.
Efficienza del Ridimensionamento: Per input non potenze di due (ad esempio, $n=17$ ), la partizione ottimizzata combinata con il multi-ridimensionamento riduce il numero totale di unità di ridimensionamento (e relative operazioni (I)NTT) di circa il 47% rispetto all'approccio standard ad albero binario.

Significato
Il documento afferma che questi miglioramenti affrontano il collo di bottiglia della moltiplicazione a multipli input nell'HE, essenziale per complesse applicazioni di tutela della privacy. Riducendo la complessità hardware e la latenza della moltiplicazione di cifratari, l'architettura proposta rende più fattibile il dispiegamento dell'HE in ambienti con risorse limitate o ad alta throughput. Il lavoro dimostra che, attraverso la riformulazione algoritmica e un'attenta partizione degli input, il sovraccarico della gestione del rumore (ridimensionamento) può essere significativamente minimizzato senza compromettere la sicurezza o la correttezza dello schema di crittografia. Gli autori notano che il lavoro futuro si concentrerà sull'ulteriore semplificazione dei moltiplicatori per numeri ancora maggiori di input.