Sintesi Tecnica: Ricerca di Embedding Privata con Query Compatte Criptate tramite Omomorfismo Completamente Omomorfo

Definizione del Probleamento

Nella machine learning preservante la privacy (PPML) che utilizza l'Omomorfismo Completamente Omomorfo (FHE), emerge un collo di bottiglia critico durante l'inferenza di modelli che si basano su input discreti, come l'elaborazione del linguaggio naturale (NLP) e i sistemi di raccomandazione. Questi modelli tipicamente iniziano con uno strato di embedding, che mappa un indice discreto (ad esempio, un token di una parola) in un vettore continuo.

Sotto FHE, il server non può eseguire l'accesso standard alla memoria basato su un indice criptato. Pertanto, la ricerca deve essere realizzata attraverso l'aritmetica omomorfa. Gli approcci esistenti affrontano un compromesso:

1. Ricerca lato client: Il client invia il vettore di embedding criptato. Ciò comporta un overhead di comunicazione massiccio proporzionale alla dimensione dell'embedding ($d$), proibitivo per tabelle di grandi dimensioni (ad esempio, GloVe con 1,9 milioni di token).
2. Ricerca lato server con Generazione One-Hot: Il client invia un indice scalare compatto criptato. Il server deve quindi costruire omomorfamente un vettore one-hot per selezionare l'embedding. Il lavoro precedente (Kim et al., ICML 2024) ottiene questo risultato utilizzando una Funzione Indicatrice Criptata (EIF), ma ciò richiede $O(p \log p)$ operazioni omomorfe (dove $p$ è la dimensione della tabella), consumando una profondità moltiplicativa significativa e diventando il costo dominante nella pipeline di inferenza.

L'obiettivo è ottenere una Ricerca di Embedding Privata (PEL) che mantenga una comunicazione compatta per il client (inviando solo un indice scalare) minimizzando al contempo il costo computazionale omomorfo lato server, evitando lo costoso passaggio di generazione one-hot.

Metodologia: Valutazione di Vettori Indipendenti (IVE)

Gli autori propongono la Valutazione di Vettori Indipendenti (Independent Vector Evaluation - IVE), un metodo che evita completamente la costruzione di un vettore one-hot.

Intuizione Centrale

Il server non richiede strettamente un vettore one-hot ($e_j$) per recuperare l'embedding $M_j$. Richiede solo una rappresentazione dell'indice $j$ che sia linearmente indipendente tra diversi indici. Se un insieme di vettori $\{v_j\}$ è linearmente indipendente, esiste una matrice di cambio di base $L$ tale che $L v_j = e_j$. Di conseguenza, il recupero dell'embedding può essere riscritto come:
$$M_j = M e_j = M (L v_j) = (M L) v_j$$
Poiché $M$ e $L$ sono noti in chiaro, il server può precomputare la matrice $M' = ML$. Il compito online passa quindi dalla generazione di un vettore one-hot alla valutazione del vettore $v_j$ in modo omomorfo.

Costruzione del Vettore e Stabilità

Per garantire efficienza e stabilità numerica sotto lo schema CKKS (che supporta l'aritmetica approssimata):

1. Efficienza: I vettori $v_j$ sono costruiti utilizzando potenze successive di un singolo valore criptato $\alpha_j$. Ciò consente al server di generare le componenti del vettore utilizzando operazioni aritmetiche standard (moltiplicazioni) invece di complessi test di uguaglianza.
2. Stabilità: Per prevenire l'amplificazione dell'errore durante il cambio di base, la matrice $L$ deve essere ben condizionata (idealmente ortogonale). Gli autori utilizzano una matrice di Trasformata Discreta del Coseno (DCT). Utilizzando le radici dell'unità e separando le parti reali e immaginarie, costruiscono una base ortogonale che si allinea con le capacità di aritmetica complessa di CKKS.

Flusso Algoritmico

1. Client: Cripta l'indice $j$ in un valore $\alpha_j$ (derivato dalle radici dell'unità) e lo trasmette come una query scalare compatta.
2. Server (Fase IVE):
   • Riceve l' $\alpha_j$ criptato.
   • Calcola le potenze $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ utilizzando un albero di moltiplicazione (profondità logaritmica).
   • Separa le parti reali e immaginarie tramite coniugazione per formare il vettore $v_j$.
   • Questo processo richiede $O(p)$ operazioni omomorfe, una riduzione significativa rispetto al $O(p \log p)$ richiesto per la generazione one-hot.
3. Server (Fase PCMM):
   • Esegue una Moltiplicazione Matrice-Testo in Chiaro (PCMM) tra la matrice precomputata $M' = ML$ e il vettore generato $v_j$.
   • Questo produce il vettore di embedding criptato.

Contributi Chiave

1. Valutazione di Vettori Indipendenti (IVE): Un nuovo algoritmo che sostituisce la generazione di un vettore one-hot criptato con la valutazione di una famiglia di vettori linearmente indipendenti. Questo riduce la complessità di generazione del vettore da $O(p \log p)$ a $O(p)$ operazioni omomorfe.
2. Base Ortogonale tramite DCT: L'istanza di IVE tramite una matrice ortogonale basata su DCT garantisce la stabilità numerica, mitigando l'amplificazione dell'errore inerente all'approssimazione CKKS durante l'esecuzione del cambio di base.
3. Pipeline PEL Integrata: Gli autori integrano IVE con PCMM per gestire query batch in modo efficiente. Questa pipeline supporta query di più token simultaneamente, ammortizzando il costo attraverso gli slot SIMD di CKKS.
4. Implementazione End-to-End: Il metodo è implementato all'interno di una pipeline di classificazione del testo di tipo FastText, dimostrando la sua fattibilità per compiti di inferenza pratici e sensibili alla privacy.

Risultati Sperimentali

Gli autori hanno valutato IVE-PEL rispetto allo stato dell'arte precedente (Kim et al.) utilizzando tre dataset di embedding (GloVe.6B.50d, GloVe.42B.300d e GPT-2) e un'inferenza FastText end-to-end sul dataset Enron-Spam.

• Accelerazione della Generazione del Vettore: IVE-PEL riduce significativamente il tempo speso sulla generazione del vettore. Per una dimensione di sottotabella $\log p = 10$, il tempo di VecGen è sceso da circa 424 ms (Kim et al.) a circa 3,15 ms (IVE-PEL) su GloVe.6B.50d, rappresentando un'accelerazione di 134,6× in questa specifica fase.
• Accelerazione dell'Intera Pipeline: Il tempo di ricerca ammortizzato è migliorato di 18,5× fino a 78,4× a seconda del dataset e della dimensione dell'embedding. I maggiori guadagni sono stati osservati negli scenari in cui la generazione del vettore era il costo dominante.
• Profondità Moltiplicativa: IVE-PEL consuma circa 1/3 della profondità moltiplicativa richiesta dal metodo di generazione one-hot, consentendo dimensioni di sottotabella più grandi e una migliore qualità di compressione senza esaurire il budget di rumore di CKKS.
• Impatto End-to-End: Nel compito di classificazione Enron-Spam, la sostituzione del metodo one-hot con IVE ha ridotto la quota della generazione del vettore nel tempo totale di inferenza criptata dal 99,6% al 66,3%, abbassando sostanzialmente la latenza complessiva.

Significato e Rivendicazioni

Il paper sostiene che IVE-PEL affronta il "punto di progettazione mancante" nella ricerca di embedding privata: ottenere una comunicazione compatta per il client (indici scalari) senza incorrere nel costo proibitivo lato server della generazione one-hot omomorfa.

Decoppiando la necessità di una base one-hot dal processo di recupero, gli autori dimostrano che la ricerca di embedding privata può essere resa pratica per client leggeri e modelli su larga scala. I risultati suggeriscono che IVE-PEL rende la ricerca di embedding lato server un'alternativa viabile alla ricerca lato client, consentendo un'inferenza efficiente e preservante la privacy per modelli NLP e di raccomandazione senza sacrificare la riservatezza degli indici di input dell'utente. Il metodo mantiene l'accuratezza dei modelli sottostanti (come dimostrato dai risultati di classificazione del sentiment IMDB e rilevamento dello spam) migliorando drasticamente l'efficienza computazionale.