💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Questo articolo introduce un algoritmo di scansione prefissa ottimale per la rotazione per layout di crittografia omomorfica bit-reversed che riduce la complessità di rotazione da $O(m^2)$ a $O(m)$ , sfruttando un invariante di replica-aggregazione, riducendo così significativamente la latenza computazionale, l'uso della memoria e l'archiviazione delle chiavi di valutazione, consentendo al contempo pipeline a valle più profonde.

Autori originali: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Pubblicato 2026-07-07

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

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 avere un enorme foglio di calcolo criptato dove ogni cella contiene un numero segreto. Vuoi eseguire un trucco matematico specifico su tutti questi numeri contemporaneamente: per ogni cella, devi conoscere il "totale progressivo" di tutti i numeri che l'hanno preceduta. Nel mondo della Crittografia Omomorfa (calcolare su dati segreti senza mai decriptarli), questo è chiamato "prefix scan" (scansione prefissa).

Il problema è che i dati non sono memorizzati in una fila ordinata come 1, 2, 3, 4. A causa di come funziona la crittografia, i dati sono rimescolati secondo un modello specifico chiamato "ordine a inversione di bit" (bit-reversed order). È come un libro in cui le pagine sono state rimescolate: la pagina 1 è seguita dalla pagina 8, poi dalla 4, poi dalla 12, e così via.

Il Vecchio Metodo: Il Problere del "Vicino Esatto"

Per calcolare il totale progressivo, di solito devi chiedere al tuo vicino il suo numero. In una riga normale, il tuo vicino è a un solo passo di distanza. Ma in questo libro rimescolato in "inversione di bit", il tuo vicino logico potrebbe trovarsi dall'altra parte della stanza.

Il vecchio metodo cercava di risolvere questo problema inviando un messaggero (una "rotazione") per andare a recuperare il vicino esatto di cui avevi bisogno.

L'Analogia: Immagina di essere in una biblioteca con 8 scaffali. Devi parlare con la persona che si trova alla tua sinistra. Ma poiché gli scaffali sono rimescolati, "sinistra" significa distanze fisiche diverse per persone diverse.
Il Costo: Per far sì che tutti ottenessero il proprio vicino corretto, il bibliotecario doveva inviare messaggeri su molte diverse rotte. Per un libro piccolo di 8 pagine, servivano 6 messaggeri. Per un libro più grande, il numero di messaggeri esplodeva (cresceva come un triangolo: 1+2+3+4...). Questo era lento, costoso e richiedeva una libreria enorme di "chiavi" (permessi) per inviare messaggeri in tutti quei posti diversi.

Il Nuovo Metodo: La Strategia del "Copia e Incolla"

Gli autori di questo articolo si sono resi conto che stavamo essendo troppo pignoli. Non avevamo bisogno del vicino esatto; avevamo solo bisogno di chiunque facesse parte del gruppo del vicino che avesse la stessa informazione.

L'Analogia: Inveve di chiedere alla specifica persona alla tua sinistra, immagina che ogni persona in un "gruppo" (un blocco di scaffali) stia tenendo una copia identica del punteggio totale del gruppo.
La Mossa Magica: Gli autori hanno scoperto un modo per ruotare l'intera biblioteca una sola volta per ogni livello del calcolo. Questa singola rotazione sposta tutti in un punto in cui si trovano accanto a qualcuno del gruppo adiacente. Poiché tutti in quel gruppo stanno tenendo una copia del "totale del gruppo", non importa quale persona specifica si ottenga; il calcolo funziona perfettamente.
Il Risultato: Invece di aver bisogno di 6 messaggeri per 8 pagine, hai bisogno di 1 messaggero per livello. Per l'intero libro, passi dal necessitare di un numero di messaggeri triangolare (come 28) a solo il numero di livelli (come 7).

Cosa Hanno Effettivamente Dimostrato

L'articolo non dice solo "questo è più veloce". Ha dimostrato tre fatti matematici difficili:

Non si può fare di meglio: Hanno dimostrato che, indipendentemente da quanto si sia astuti, si deve usare almeno tanti messaggi quanti sono i livelli nel calcolo. Non si possono saltare del tutto i messaggeri.
La Rotta "Perfetta": Hanno mostrato che, se si utilizza il numero minimo di messaggeri, questi devono seguire un modello molto specifico e rigido (legato alle potenze di 2). Non c'è margine di manovra; la matematica impone questo percorso specifico.
Il Compromesso: Per risparmiare sui messaggeri, bisogna fare un po' più di lavoro matematico localmente (mantenendo due set di numeri invece di uno). Ma nei loro test, risparmiare sui messaggeri è valso la pena rispetto al lavoro matematico extra.

Il Test del Mondo Reale (Il Problema del "Riporto")

Hanno testato questo su un problema matematico molto comune: il riporto dei numeri (come quando aggiungi 9 + 3 e ottieni 12, devi "riportare" l'1 alla colonna successiva).

La Configurazione: Hanno criptato una lista di cifre e hanno cercato di correggere i riporti senza rimescolare l'ordine.
L'Esito:
- Velocità: Il loro nuovo metodo era circa il 20% più veloce del vecchio metodo del "vicino esatto" per problemi di medie dimensioni.
- Memoria: Utilizzava il 64% di memoria in meno perché non avevano bisogno di memorizzare così tante chiavi di permesso.
- La Grande Vittoria: In una catena di calcoli più lunga, il loro metodo ha risparmiato abbastanza "potenza di crittografia" da evitare una procedura di reset massiccia e lenta (chiamata "bootstrapping"). Questo ha reso l'intero processo 4,3 volte più veloce dall'inizio alla fine.

Riassunto

Pensatelo come una staffetta.

Vecchio Metodo: Ogni corridore doveva percorrere un sentiero unico, lungo e tortuoso per trovare il proprio compagno specifico. Richiedeva molta energia e tempo.
Nuovo Metodo: La squadra si è resa conto che se avessero corso un giro breve e standardizzato, tutti sarebbero finiti accanto a un compagno che aveva lo stesso testimone. Ha richiesto meno passi, meno energia e ha portato a termine il lavoro più velocemente, anche se i corridori dovevano tenere in mano qualche testimone in più.

L'articolo dimostra che questa scorciatoia è il modo più veloce in assoluto per eseguire questo specifico tipo di calcolo su dati criptati e rimescolati.

Sintesi Tecnica: Scansioni di Prefisso Noncommutative Ottimali per Rotazione in Layout Bit-Reversed

Definizione del Problema

Nella crittografia omomorfica (HE) impacchettata, specificamente nello schema CKKS, le operazioni SIMD consentono il calcolo parallelo su vettori cifrati. Tuttavia, la comunicazione tra gli slot richiede rotazioni cicliche (automorfismi di Galois), che sono operazioni onerose che comportano il cambio di chiave (key switching). Il costo di una rotazione dipende dalla disposizione fisica dei dati.

Il documento affronta il problema dell'esecuzione di computazioni di prefisso ordinate (scansioni) su $n = 2^m$ elementi di un monoide associativo, potenzialmente non commutativo, quando i dati sono memorizzati in un ordine bit-reversed (in ordine di inversione dei bit). Questa disposizione è comune nelle trasformate veloci e nelle conversioni di packing.

La sfida principale è che una scansione standard a "predecessore trasportato" (transported-predecessor), che raddoppia ricorsivamente la distanza dai predecessori logici, comporta un elevato costo di routing in un layout bit-reversed. Poiché l'inversione dei bit permuta gli indici logici, uno shift logico singolo di $2^t$ si decompone in molteplici classi di spostamento ciclico distinte. Di conseguenza, un'implementazione diretta richiede $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotazioni. Gli autori indagano se questo costo triangolare sia una proprietà inerente alla computazione del prefisso nei layout bit-reversed o un artefatto della specifica topologia di routing.

Metodologia e Costruzione

Il documento introduce un invariante di replica-aggregazione per ridurre il conteggio delle rotazioni da quadratico a lineare.

Replicazione Semantica: Invece di instradare ogni slot al suo esatto predecessore logico, la costruzione mantiene uno stato in cui ogni slot all'interno di un blocco logico allineato contiene l'aggregato completo di quel blocco.
Scambio tra Blocchi Sibling: Ad ogni livello $d$ $d$ della scansione (combinando blocchi di dimensione $2^d$ $2^{d}$ ), l'algoritmo ruota lo stato aggregato di un offset specifico $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ .
- Sotto inversione dei bit, i due figli di un blocco genitore occupano cosetti fisici separati esattamente da $s_d$ .
- Una rotazione di $s_d$ mappa uno slot in alcuna posizione nel blocco sibling. Poiché l'aggregato del sibling è replicato in tutti i suoi slot, qualsiasi posizione nel blocco sibling fornisce il valore semantico corretto.
- Ciò consente a una singola rotazione ciclica diretta di fornire aggregati validi per entrambe le orientazioni dei figli simultaneamente, preservando la correttezza per i monoide non commutativi tramite maschere pubbliche che selezionano l'ordine degli operandi.
Formulazione di Scansione Esclusiva: Gli autori implementano una scansione esclusiva (che restituisce il prefisso prima dell'elemento corrente). Questo evita la necessità di uno shift finale del predecessore logico per recuperare il carry in entrata per la correzione del dígito, un requisito che altrimenti reintroduce il routing sensibile al layout.
Dimostoli di Limite Inferiore: Il documento stabilisce che $m$ rotazioni sono un limite inferiore globale per qualsiasi circuito che computi un output dipendente da tutti i $2^m$ input in questo modello. La prova si basa su un argomento di subset-sum: se vengono utilizzate $R$ rotazioni, al massimo $2^R$ spostamenti di input distinti possono raggiungere un output fisso. Per coprire tutti i $2^m$ input, $R \ge m$ è necessario. Inoltre, il documento prova che il raggiungimento di questo limite richiede che gli offset di rotazione formino una completa base 2-adica (un offset per ogni valutazione $0, \dots, m-1$ ).

Contributi Chiave

Costruzione di Scansione Ottimale: Un algoritmo di scansione inclusiva ed esclusiva che raggiunge $R = m$ rotazioni e $D = m$ profondità del monoide per i layout bit-reversed. Ciò riduce il conteggio delle rotazioni dal costo $O(m^2)$ della topologia diretta a $O(m)$ .
Rigidità dell'Ottimalità: Una caratterizzazione di tutti i circuiti ottimali. Se un circuito utilizza esattamente $m$ rotazioni, gli offset devono formare una base 2-adica completa. Ciò dimostra che il profilo di rotazione è rigido, anche se la topologia del circuito varia.
Frontiera delle Chiavi di Rotazione: Un'analisi del compromesso tra il numero di offset con chiave diretta ( $K$ $K$ ) e il numero di chiamate di rotazione online ( $R$ $R$ ).
- Il documento deriva un limite inferiore del prodotto: $\prod (c_j + 1) \ge 2^m$ , dove $c_j$ è il numero di volte che la chiave $j$ viene utilizzata.
- Quando $K$ divide $m$ , la frontiera esatta è provata essere $R^* = K \cdot (2^{m/K} - 1)$ .
Istanza Radix-CKKS: Applicazione della scansione esclusiva alla propagazione esatta di carry e borrow in radix-based CKKS. Ciò consente il confronto tra interi e l'aritmetica modulare senza ripristinare l'ordine naturale o eseguire uno shift finale.
Efficienza di Batching: Dimostrazione che i risparmi di rotazione valgono per gli interleaving digit-major completamente occupati, dove $g$ interi indipendenti sono impacchettati in un singolo ciphertext senza moltiplicare il conteggio delle rotazioni.

Risultati e Valutazione

Gli autori hanno implementato l'algoritmo in Lattigo (Go) e l'hanno confrontato con due baseline:

Predecessore Bit-Reversed Diretto: L'approccio ingenuo con rotazioni $O(m^2)$ .
Normalize–Scan–Restore: Una baseline che converte i dati in ordine naturale, esegue la scansione e riconverte.

Risultati Chiave a $m=7$ (128 slot):

Rotazioni: Ridotte da 28 (diretto) a 7 (replicato).
Chiavi di Valutazione: Lo storage è ridotto del 70.0% (908.6 MB $\to$ 272.6 MB).
Memoria: L'uso del picco di heap è ridotto del 63.9% (2.30 GB $\to$ 830.5 MB).
Latenza: La scansione replicata ha migliorato la latenza isolata della scansione del 19.9% rispetto al metodo del predecessore diretto.
Pipeline End-to-End: In una pipeline a valle di profondità 5, la scansione replicata ha evitato un'operazione completa di bootstrapping richiesta dalla baseline normalize-restore. Ciò ha prodotto un guadagno di velocità medio accoppiato di 4.31 $\times$ (95% CI [3.69, 4.92]).

Il documento nota che, sebbene "normalize–scan–restore" abbia una latenza isolata inferiore per piccoli $m$ a causa di meno composizioni del monoide, la scansione replicata diventa più veloce per $m \ge 5$ e offre una maggiore efficienza delle risorse (chiavi, memoria, livelli di modulo).

Significato e Rivendicazioni

Il documento afferma che preservare una rappresentazione SIMD bit-reversed non impone un overhead di rotazione inevitabile per la computazione del prefisso ordinato. Il significato risiede nel:

Rompere la Barriera Quadratica: Provare che il costo $O(m^2)$ del routing diretto nei layout bit-reversed non è intrinseco ma può essere ridotto al limite teorico di $O(m)$ tramite la replica semantica.
Compromessi di Risorse: Stabilire che la riduzione del costo di routing (rotazioni) e dello storage delle chiavi avviene a scapito di un maggiore lavoro del monoide impacchettato ( $2m-1$ composizioni rispetto a $m$ ) e di un secondo vettore di stato vivo. Il documento sostiene che questo compromesso è favorevole per le pipeline profonde dove i livelli di modulo e il bootstrapping sono colli di bottiglia.
Esattezza: Fornire limiti inferiori esatti e caratterizzazioni della frontiera per la gestione delle chiavi di rotazione, andando oltre le ottimizzazioni euristiche verso limiti provabili per specifici pattern di dipendenza.

Il lavoro è presentato come un'ottimizzazione specifica per il vincolo del layout bit-reversed, distinta dalla teoria generale delle reti di prefisso, ed è validata attraverso prove combinatorie rigorose e valutazione empirica in un'implementazione standard di CKKS.