💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

Cet article introduit les Sparse Roots of Unity (SPRU), un nouvel algorithme de bootstrapping pour le schéma de chiffrement homomorphe CKKS qui intègre l'arithmétique modulaire dans les racines de l'unité complexes afin de réduire considérablement la profondeur multiplicative et d'obtenir une amélioration de la latence allant jusqu'à 5 fois par rapport aux méthodes traditionnelles.

Auteurs originaux : Jean-Sebastien Coron, Robin Koestler

Publié 2026-07-31

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jean-Sebastien Coron, Robin Koestler

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'envoyer un message secret à un ami, mais que vous ne pouvez pas faire confiance à la poste. Vous verrouillez votre lettre dans une boîte, mais la poste doit la trier, l'empiler et peut-être même l'ouvrir pour vérifier l'adresse sans jamais voir ce qu'il y a à l'intérieur. C'est toute la magie du Chiffrement Homomorphe Total (FHE). Cela permet aux ordinateurs d'effectuer des calculs sur des données qui sont encore verrouillées sous leur forme chiffrée. Pensez à cela comme une cuisine magique où vous pouvez préparer un gâteau en utilisant des ingrédients qui sont encore dans leurs emballages scellés et non ouverts ; le four fait le travail, et quand vous ouvrez enfin la boîte à la fin, vous avez un gâteau frais, mais le four n'a jamais su quels étaient les ingrédients.

Cependant, il y a un piège. Chaque fois que l'ordinateur effectue une opération mathématique sur ces données verrouillées, un peu de « bruit » ou de statique est ajouté à la boîte, comme de la poussière se déposant sur une lentille. Si vous effectuez trop de calculs, le bruit devient si fort que le message devient brouillé et illisible. Pour corrir cela, les scientifiques utilisent un processus appelé bootstrapping. C'est comme un bouton de réinitialisation magique : l'ordinateur prend la boîte verrouillée et bruyante, réalise un tour de magie complexe pour nettoyer la poussière, et remet le message dans une boîte neuve et propre afin que les calculs puissent continuer. Le problème est que ce tour de nettoyage est incroyablement lent et lourd, comme essayer de laver une voiture avec une brosse à dents. Cela demande tellement de puissance de calcul que cela ralentit tout, rendant les applications réelles très poussives.

C'est ici qu'intervient un nouvel article de Jean-Sébastien Coron et Robin Köstler. Ils introduisent une nouvelle façon astucieuse d'effectuer ce processus de « nettoyage », appelée le bootstrapping par Racines de l'Unité Creuses (SPRU). Au lieu d'utiliser l'ancienne méthode lourde qui tente d'approcher une courbe complexe (comme une onde sinusoïdale) pour nettoyer les données, ils ont trouvé un moyen de mapper les données directement sur un cercle de nombres appelés « racines de l'unité ». Imaginez qu'au lieu de frotter la voiture avec une brosse à dents, vous faites simplement glisser la voiture sur un immense carrousel tournant qui essuie naturellement la poussière pendant qu'il tourne. Leur méthode est beaucoup plus rapide et légère, surtout lorsque vous traitez un petit nombre d'éléments de données à la fois. En utilisant cette nouvelle approche, ils ont montré que le temps nécessaire pour réinitialiser le chiffrement peut être réduit jusqu'à 5 fois par rapport à la méthode standard, faisant de l'informatique secrète un processus qui ressemble beaucoup plus à une réalité qu'à un rêve lointain.

L'ancienne méthode : Le porteur de charge

Pour comprendre pourquoi ce nouveau tour est si spécial, regardons comment fonctionnait l'ancienne méthode. Dans le schéma de chiffrement CKKS standard (le plus populaire pour effectuer des calculs sur des décimales), le processus de bootstrapping était comme essayer de deviner la forme d'une montagne en dessinant une ligne lisse au-dessus d'elle. L'ordinateur devait évaluer un polynôme compliqué (une formule mathématique sophistiquée) qui approchait une « réduction modulaire ». Considérez la réduction modulaire comme une façon d'enrouler une longue ligne numérique en un cercle pour qu'elle rentre de nouveau dans une petite boîte. L'ancienne méthode essayait de dessiner une onde sinusoïdale (une ligne ondulée) pour imiter ce processus d'enroulement.

Bien que cela fonctionne, c'était un effort colossal. Cela nécessitait une pile profonde d'opérations mathématiques, ce qui signifiait que l'ordinateur devait utiliser une très grande « dimension d'anneau » (une mesure de la taille du terrain de jeu mathématique). C'était comme essayer de courir un marathon en portant un sac à dos très lourd ; cela ralentissait tout et limitait la quantité de travail utile pouvant être accompli après la réinitialisation. Les auteurs soulignent que cette haute « profondeur multiplicative » (le nombre de couches de mathématiques par lesquelles vous devez passer) était le principal goulot d'étranglement, rendant le processus trop lent pour une utilisation pratique, surtout si vous ne vouliez traiter que quelques nombres à la fois.

La nouvelle méthode : Le carrousel des racines

La nouvelle idée des auteurs, le bootstrapping SPRU, change la donne en sautant l'approximation lourde. Au lieu d'essayer de dessiner une ligne ondulée pour imiter l'enroulement, ils ont réalisé qu'ils pouvaient simplement incorporer les données directement sur les « racines de l'unité ».

Voici une analogie simple : imaginez que l'ancienne méthode consistait à essayer de traduire un code secret en écrivant une entrée de dictionnaire longue et compliquée pour chaque lettre. Cela prenait une éternité. La nouvelle méthode consiste à réaliser que le code secret est en fait un ensemble de clés qui s'insèrent parfaitement dans une serrure spécifique. Au lieu de traduire, vous tournez simplement la clé.

En termes techniques, ils mappent le groupe additif (la façon dont les nombres s'additionnent) directement dans les racines de l'unité complexes (des points sur un cercle dans le système de nombres complexes). Comme le schéma de chiffrement CKKS comprend nativement ces nombres complexes, l'ordinateur peut effectuer l'opération de « nettoyage » directement, sans avoir besoin d'approximer une onde sinusoïdale. C'est comme passer de la construction d'un pont avec des briques individuelles à l'utilisation d'un arc préfabriqué qui s'ajuste parfaitement.

La recette secrète : Parcimonie et Emballage

L'article ne s'arrête pas seulement à cette nouvelle carte ; ils ont également introduit deux optimisations astucieuses pour rendre le processus encore plus rapide, surtout lorsqu'on traite un petit nombre de créneaux de données (comme quelques nombres dans une liste).

L'emballage des bits : Autrefois, si vous aviez une clé secrète de 1 000 bits, l'ordinateur devait traiter chaque bit un par un. Les auteurs ont réalisé qu'ils pouvaient « emballer » ces bits dans les créneaux du chiffrement, comme si l'on fourrait 1 000 lettres dans une seule boîte aux lettres ultra-efficace. Cela a réduit le nombre de calculs lourds nécessaires d'un montant massif à un montant logarithmique (pensez à réduire une longue liste en un court résumé).
L'astuce du bloc parcimonieux : Ils ont également supposé que la clé secrète avait une structure spéciale : au lieu de bits aléatoires, la clé était divisée en blocs où un seul bit de chaque bloc était un « 1 » et les autres étaient des « 0 ». C'est comme avoir une rangée d'interrupteurs où un seul est allumé dans chaque groupe de dix. En utilisant cette structure « parcimonieuse » (sparse), ils ont pu remplacer de nombreuses étapes de multiplication difficiles par de simples étapes d'addition. C'est la différence entre multiplier une longue liste de nombres et simplement en additionner quelques-unes. Cela a réduit la « profondeur » du calcul encore davantage, passant d'une tour profonde à un petit escalier.

Les résultats : Accélérer la magie

Les auteurs ont testé leur nouvelle méthode en utilisant la bibliothèque OpenFHE, un outil populaire pour construire des logiciels de chiffrement. Ils ont comparé leur bootstrapping SPRU à la méthode originale, plus lourde.

Les résultats sont frappants pour des scénarios spécifiques. Lorsque l'on effectue le bootstrapping de chiffrements avec un petit nombre de créneaux (ce qui est courant dans de nombreuses applications réelles), leur nouvelle méthode est jusqu'à 5 fois plus rapide (une réduction de la latence de 5x). C'est un événement majeur car cela signifie que le « bouton de réinitialisation » n'a plus besoin d'attendre si longtemps, permettant à l'ordinateur de se remettre beaucoup plus vite à effectuer un travail utile.

Cependant, l'article note prudemment que ce n'est pas une solution miracle pour chaque situation. Si vous essayez de traiter un nombre massif de créneaux (une liste énorme de données), la méthode originale pourrait encore être plus efficace. Mais pour de nombreux cas où nous traitons de plus petits lots de données, cette nouvelle approche offre une accélération significative.

Pourquoi c'est important

La beauté de ce travail est qu'il ne se contente pas de peaufiner les chiffres ; il change fondamentalement notre façon de concevoir le processus de bootstrapping. En s'éloignant des approximations polynomiales lourdes pour embrasser les capacités natives du schéma de chiffrement, les auteurs ont montré que nous pouvons rendre le chiffrement homomorphe total beaucoup plus pratique.

Ils ont prouvé qu'en utilisant ces « racines de l'unité » et des techniques d'emballage intelligentes, nous pouvons réduire considérablement le temps et la puissance de calcul nécessaires pour maintenir les données chiffrées utilisables. Bien que l'article se concentre sur les détails techniques et les mathématiques sous-jacentes, l'idée principale est claire : le rêve de réaliser des calculs complexes sur des données secrètes sans ralentir est un peu plus proche de la réalité. Les auteurs ont fourni une nouvelle méthode, plus légère et plus rapide, pour maintenir la magie vivante, rendant possible l'idée d'un futur où vos données privées peuvent être traitées dans le cloud sans jamais être vues, et sans attendre indéfiniment le résultat.

Résumé Technique : Bootstrapping à Faible Latence pour CKKS utilisant les Racines de l'Unité

Énoncé du Problème

Le schéma de chiffrement homomorphe CKKS supporte l'arithmétique approximative sur des nombres complexes, ce qui le rend adapté à l'apprentissage automatique sécurisé et au calcul en nuage (cloud computing). Cependant, une étape critique de CKKS est la procédure de bootstrapping, nécessaire pour rafraîchir les ciphertext et permettre une profondeur de calcul illimitée.

La méthode de bootstrapping originale de CKKS [CHK+18a] repose sur l'évaluation homomorphe d'une approximation polynomiale de la fonction de réduction modulaire (plus précisément, une fonction sinus mise à l'échelle). Cette approche souffre de deux inconvénients majeurs :

Profondeur Multiplicative Élevée : L'approximation polynomiale nécessite un circuit profond, ce qui nécessite un grand module de ciphertext.
Inefficacité pour de Faibles Nombres de Slots : La complexité de la méthode originale dépend du nombre de slots ( $n$ ) et de la dimension de l'anneau ( $N$ ), nécessitant souvent $O(\log n + \log N)$ opérations. Cette profondeur élevée force l'utilisation de dimensions d'anneau plus grandes pour maintenir la sécurité, entraînant une latence accrue.

Les auteurs identifient la nécessité d'un algorithme de bootstrapping qui réduit la profondeur multiplicative, permettant ainsi des dimensions d'anneau plus petites et une latence nettement plus faible, particulièrement pour les ciphertexts avec un petit nombre de slots.

Méthodologie : Sparse Roots of Unity (SPRU)

L'article introduit le bootstrapping par Racines de l'Unité Creuses (SPRU), un nouvel algorithme qui change fondamentalement la manière dont la réduction modulaire est effectuée dans CKKS.

Concept Central : Imbrication Native

Au lieu d'approximer la réduction modulaire via une fonction sinus, le bootstrapping SPRU intègre directement le groupe additif $\mathbb{Z}_q$ dans le groupe multiplicatif des racines de l'unité complexes. Les auteurs utilisent l'homomorphisme :
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

Pour une équation de déchiffrement de type LWE $m = \langle s, c \rangle \pmod q$ , les auteurs observent que :
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Puisque les bits de la clé secrète $s_k \in \{0, 1\}$ agissent comme des sélecteurs, ce produit peut être réécrit comme :
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
En isolant la partie imaginaire et en appliquant un facteur d'échelle linéaire, le message original $m$ peut être récupéré. Cette équation peut être évaluée homomorphiquement au sein du schéma CKKS sans l'approximation polynomiale de la fonction sinus.

Optimisations Clés

Pour rendre cette approche pratique, les auteurs introduisent deux optimisations critiques :

Packing des Bits de la Clé Secrète :
Au lieu de chiffrer chaque bit de la clé secrète individuellement, les $N$ bits sont regroupés (packed) dans les $N/2$ slots de deux ownfaits de CKKS. Les termes $(\exp(2i\pi \cdot c_k/q) - 1)$ sont également regroupés. Le produit de ces termes est calculé à l'aide de l'Opérateur de Produit ( $Pr_{N/2 \to 1}$ ), ce qui réduit le nombre de multiplications homomorphiques de $O(N)$ à $O(\log N)$ .
Clé Secrète à Blocs Creux (Sparse Block Secret Key) :
Les auteurs supposent une clé secrète structurée $s$ divisée en $h$ blocs de taille $B = N/h$ , où chaque bloc contient exactement un bit non nul (un '1'). Cette structure permet de remplacer le produit au sein de chaque bloc par une somme.
- La somme au sein des blocs est calculée à l'aide de l'Opérateur de Trace ( $Tr_{N/2 \to h}$ ), qui n'implique que des additions et des automorphismes (pas de profondeur multiplicative).
- Le produit final est pris sur les $h$ résultats de blocs.
- Résultat : La profondeur multiplicative est réduite de $\log_2 N + 2$ à $\log_2 h + 1$ . Puisque $h \ll N$ , cela abaisse considérablement la taille du module requis.

Extension à de Multiples Slots

La méthode est généralisée pour gérer $n$ slots (où $n \le N/2$ ). La matrice de déchiffrement est extraite, et l'équation de bootstrapping est appliquée en parallèle à chaque composante de message des $n$ slots. La complexité est de $O(n + \log N)$ , ce qui est asymptotiquement plus élevé que le bootstrapping CKKS original ( $O(\log n + \log N)$ ) pour de grands $n$ . Cependant, pour de petits $n$ , la réduction de la profondeur multiplicative offre des performances pratiques supérieures.

Contributions Clés

Algorithme de Bootstrapping SPRU : Une nouvelle technique de bootstrapping pour CKKS qui remplace l'approximation par fonction sinus par l'évaluation native des racines de l'unité.
Réduction de la Profondeur Multiplicative : En exploitant les clés secrètes à blocs creux et l'opérateur de trace, l'algorithme atteint une profondeur multiplicative de $O(\log h)$ , nettement inférieure au $O(\log N)$ de la méthode originale.
Implémentation Optimisée : Les auteurs fournissent une implémentation open-source utilisant la bibliothèque C++ OpenFHE, démontrant la compatibilité avec l'arithmétique du Système de Nombres Résiduels (RNS) et les optimisations existantes de transformation linéaire (SlotToCoeff).
Analyse de Sécurité : Une analyse formelle de la distribution de la clé binaire par blocs, montrant qu'elle ne fragilise pas la sécurité du problème RLWE contre les attaques connues (attaques hybrides duales et meet-in-the-middle), à condition que les paramètres soient ajustés correctement.

Résultats

Les auteurs ont testé le bootstrapping SPRU par rapport au bootstrapping CKKS original en utilisant la bibliothèque OpenFHE avec des paramètres de sécurité de 128 bits.

Réduction de la Latence : Pour les ciphertexts avec un petit nombre de slots, le bootstrapping SPRU permet d'obtenir jusqu'à une réduction de 5 fois de la latence.
Efficacité : La réduction de la profondeur multiplicative permet l'utilisation de dimensions d'anneau plus petites, contribuant davantage à l'accélération.
Parallélisme : La méthode est hautement parallélisable ; avec $n$ processeurs, elle peut atteindre une complexité de $O(\log N)$ comparable à la méthode originale.

Signification et Revendications

L'article affirme que le bootstrapping SPRU offre une alternative pratique au bootstrapping CKKS original, ciblant spécifiquement les scénarios où la faible latence est critique et le nombre de slots est faible. En évitant les approximations polynomiales coûteuses et en réduisant la profondeur multiplicative, la méthode permet un rafraîchissement plus efficace des ownfaits.

Les auteurs positionnent leur travail comme une étape significative vers la viabilité du chiffrement totalement homomorphe pour des applications réelles nécessitant un bootstrapping fréquent. Ils notent que bien que leur méthode soit optimisée pour de petits nombres de slots, elle complète les travaux existants (tels que le travail indépendant de Cheon et al. [CHKS25] qui se concentre sur le bootstrapping complet de $N/2$ slots) en offrant un compromis différent privilégiant la latence par rapport au parallélisme massif pour de petits ensembles de données.

L'article conclut que la réduction de la profondeur multiplicative est le principal moteur de l'efficacité, libérant plus de niveaux de calcul pour des opérations utiles après le bootstrapping et permettant l'utilisation de dimensions d'anneau plus petites et plus rapides.