Résumé technique : Recherche d'embeddings privée avec requêtes compactes chiffrées sous chiffrement homomorphe complet

Énoncé du problème

Dans l'apprentissage automatique préservant la confidentialité (PPML) utilisant le chiffrement homomorphe complet (FHE), un goulot d'étranglement critique apparaît lors de l'inférence de modèles reposant sur des entrées discrètes, tels que le traitement du langage naturel (NLP) et les systèmes de recommandation. Ces modèles commencent généralement par une couche d'embedding (plongement lexical), qui associe un indice discret (par exemple, un jeton de mot) à un vecteur continu.

Sous FHE, le serveur ne peut pas effectuer d'accès mémoire standard basé sur un indice chiffré. La recherche doit donc être réalisée par le biais d'opérations arithmétiques homomorphes. Les approches existantes font face à un compromis :

1. Recherche côté client : Le client envoie le vecteur d'embedding chiffré. Cela entraîne une surcharge de communication massive proportionnelle à la dimension de l'embedding ($d$), ce qui est prohibitif pour de grandes tables (par exemple, GloVe avec 1,9 M de jetons).
2. Recherche côté serveur avec génération de vecteur "one-hot" : Le client envoie un scalaire d'indice chiffré compact. Le serveur doit alors construire homomorphiquement un vecteur "one-hot" pour sélectionner l'embedding. Les travaux antérieurs (Kim et al., ICML 2024) parviennent à cela en utilisant une fonction indicatrice chiffrée (EIF), mais cela nécessite $O(p \log p)$ opérations homomorphes (où $p$ est la taille de la table), consommant une profondeur multiplicative importante et devenant le coût dominant dans le pipeline d'inférence.

L'objectif est de réaliser une recherche d'embedding privée (PEL - Private Embedding Lookup) qui maintienne une communication client compacte (en envoyant uniquement un indice scalaire) tout en minimisant le coût de calcul homomorphe côté serveur, en évitant l'étape coûteuse de génération du vecteur "one-hot".

Méthodologie : Évaluation de vecteurs indépendants (IVE)

Les auteurs proposent l'Évaluation de Vecteurs Indépendants (IVE - Independent Vector Evaluation), une méthode qui contourne totalement la construction d'un vecteur "one-hot".

Intuition fondamentale

Le serveur n'a pas strictement besoin d'un vecteur "one-hot" ($e_j$) pour récupérer l'embedding $M_j$. Il a seulement besoin d'une représentation de l'indice $j$ qui soit linéairement indépendante à travers différents indices. Si un ensemble de vecteurs $\{v_j\}$ est linéairement indépendant, il existe une matrice de changement de base $L$ telle que $L v_j = e_j$. Par conséquent, la récupération de l'embedding peut être réécrite comme :
$$M_j = M e_j = M (L v_j) = (M L) v_j$$
Puisque $M$ et $L$ sont connus en clair, le serveur peut précalculer la matrice $M' = ML$. La tâche en ligne consiste alors à passer de la génération d'un vecteur "one-hot" à l'évaluation du vecteur $v_j$ de manière homomorphe.

Construction des vecteurs et stabilité

Pour garantir l'efficacité et la stabilité numérique sous le schéma CKKS (qui supporte l'arithmétique approximative) :

1. Efficacité : Les vecteurs $v_j$ sont construits à l'aide de puissances successives d'une valeur unique $\alpha_j$ chiffrée. Cela permet au serveur de générer les composantes du vecteur à l'aide d'opérations arithmétiques standards (multiplications) plutôt que de tests d'égalité complexes.
2. Stabilité : Pour éviter l'amplification de l'erreur lors du changement de base, la matrice $L$ doit être bien conditionnée (idéalement orthogonale). Les auteurs utilisent une matrice de Transformée en Cosinus Discrète (DCT). En utilisant des racines de l'unité et en séparant les parties réelles et imaginaires, ils construisent une base orthogonale qui s'aligne avec les capacités d'arithmétique complexe de CKKS.

Flux algorithmique

1. Client : Chiffre l'indice $j$ en une valeur $\alpha_j$ (dérivée de racines de l'unité) et la transmet comme une requête scalaire compacte.
2. Serveur (Phase IVE) :
   • Reçoit l' $\alpha_j$ chiffré.
   • Calcule les puissances $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ en utilisant un arbre de multiplication (profondeur logarithmique).
   • Sépare les parties réelles et imaginaires via la conjugaison pour former le vecteur $v_j$.
   • Ce processus nécessite $O(p)$ opérations homomorphes, une réduction significative par rapport au $O(p \log p)$ requis pour la génération "one-hot".
3. Serveur (Phase PCMM) :
   • Effectue une multiplication matrice-chiffrement de texte clair (PCMM - Plaintext-Ciphertext Matrix Multiplication) entre la matrice précalculée $M' = ML$ et le vecteur $v_j$ généré.
   • Cela produit le vecteur d'embedding chiffré.

Principales contributions

1. Évaluation de Vecteurs Indépendants (IVE) : Un nouvel algorithme qui remplace la génération de vecteur "one-hot" chiffré par l'évaluation d'une famille de vecteurs linéairement indépendants. Cela réduit la complexité de génération du vecteur de $O(p \log p)$ à $O(p)$ opérations homomorphes.
2. Base orthogonale via DCT : L'instanciation de l'IVE à l'aide d'une matrice orthogonale basée sur la DCT garantit la stabilité numérique, atténuant l'amplification de l'erreur inhérente à l'approximation CKKS lors de l'exécution du changement de base.
3. Pipeline PEL intégré : Les auteurs intègrent l'IVE avec la PCMM pour gérer efficacement les requêtes par lots. Ce pipeline permet de traiter simultanément plusieurs requêtes de jetons, en amortissant le coût sur les créneaux (slots) SIMD de CKKS.
4. Implémentation de bout en bout : La méthode est implémentée dans un pipeline de classification de texte de type FastText, démontrant sa viabilité pour des tâches d'inférence pratiques et sensibles à la confidentialité.

Résultats expérimentaux

Les auteurs ont évalué l'IVE-PEL par rapport à l'état de l'art précédent (Kim et al.) en utilisant trois jeux de données d'embeddings (GloVe.6B.50d, GloVe.42B.300d, et GPT-2) ainsi qu'une inférence FastText de bout en bout sur le jeu de données Enron-Spam.

• Accélération de la génération de vecteurs : L'IVE-PEL réduit considérablement le temps passé sur la génération de vecteurs. Pour une taille de sous-table de $\log p = 10$, le temps de VecGen est passé d'environ 424 ms (Kim et al.) à environ 3,15 ms (IVE-PEL) sur GloVe.6B.50d, ce qui représente une accélération de 134,6× dans cette étape spécifique.
• Accélération du pipeline total : Le temps de recherche amorti s'est amélioré de 18,5× à 78,4× selon le jeu de données et la dimension de l'embedding. Les gains les plus importants ont été observés dans les scénarios où la génération de vecteurs était le coût dominant.
• Profondeur multiplicative : L'IVE-PEL consomme environ 1/3 de la profondeur multiplicative requise par la méthode de génération "one-hot", permettant des tailles de sous-tables plus grandes et une meilleure qualité de compression sans épuiser le budget de bruit de CKKS.
• Impact de bout en bout : Dans la tâche de classification Enron-Spam, le remplacement de la méthode "one-hot" par l'IVE a réduit la part de la génération de vecteurs dans le temps total d'inférence chiffrée de 99,6 % à 66,3 %, abaissant ainsi considérablement la latence globale.

Signification et affirmations

L'article affirme que l'IVE-PEL répond au "point de conception manquant" de la recherche d'embedding privée : parvenir à une communication client compacte (indices scalaires) sans subir le coût prohibitif côté serveur de la génération de "one-hot" homomorphe.

En découplant le besoin d'une base "one-hot" du processus de recherche, les auteurs démontrent que la recherche d'embedding privée peut devenir pratique pour des clients légers et des modèles à grande échelle. Les résultats suggèrent que l'IVE-PEL rend l'embedding côté serveur viable, permettant une inférence respectueuse de la vie privée pour les modèles de NLP et de recommandation sans sacrifier la confidentialité des indices d'entrée de l'utilisateur. La méthode maintient la précision des modèles sous-jacents (comme en témoignent les résultats de classification de sentiment IMDB et de détection de spam) tout en améliorant considérablement l'efficacité de calcul.