Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

Résumé Technique : Transformation Linéaire à Pas de Bébé et Géant Triple-Hoistée sur le Chiffrement Homomorphe CKKS et Accélérateur Matériel

Énoncé du Problème
Le chiffrement homomorphe (HE), en particulier le schéma CKKS, permet des calculs préservant la vie privée sur des données chiffrées, ce qui est crucial pour des applications telles que le diagnostic médical, l'analyse financière et le séquençage du génome. Une opération fondamentale dans les réseaux de neurones et les transformateurs basés sur le HE est la Transformation Linéaire (HE-LT). Bien que la méthode diagonale permette la HE-LT en emballant les diagonales de matrices dans des polynômes, elle nécessite un nombre prohibitif de rotations de chiffrés pour les matrices de haute dimension. Ces rotations impliquent des opérations complexes d'automorphisme et de commutation de clés, entraînant une surcharge computationnelle significative et un accès massif à la mémoire hors puce. Les accélérateurs matériels existants, même ceux utilisant la décomposition Pas de Bébé et Géant (BSGS) et des techniques à double hoisting, souffrent toujours de latences substantielles et de goulots d'étranglement de bande passante mémoire, nécessitant souvent des centaines de gigaoctets de transfert de données hors puce pour des ensembles de paramètres typiques.

Méthodologie
L'article propose une solution complète adressant à la fois la complexité algorithmique et le flux de données matériel :

1. Algorithme BSGS Triple-Hoisté (TH-BSGS) :
   Les auteurs étendent l'algorithme BSGS à double hoisting existant en décomposant davantage le « pas de bébé » en deux couches, créant une structure à trois couches ($n = n'_1 n'_2 n'_3$).

   • Triple Hoisting : La technique est appliquée sur les trois couches de rotations. En réorganisant les calculs et en appliquant des automorphismes inverses aux clés de commutation, l'algorithme garantit que l'opération Decompose (une étape coûteuse de commutation de clés) n'est effectuée qu'une seule fois pour toutes les rotations internes d'une couche.
   • ModDown Différé : De manière similaire aux méthodes de hoisting précédentes, les opérations ModDown sont différées et combinées. Dans la conception proposée, ModDown est appliqué uniquement aux sommes accumulées plutôt qu'aux produits intermédiaires, réduisant considérablement le nombre d'opérations modulaires requises.
   • Flexibilité des Compromis : En ajustant les facteurs de décomposition $n'_1, n'_2, n'_3$, l'algorithme permet des compromis flexibles entre le nombre de clés de commutation requises (mémoire) et la complexité computationnelle.

2. Chemin de Données Optimisé Mémoire :
   Pour adresser la latence causée par l'accès à la mémoire hors puce, l'algorithme TH-BSGS est partitionné en six phases distinctes.

   • Partitionnement des Phases : L'algorithme est restructuré afin que les données soient lues depuis la mémoire hors puce, traitées avec des résultats intermédiaires stockés et réutilisés sur puce, et réécrites uniquement à la fin de chaque phase.
   • Réutilisation des Données : La conception maximise la réutilisation de la mémoire sur puce en planifiant soigneusement le chargement des clés de commutation et des membres de polynômes. Par exemple, dans les couches intermédiaires, les clés de commutation sont chargées dans la mémoire sur puce et réutilisées sur plusieurs itérations pour minimiser le trafic.
   • Ajustement du Parallélisme : Six paramètres de parallélisme ($m_1$ à $m_6$) sont introduits pour équilibrer le traitement des clés de commutation, des membres de polynômes et des chiffrés, garantissant que la conception s'adapte aux contraintes de la mémoire sur puce FPGA (par exemple, 43 Mo sur Xilinx U280).

3. Architecture de l'Accélérateur Matériel :
   Un accélérateur basé sur FPGA efficace est conçu pour implémenter l'algorithme proposé.

   • Circuit de Permutation Optimisé : Un circuit de permutation novateur est introduit pour implémenter l'automorphisme $\phi_r$. En exploitant les propriétés spécifiques de l'automorphisme dans le domaine NTT et l'ordre de stockage inversé par bits des coefficients, la conception réduit le nombre de multiplexeurs de moitié par rapport à l'état de l'art et élimine le besoin de tampons de mémoire scratchpad. Cela réduit de moitié la latence de l'opération de permutation.
   • Composants Modulaires : L'architecture comprend un tableau d'Éléments de Traitement (PE) supportant le NTT, l'INTT et les opérations élément par élément ; un tableau d'Adder en Arbre (TA) pour les sommes ; et un tableau de Circuit de Permutation (PC).

Contributions Clés

• Innovation Algorithmique : La proposition de l'algorithme BSGS Triple-Hoisté, qui décompose davantage le pas de bébé pour réduire le nombre de rotations de chiffrés et d'opérations Decompose par rapport à l'approche à double hoisting.
• Optimisation du Chemin de Données : Une stratégie d'optimisation mémoire basée sur les phases qui réduit drastiquement le trafic mémoire hors puce en maximisant la réutilisation des données sur puce, spécifiquement adaptée aux calculs réorganisés de l'algorithme TH-BSGS.
• Efficacité Matérielle : Le développement d'un accélérateur matériel doté d'un circuit de permutation simplifié qui réduit la latence d'automorphisme de 50 % et élimine le tamponnage mémoire supplémentaire.

Résultats Expérimentaux
La conception a été synthétisée sur des dispositifs Xilinx Virtex UltraScale+ (U280) et évaluée par rapport aux accélérateurs matériels de l'état de l'art (incluant FAME, CHAM et des conceptions de [25]) sous trois ensembles de paramètres HE différents (Set-A, Set-B, Set-C) supportant une sécurité de 128 bits.

• Accès à la Mémoire Hors Puce : La conception proposée réduit l'accès à la mémoire hors puce de 2,9 à 4,2 fois par rapport à la meilleure conception antérieure (FAME) dans les mêmes paramètres. Par rapport à la méthode diagonale, les améliorations atteignent jusqu'à 10,6 fois en réduction d'accès mémoire.
• Latence Computationnelle : L'accélérateur proposé réalise une réduction de 2,9 à 10,6 fois de la latence computationnelle par rapport aux accélérateurs matériels antérieurs.
• Utilisation des Ressources : La conception maintient des exigences en ressources matérielles (LUT, FF, DSP, BRAM) comparables ou légèrement meilleures que les solutions existantes, malgré les gains de performance significatifs.
• Comparaison Algorithmique : Bien que l'algorithme TH-BSGS réduise l'exigence mémoire pour les clés de commutation d'environ 3,65 fois par rapport à l'algorithme BSGS à double hoisting (DH-BSGS), la complexité computationnelle globale reste similaire à celle du DH-BSGS et du BSGS, car les multiplications de polynômes dominent la complexité totale.

Signification
L'article affirme que l'algorithme TH-BSGS proposé et son accélérateur matériel associé représentent une avancée significative dans l'efficacité de la HE-LT. En adressant simultanément la surcharge algorithmique de la commutation de clés et le goulot d'étranglement matériel de l'accès à la mémoire hors puce, la conception permet des transformations linéaires préservant la vie privée plus rapides et plus évolutives. La réduction du trafic mémoire hors puce est particulièrement critique, car les transferts de données constituent la majorité de la latence dans les opérations HE-LT. Le travail démontre qu'une décomposition supplémentaire du pas de bébé, combinée à une optimisation rigoureuse du chemin de données et à un matériel spécialisé, peut produire des améliorations de performance substantielles sans augmenter les coûts de ressources matérielles. Il est noté que les travaux futurs se concentreront sur l'optimisation supplémentaire des transformations linéaires pour des applications spécifiques.