Sintesi Tecnica: HE-LRM

Definizione del Problema

La Crittografia Completamente Omomorfica (FHE) consente l'inferenza neurale che preserva la privacy su dati criptati, tuttavia le soluzioni esistenti affrontano principalmente modelli con input densi (es. CNN, MLP). I modelli di raccomandazione di Deep Learning (DLRM) presentano una sfida distinta a causa della loro dipendenza da input categorici sparsi gestiti attraverso massicce tabelle di embedding.

In un DLRM standard, le feature sparse vengono mappate in vettori densi tramite lookup in tabeli di embedding. In un contesto FHE (specificamente utilizzando lo schema CKKS), l'indicizzazione diretta non è nativamente supportata; sono disponibili solo addizioni SIMD, moltiplicazioni e rotazioni cicliche. Gli approcci ingenui ai lookup criptati affrontano gravi problemi di scalabilità:

1. Overhead di Comunicazione: Una codifica "one-hot" di un indice per una tabella con $k$ righe richiede un vettore di dimensione $k$. Per dataset su scala industriale come Criteo (33,8 milioni di righe), ciò richiede il caricamento di oltre 1.000 ciphertext (>1 GiB) per singola inferenza.
2. Costi Computazionali lato Server: Il lavoro precedente (es. Kim et al. [10]) tenta di mitigare i costi di upload facendo costruire al server il selettore one-hot a partire da un indice criptato. Tuttavia, ciò richiede circuiti aritmetici profondi (funzioni indicatrici) che consumano un significativo livello moltiplicativo, rendendo spesso necessarie costose operazioni di bootstrapping.
3. Perdita di Memoria e Struttura: Le tecniche di compressione esistenti spesso richiedono che il client memorizzi mappature di codici apprese (rivelando le correlazioni degli embedding) o risultano in un utilizzo inefficiente degli slot e in un elevato footprint di memoria sul server.

Metodologia: HE-LRM

Gli autori propongono HE-LRM, un sistema FHE end-to-end ottimizzato per l'inferenza DLRM. La soluzione affronta il collo di bottiglia del lookup di embedding attraverso tre innovazioni tecniche centrali:

1. Compressione per Decomposizione dei Dati lato Client

Invece di fare affidamento sulla costruzione lato server di vettori one-hot o su mappature di codici apprese che rivelano la struttura, HE-LRM impiega una tecnica di compressione deterministica lato client basata sulla decomposizione dei dati (digit decomposition).

• Meccanismo: Una tabella di embedding originale di dimensione $k \times d$ viene decomposta in $\ell$ tabelle più piccole di dimensione $p \times d$ (dove $k \approx p^\ell$).
• Processo: Il client prende un indice categorico $i$ e lo decompone in una tupla di cifre in base-$p$ $(i_0, i_1, \dots, i_{\ell-1})$.
• Privacy: Il client costruisce localmente le codifiche one-hot per queste cifre più piccole e le cripta. Il server non vede mai l'indice originale, né deve eseguire costose funzioni indicatrici omomorfiche. La compressione è appresa end-to-end durante l'addestramento senza rivelare la struttura della mappatura al client.

2. Strategia di Packing Diagonale a Blocchi

I DLRM utilizzano tipicamente molteplici tabelle di embedding (es. 26 per Criteo). HE-LRM introduce una strategia di packing diagonale a blocchi per gestirle simultaneamente.

• Implementazione: Molteplici tabelle di embedding sono concatenate diagonalmente in un'unica grande matrice di pesi.
• Vantaggio: Ciò consente al client di concatenare le codifiche one-hot per tutte le feature in un unico vettore. Il server può quindi eseguire un singolo prodotto matrice-vettore Baby-Step Giant-Step (BSGS) per recuperare gli embedding per tutte le tabelle in parallelo. Questo massimizza l'utilizzo degli slot dei ciphertext ed evita l'overhead del processamento sequenziale delle tabelle.

3. Trasformazione Lineare Ottimizzata

Il sistema sfrutta l'algoritmo double-hoisted BSGS per il prodotto matrice-vettore.

• A differenza degli approcci precedenti "Table-Mult" che richiedono rotazioni separate per ogni dimensione del vettore di embedding (consumando livelli moltiplicativi extra), l'approccio BSGS tratta il lookup come una standard trasformazione lineare.
• Ciò riduce l'operazione a un singolo livello moltiplicativo, eliminando la necessità di bootstrapping intermedio durante la fase di lookup.

Contributi Chiave

1. Primo DLRM FHE End-to-End: HE-LRM è il primo sistema che supporta sia feature dense che sparse in un DLRM sotto FHE, validato sui dataset UCI Heart Disease e Criteo.
2. Accelerazione di 56×: La proposta di decomposizione dei dati lato client e la strategia di lookup BSGS ottiene un'accelerazione di 56× rispetto allo stato dell'arte (CodedHeLUT) per grandi dimensioni di embedding (768). Ciò è ottenuto evitando le funzioni indicatrici lato server, riducendo il consumo di livelli moltiplicativi (da ~10 livelli a 1) ed eliminando la necessità di bootstrapping durante la fase di lookup.
3. Lookup Multi-Tabella in Parallelo: La strategia di packing diagonale a blocchi consente lookup paralleli efficienti attraverso molteplici tabelle di embedding, riducendo significativamente l'overhead di comunicazione e computazione rispetto al processamento delle tabelle individualmente.
4. Profilo di Leakage Pulito: Il metodo aderisce a un modello di minaccia semi-onesto in cui il client conosce solo le dimensioni degli input e le dimensioni delle tabelle, ma non apprende nulla sui valori degli embedding, sulle correlazioni o sui parametri del modello.

Risultati Sperimentali

Gli autori hanno valutato HE-LRM utilizzando il framework FHE open-source Orion su una CPU single-threaded (Intel Xeon Gold 5218).

• UCI Heart Disease: Ha raggiunto una latenza di inferenza end-to-end di 24 secondi.
• Dataset Criteo: Ha raggiunto latenze che variano da 228 a 489 secondi a seconda del rapporto di compressione (che varia da $10\times$ a $10^5\times$).
  • Modelli altamente compressi ($\approx 10^3\times$ a $10^5\times$) hanno mostrato latenze simili (~230s) perché il tempo di lookup dell'embedding è diventato trascurabile (3–5 secondi) rispetto al resto della rete, e l'operazione BSGS poteva essere eseguita su un singolo ciphertext.
  • Modelli meno compressi richiedevano più ciphertext, aumentando la latenza del prodotto matrice-vettore.
• Proiezioni Hardware:
  • GPU: Le proiezioni utilizzando l'acceleratore Cheddar suggeriscono un aumento di velocità di ~200× rispetto alla CPU, riducendo l'inferenza di Criteo a circa 1 secondo.
  • ASIC: Le proiezioni utilizzando il modello di costo Osiris suggeriscono latenze sub-secondarie (~0,037 secondi) per i modelli compressi.

Significato e Rivendicazioni

Il paper afferma che HE-LRM colma una lacuna critica nell'inferenza privata, dimostrando che i sistemi di raccomandazione che preservano la privacy si stanno avvicinando a una distribuzione pratica.

• Scalabilità: Il lavoro dimostra che il "collo di bottiglia dell'embedding" in FHE può essere risolto senza sacrificare la privacy o richiedere al client di possedere i pesi del modello.
• Efficienza del Sistema: Spostando la complessità della codifica dell'indice al client (tramite decomposizione deterministica) e utilizzando l'algebra lineare efficiente (BSGS) sul server, il sistema evita i costi proibitivi del bootstrapping e l'enorme overhead di comunicazione associato ai naive one-hot encodings.
• Ampia Applicabilità: Gli autori osservano che la primitiva di lookup dell'embedding criptato non è limitata ai DLRM, ma è rilevante anche per i modelli basati su Transformer, suggerendo un'astrazione riutilizzabile per futuri sistemi di inferenza privata.

Gli autori rimangono modesti riguardo alle attuali prestazioni della CPU (minuti per modelli grandi), sottolineando che le accelerazioni dimostrate su hardware GPU e ASIC sono necessarie per una distribuzione reale in produzione.