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

Résumé Technique : Scans de Préfixes Non Commutatifs Optimaux en Rotation dans les Dispositions à Bit Inversé

Énoncé du Problème

Dans le chiffrement homomorphe (HE) compacté, spécifiquement le schéma CKKS, les opérations SIMD permettent le calcul parallèle sur des vecteurs chiffrés. Cependant, la communication entre les créneaux (slots) nécessite des rotations cycliques (automorphismes de Galois), qui sont des opérations coûteuses impliquant le changement de clé (key switching). Le coût d'une rotation dépend de la disposition physique des données.

Le présent article traite du problème de l'exécution de calculs de préfixes ordonnés (scans) sur $n = 2^m$ éléments d'un monoïde associatif, potentiellement non commutatif, lorsque les données sont stockées dans un ordre de bit inversé (bit-reversed order). Cette disposition est courante dans les transformées rapides et les conversions de mise en paquet (packing).

Le défi central est qu'un scan classique de « prédécesseur transporté » (qui double récursivement la distance vers les prédécesseurs logiques) induit un coût de routage élevé dans une disposition à bit inversé. Parce que l'inversion de bits permute les indices logiques, un décalage logique unique par $2^t$ se décompose en plusieurs classes de déplacements cycliques distinctes. Par conséquent, une implémentation directe nécessite $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotations. Les auteurs étudient si ce coût triangulaire est une propriété inhérente au calcul de préfixe dans les dispositions à bit inversé ou un artefact de la topologie de routage spécifique.

Méthodologie et Construction

L'article introduit un invariant de réplication-agrégation pour réduire le nombre de rotations d'un ordre quadratique à un ordre linéaire.

1. Réplication Sémantique : Au lieu de router chaque créneau vers son prédécesseur logique exact, la construction maintient un état où chaque créneau au sein d'un bloc logique aligné stocke l'agrégat complet de ce bloc.
2. Échange de Blocs Frères (Sibling-Block Exchange) : À chaque niveau $d$ du scan (combinant des blocs de taille $2^d$), l'algorithme effectue une rotation de l'état agrégé selon un décalage spécifique $s_d = 2^{m-d-1}$.
   • Sous l'inversion de bits, les deux enfants d'un bloc parent occupent des cosets physiques séparés exactement par $s_d$.
   • Une rotation par $s_d$ mappe un créneau vers une position dans le bloc frère. Comme l'agrégat du frère est répliqué à travers tous ses créneaux, n'importe quelle position dans le bloc frère fournit la valeur sémantique correcte.
   • Cela permet à une seule rotation cyclique dirigée de fournir les agrégats valides pour les deux orientations d'enfants simultanément, préservant la correction pour les monoïdes non commutatifs via des masques publics qui sélectionnent l'ordre des opérandes.
3. Formulation de Scan Exclusif : Les auteurs implémentent un scan exclusif (produisant le préfixe avant l'élément actuel). Cela évite la nécessité d'un décalage final du prédécesseur logique pour récupérer la retenue entrante pour la correction de chiffre, une exigence qui réintroduirait autrement un routage sensible à la disposition.
4. Preuves de Bornes Inférieures : L'article établit que $m$ rotations est une borne inférieure globale pour tout circuit calculant une sortie dépendant de toutes les $2^m$ entrées dans ce modèle. La preuve repose sur un argument de somme de sous-ensembles : si $R$ rotations sont utilisées, au plus $2^R$ déplacements d'entrée distincts peuvent atteindre une sortie fixe. Pour couvrir l'ensemble des $2^m$ entrées, $R \ge m$ est nécessaire. De plus, l'article prouve que l'atteinte de cette borne nécessite que les décalages de rotation forment une base 2-adique complète (un décalage pour chaque valuation $0, \dots, m-1$).

Contributions Clés

1. Construction de Scan Optimale : Un algorithme de scan inclusif et exclusif qui atteint $R = m$ rotations et une profondeur de monoïde $D = m$ pour les dispositions à bit inversé. Cela réduit le nombre de rotations de l'ordre direct $O(m^2)$ à $O(m)$.
2. Rigidité de l'Optimalité : Une caractérisation de tous les circuits optimaux. Si un circuit utilise exactement $m$ rotations, les décalages doivent former une base 2-adique complète. Cela prouve que le profil de rotation est rigide, même si la topologie du circuit varie.
3. Frontière Rotation-Clé : Une analyse du compromis entre le nombre de décalages directement clés ($K$) et le nombre d'appels de rotation en ligne ($R$).
   • L'article dérive une borne inférieure de produit : $\prod (c_j + 1) \ge 2^m$, où $c_j$ est le nombre de fois que la clé $j$ est utilisée.
   • Lorsque $K$ divise $m$, la frontière exacte est prouvée être $R^* = K \cdot (2^{m/K} - 1)$.
4. Instanciation Radix-CKKS : Application du scan exclusif à la propagation exacte des retenues et des emprunts dans le mode radix de CKKS. Cela permet l'arithmétique modulaire et la comparaison d'entiers sans restaurer l'ordre naturel ou effectuer un décalage final.
5. Efficacité du Batching : Démonstration que les économies de rotation sont maintenues pour les entrelacements de type digit-major entièrement occupés, où $g$ entiers indépendants sont empaquetés dans un seul ciphertext sans multiplier le nombre de rotations.

Résultats et Évaluation

Les auteurs ont implémenté l'algorithme dans Lattigo (Go) et l'ont comparé à deux bases de référence :

1. Prédécesseur Direct à Bit Inversé : L'approche naïve de rotation $O(m^2)$.
2. Normaliser–Scanner–Restaurer (Normalize–Scan–Restore) : Une base de référence qui convertit les données vers l'ordre naturel, effectue le scan, puis reconvertit.

Principales conclusions à $m=7$ (128 créneaux) :

• Rotations : Réduites de 28 (direct) à 7 (répliqué).
• Clés d'évaluation : Stockage réduit de 70,0 % (908,6 Mo $\to$ 272,6 Mo).
• Mémoire : Utilisation de la mémoire vive (heap) réduite de 63,9 % (2,30 Go $\to$ 830,5 Mo).
• Latence : Le scan répliqué a amélioré la latence isolée du scan de 19,9 % par rapport à la méthode du prédécesseur direct.
• Pipeline de bout en bout : Dans un pipeline en aval de profondeur 5, le scan répliqué a évité une opération de bootstrapping complète requise par la base de référence normalize-restore. Cela a produit une accélération moyenne appariée de 4,31$\times$ (IC à 95 % [3,69, 4,92]).

L'article note que bien que la méthode « normalize–scan–restore » présente une latence isolée plus faible pour de petits $m$ en raison de moins de compositions de monoïdes, le scan répliqué devient plus rapide pour $m \ge 5$ et offre une efficacité de ressources supérieure (clés, mémoire, niveaux de module).

Signification et Revendications

L'article affirme que préserver une représentation SIMD à bit inversé n'impose pas un surcoût de rotation inévitable pour le calcul de préfixe ordonné. La signification réside dans :

• Briser la barrière quadratique : Prouver que le coût $O(m^2)$ du routage direct dans les dispositions à bit inversé n'est pas inhérent mais peut être réduit à la borne théorique de $O(m)$ via la réplication sémantique.
• Compromis de Ressources : Établir que la réduction du coût de routage (rotations) et du stockage des clés se fait au prix d'un travail de monoïde empaqueté accru ($2m-1$ compositions contre $m$) et d'un second vecteur d'état vivant. L'article soutient que ce compromis est favorable pour les pipelines profonds où les niveaux de module et le bootstrapping sont des goulots d'étranglement.
• Exactitude : Fournir des bornes inférieures exactes et des caractérisations de frontières pour la gestion des clés de rotation, allant au-delà des optimisations heuristiques pour atteindre des limites prouvables pour des schémas de dépendance spécifiques.

Ce travail est présenté comme une optimisation spécifique de la contrainte de disposition à bit inversé, distincte de la théorie générale des réseaux de préfixes, et est validé par une évaluation combinatoire rigoureuse et une évaluation empirique dans une implémentation standard de CKKS.