💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Ce papier propose une méthode de multiplication de chiffrés multi-entrées optimisée pour le chiffrement homomorphe qui dépasse deux entrées grâce à des calculs reformulés, des clés d'évaluation supplémentaires et une approche de redimensionnement multi-niveaux, aboutissant à des architectures matérielles qui réduisent considérablement la surface logique et la latence par rapport aux conceptions antérieures.

Auteurs originaux : Sajjad Akherati, Xinmiao Zhang

Publié 2026-05-19

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sajjad Akherati, Xinmiao Zhang

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 êtes un chef étoilé essayant de faire un gâteau, mais il y a un piège : vous devez tout mélanger et cuire en portant des gants de four épais et lourds qui vous empêchent de sentir les ingrédients ou de voir le bol. C'est le Chiffrement Homomorphe (HE). Il permet aux ordinateurs d'effectuer des calculs mathématiques sur des données « chiffrées » (la pâte à gâteau dans les gants) sans jamais les déchiffrer (enlever les gants). Cela garde les secrets en sécurité, qu'il s'agisse de vos dossiers médicaux ou de votre solde bancaire.

Cependant, faire des mathématiques avec ces « gants » est incroyablement lent et désordonné. Le goulot d'étranglement principal est la multiplication. Dans le chiffrement standard, vous ne pouvez multiplier que deux ingrédients à la fois. Mais de nombreuses tâches modernes, comme entraîner une IA à reconnaître une maladie ou analyser des tendances financières complexes, nécessitent de multiplier beaucoup d'ingrédients (textes chiffrés) ensemble en une seule fois.

Cet article présente une nouvelle méthode, ultra-efficace, pour multiplier ces ingrédients chiffrés, spécifiquement pour une méthode de chiffrement populaire appelée CKKS. Voici la décomposition de leur percée en utilisant des analogies simples :

1. Le Problème : La « Cuisine Désordonnée »

Lorsque vous multipliez des nombres chiffrés, le « bruit » (le désordre créé par les gants de four) devient de plus en plus fort. Si vous multipliez trop de nombres à la fois sans nettoyer, le bruit noie les données réelles et le résultat devient inexploitable.

Pour corriger cela, le système de chiffrement doit effectuer une étape de « nettoyage » appelée Redimensionnement (Rescaling) après chaque multiplication. Pensez-y comme s'arrêter pour essuyer le comptoir et remettre les ingrédients en ordre.

L'Ancienne Méthode : Si vous deviez multiplier 10 ingrédients, l'ancienne méthode était comme un convoyeur où vous multipliez deux, vous arrêtez pour nettoyer, vous multipliez deux autres, vous arrêtez pour nettoyer, et ainsi de suite. C'était lent et nécessitait beaucoup de produits de nettoyage (ressources matérielles).
La Tentative Précédente « Trois Ingrédients » : Le travail antérieur des auteurs montrait qu'on pouvait multiplier trois ingrédients à la fois, ce qui était plus rapide. Mais cela comportait encore beaucoup d'étapes de nettoyage inutiles.

2. La Solution : La « Chaîne de Montage Intelligente »

Les auteurs proposent deux améliorations majeures pour rendre ce processus plus rapide et plus compact :

A. Le « Nettoyage en Une Seule Étape » (Multiplication à 3 Entrées Améliorée)

Dans leur nouvelle conception pour multiplier trois ingrédients, ils ont réalisé qu'ils effectuaient le nettoyage (Redimensionnement) et le réarrangement (Relinearisation) d'une manière maladroite et détournée.

L'Analogie : Imaginez que vous avez trois bols de pâte. L'ancienne méthode consistait à les mélanger, verser le mélange dans un nouveau bol, nettoyer les vieux bols, verser le mélange à nouveau, et nettoyer à nouveau.
La Correction : Ils ont redessiné le processus pour que vous puissiez mélanger et nettoyer en un seul mouvement fluide. Ils ont trouvé comment combiner les étapes de nettoyage afin que vous n'ayez pas à vous arrêter et à essuyer le comptoir autant de fois.
Le Résultat : Leur nouveau « mixeur à trois bols » est 50 % plus rapide (latence) et occupe 15 % moins d'espace sur la puce (surface) par rapport à leur meilleure conception précédente.

B. Le « Nettoyage de Groupe » (Multiplication Multi-Entrées)

Que se passe-t-il si vous devez multiplier quatre, cinq, ou même douze ingrédients à la fois ?

L'Ancienne Méthode : Vous construiriez une longue file de « mixeurs à deux bols ». Vous mélangez deux, nettoyez, mélangez deux autres, nettoyez, puis mélangez les résultats, nettoyez à nouveau. Cela crée une file très longue (une grande « profondeur multiplicative »), ce qui signifie que le bruit s'accumule trop vite.
La Nouvelle Stratégie : Les auteurs ont réalisé que si vous regroupez vos ingrédients différemment, vous pouvez effectuer un « Nettoyage de Groupe ».
- Au lieu de nettoyer après chaque étape unique, ils ont développé une astuce mathématique (appelée Multi-Redimensionnement) qui vous permet d'attendre et de nettoyer plusieurs couches de désordre en même temps.
- L'Analogie : Imaginez que vous lavez la vaisselle. Au lieu de laver une assiette, la sécher et la ranger, puis de laver une tasse, la sécher et la ranger, vous lavez toute une pile de vaisselle, puis vous séchez toute la pile, puis vous les rangez tous. Vous ne faites le « séchage » (la partie coûteuse et lente) qu'une seule fois pour tout le groupe.
Le Résultat : En réorganisant la façon dont ils regroupent les ingrédients (le « partitionnement »), ils peuvent combiner ces étapes de nettoyage. Pour la multiplication entre 4 et 12 ingrédients, leur nouvelle méthode économise 32 % d'espace et réduit le temps de moitié (45 % plus rapide) par rapport à l'ancienne file « deux par deux ».

3. Pourquoi Cela Compte (Selon l'Article)

L'article se concentre strictement sur l'architecture matérielle — la conception physique de la puce d'ordinateur qui effectue ces calculs.

Ils ont prouvé qu'en changeant la façon dont les mathématiques sont organisées (l'algorithme) et la façon dont la puce est construite (l'architecture), on peut effectuer des mathématiques chiffrées complexes beaucoup plus rapidement.
Ils mentionnent spécifiquement que cela aide des applications comme l'apprentissage automatique, le diagnostic médical et l'analyse financière, car ces domaines nécessitent souvent de multiplier de nombreuses données chiffrées ensemble.

Résumé

Pensez à cet article comme à l'invention d'une nouvelle cuisine ultra-efficace pour un chef qui ne peut pas retirer ses gants de four.

Ils ont trouvé comment mélanger trois ingrédients à la fois sans faire de désordre.
Ils ont inventé un moyen de nettoyer plusieurs couches de désordre en même temps, plutôt que les unes après les autres.
Le résultat est une cuisine qui est plus petite, plus rapide et nécessite moins d'énergie pour garder les secrets en sécurité tout en effectuant des mathématiques complexes.

Les auteurs n'ont pas testé cela sur de vrais patients ou de vrais comptes bancaires dans cet article ; ils ont seulement prouvé que la machine conçue pour faire ce travail est nettement supérieure aux machines que nous avions auparavant.

Résumé technique : Multiplication de chiffrés à entrées multiples pour le chiffrement homomorphe

Énoncé du problème
Le chiffrement homomorphe (HE), en particulier le schéma RNS-CKKS, permet des opérations arithmétiques sur des données chiffrées, ce qui est crucial pour des applications de préservation de la vie privée telles que l'apprentissage automatique et le diagnostic médical. Cependant, les schémas HE standards définissent la multiplication de chiffrés uniquement pour deux entrées. De nombreuses applications pratiques, telles que les approximations polynomiales d'ordre élevé pour les fonctions d'activation des réseaux de neurones (par exemple, ReLU), les arbres de décision et le séquençage du génome, nécessitent la multiplication de plusieurs chiffrés ( $n > 2$ ).

Les approches existantes pour gérer la multiplication à entrées multiples chaînent généralement plusieurs multiplicateurs à deux entrées dans une structure d'arbre binaire. Cette méthode souffre de deux inefficacités principales :

Latence et surface élevées : La multiplication séquentielle de $n$ chiffrés à l'aide d'unités à deux entrées entraîne une surcharge matérielle et une latence importantes.
Croissance du bruit et surcharge de redimensionnement : Chaque multiplication augmente le niveau de bruit, nécessitant une opération de redimensionnement (rescaling) pour restaurer l'échelle du message. Dans un arbre binaire standard, le redimensionnement doit avoir lieu après chaque étape de multiplication pour éviter une croissance exponentielle du bruit. Cela se traduit par un grand nombre d'unités de redimensionnement, chacune nécessitant des opérations coûteuses de Transformée Numérique Théorique (NTT) et de Transformée Numérique Théorique Inverse (INTT), augmentant considérablement la complexité computationnelle et l'utilisation des ressources matérielles.

Méthodologie
L'article propose un cadre pour une multiplication directe de chiffrés à $n$ entrées minimisant la profondeur multiplicative et la complexité matérielle. La méthodologie se divise en deux contributions principales :

Multiplicateur à trois entrées amélioré :
Les auteurs reformulent d'abord le processus de multiplication à trois entrées. Dans les travaux préliminaires [26], la rélinéarisation et le redimensionnement étaient effectués séparément, nécessitant plusieurs opérations ModUp/ModDown et de nombreux blocs (I)NTT. La nouvelle conception :
- Reformule la rélinéarisation : En déplaçant le facteur d'échelle $P^{-1}$ dans la conversion de base (BConv) et la multiplication de la clé d'évaluation, la conception élimine les étapes d'échelle séparées.
- Optimise le redimensionnement : Les auteurs restructurent le chemin de données pour effectuer le redimensionnement dans le domaine d'origine avant la NTT finale, plutôt que dans le domaine NTT. Cela permet d'éliminer les opérations (I)NTT redondantes.
- Résultat : Ces changements réduisent le nombre de blocs (I)NTT dans le chemin de données de huit à quatre, divisant efficacement la longueur du chemin de données par deux.
Extension à entrées multiples avec redimensionnement combiné :
Pour étendre la multiplication à $n > 3$ entrées sans augmenter la profondeur multiplicative, l'article introduit :
- Clés d'évaluation généralisées : De nouvelles clés d'évaluation ( $ek_t$ ) sont introduites pour rélinéariser les termes polynomiaux de degré supérieur ( $d_t s^t$ ) générés par la multiplication de $n$ chiffrés, ramenant le résultat à un format à deux polynômes.
- Algorithme de redimensionnement multiple (Multi-RS) : Une analyse théorique identifie les conditions dans lesquelles plusieurs opérations de redimensionnement peuvent être retardées et combinées. Les auteurs proposent un algorithme qui effectue $\mu$ opérations de redimensionnement concaténées en utilisant le même nombre d'opérations (I)NTT qu'un seul redimensionnement. Cela est réalisé en transformant l'entrée vers le domaine INTT, en effectuant un redimensionnement itératif dans le domaine des coefficients, puis en transformant à nouveau, en utilisant des constantes précalculées pour fusionner les opérations.
- Lignes directrices pour la partition des entrées : L'article fournit des lignes directrices pour partitionner $n$ entrées en groupes (par exemple, $(n_1, n_2, \dots, n_m)$ ) afin de maximiser le nombre d'opérations de redimensionnement combinées tout en maintenant la profondeur multiplicative optimale de $\lceil \log_2 n \rceil$ . Cela implique de créer des structures d'arbres déséquilibrées lorsque cela est possible pour regrouper davantage d'entrées avant une étape de redimensionnement.

Contributions clés

Reformulation algorithmique : Une nouvelle formulation pour la multiplication à trois entrées qui combine les calculs intermédiaires, réduisant le nombre d'opérations (I)NTT et raccourcissant le chemin de données.
Cadre à entrées multiples : Une extension de la multiplication de chiffrés à $n$ entrées arbitraires utilisant des clés d'évaluation généralisées et un multiplicateur en structure d'arbre.
Redimensionnement combiné : Un algorithme de redimensionnement multiple novateur qui réduit la complexité de l'exécution de plusieurs redimensionnements à celle d'un seul redimensionnement, indépendamment du nombre d'étapes combinées ( $\mu$ ).
Architecture matérielle : Conception d'architectures matérielles entièrement pipelinées pour les multiplicateurs proposés, incluant des unités ModUp, ModDown et de redimensionnement optimisées.

Résultats
Les conceptions proposées ont été synthétisées en utilisant le procédé GlobalFoundries 22FDX avec les paramètres $N=2^{16}$ , $L=K=24$ et $w=64$ .

Multiplicateur à trois entrées : Par rapport au travail antérieur [26], le multiplicateur à trois entrées amélioré réalise une réduction de 15 % de la surface logique et une réduction de 50 % de la latence. Il réduit également les besoins en mémoire d'environ 20 % grâce à un nombre réduit d'unités (I)NTT.
Multiplicateurs à entrées multiples ( $n=4$ à $12$) : Par rapport à une implémentation de base utilisant un arbre binaire de multiplicateurs à deux entrées, la méthode proposée réalise une réduction moyenne de 32 % de la surface totale et une réduction de 45 % de la latence.
Efficacité du redimensionnement : Pour des entrées non puissances de deux (par exemple, $n=17$ ), la partition optimisée combinée au redimensionnement multiple réduit le nombre total d'unités de redimensionnement (et des opérations (I)NTT associées) d'environ 47 % par rapport à l'approche d'arbre binaire standard.

Importance
L'article affirme que ces améliorations répondent au goulot d'étranglement de la multiplication à entrées multiples dans le HE, ce qui est essentiel pour des applications complexes de préservation de la vie privée. En réduisant la complexité matérielle et la latence de la multiplication de chiffrés, l'architecture proposée rend le déploiement du HE dans des environnements à ressources limitées ou à haut débit plus réalisable. Le travail démontre que grâce à une reformulation algorithmique et à une partition soignée des entrées, la surcharge de la gestion du bruit (redimensionnement) peut être considérablement minimisée sans compromettre la sécurité ou la correction du schéma de chiffrement. Les auteurs notent que les travaux futurs se concentreront sur la simplification supplémentaire des multiplicateurs pour un nombre encore plus élevé d'entrées.