🤖 machine learning

CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations

Cet article introduit CHEHAB RL, un cadre d'apprentissage par renforcement profond qui automatise l'optimisation du code de chiffrement totalement homomorphe en apprenant à appliquer des règles de réécriture pour la vectorisation, ce qui permet d'obtenir une exécution nettement plus rapide, une croissance du bruit réduite et une compilation beaucoup plus rapide par rapport aux méthodes de pointe.

Auteurs originaux : Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

Publié 2026-01-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

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

La vue d'ensemble : Le problème de la « boîte verrouillée »

Imaginez que vous possédez un secret très précieux, comme votre mot de passe bancaire ou un dossier médical. Vous voulez envoyer ce secret à un inconnu (un serveur cloud) pour qu'il effectue des calculs dessus, mais vous avez la peur bleue qu'il jette un coup d'œil à l'intérieur et vole votre secret.

Le chiffrement totalement homomorphe (FHE) est une solution magique à ce problème. C'est comme si vous placiez vos données dans une boîte transparente et verrouillée. Vous pouvez donner cette boîte à l'inconnu, et il peut secouer la boîte, la frapper et mélanger son contenu (effectuer des calculs) sans jamais ouvrir le verrou ni voir ce qu'il y a à l'intérieur. Lorsqu'il a terminé, il vous rend la boîte, et vous la déverrouillez pour voir le résultat.

Le bémol : Cette magie est incroyablement lente et désordonnée. Faire des mathématiques sur une boîte verrouillée prend des milliers de fois plus de temps que de les faire sur des données classiques. C'est comme essayer de cuisiner un gâteau en portant des gants de cuisine épais et encombrants ainsi qu'un bandeau sur les yeux.

Le problème : Écrire la recette est difficile

Pour rendre ce calcul en « boîte verrouillée » plus rapide, les experts doivent écrire un code de bas niveau très spécifique. C'est comme essayer d'écrire une recette de gâteau tout en portant ces gants de cuisine.

Trop complexe : Vous devez décider exactement comment emballer les ingrédients (les données) dans la boîte pour qu'ils ne se mélangent pas.
Trop lent : Si vous les emballez mal, les calculs prendront une éternité, ou le « bruit » (l'électricité statique) dans la boîte deviendra si fort que le résultat final sera de la camelote.
Le piège de la recherche : Trouver la façon parfaite d'emballer les données, c'est comme chercher une aiguille dans une botte de foin. Les outils existants essaient de trouver l'aiguille en vérifiant chaque endroit un par un (une recherche par « force brute »). Cela prend beaucoup de temps et on finit souvent bloqué sur un point « assez bon » qui n'est pas réellement le meilleur.

La solution : CHEHAB RL (L'apprenti intelligent)

Les auteurs de cet article ont construit un nouvel outil appelé CHEHAB RL. Au lieu d'essayer de vérifier chaque possibilité, ils ont appris à un ordinateur comment apprendre en utilisant une technique appelée Apprentissage par Renforcement (RL).

Voyez cela comme la formation d'un apprenti chef intelligent :

L'objectif : Le travail de l'apprenti est de réorganiser les ingrédients dans la boîte verrouillée afin que les calculs soient les plus rapides possibles avec le moins de « bruit ».
L'entraînement : Au lieu de donner un manuel de règles à l'apprenti, ils l'ont laissé essayer des millions de façons différentes de réorganiser les ingrédients.
- Si un réarrangement rend les calculs plus rapides, l'apprenti reçoit une « récompense » (une friandise).
- Si cela rend les choses plus lentes ou plus bruyantes, il reçoit un « froncement de sourcils » (une pénalité).
Le jeu de données : Pour enseigner à l'apprenti, les auteurs n'ont pas utilisé de vieux déchets aléatoires. Ils ont utilisé un Grand Modèle de Langage (LLM) — une IA super intelligente entraînée sur du code réel — pour générer des milliers de « recettes d'entraînement » réalistes. C'est comme donner à l'apprenti de l'entraînement sur de vrais gâteaux plutôt que sur des tas de farine et d'œufs aléatoires.

Comment ça marche : Le jeu de la « réécriture »

Le cœur du système est un jeu de Lego.

Vous avez une structure construite à partir de briques Lego (votre code chiffré).
Vous avez un ensemble de règles (comme « échanger ces deux briques » ou « combiner ces trois briques en une seule »).
L'agent de RL (l'apprenti) regarde la structure et décide : « Si j'applique la Règle A ici, puis la Rule B là, est-ce que l'ensemble deviendra plus stable et plus rapide ? »

L'agent apprend une politique (une stratégie) pour appliquer ces règles dans l'ordre parfait. Il ne se contente pas de regarder une seule étape ; il regarde l'ensemble de l'image pour trouver le meilleur chemin.

Les résultats : Vitesse, Silence et Efficacité

L'article compare leur « Apprenti Intelligent » (CHEHAB RL) à l'outil de référence actuel, appelé Coyote. Voici ce qui s'est passé :

Vitesse d'exécution (La cuisson du gâteau) : Le code généré par CHEHAB RL s'est exécuté 5,3 fois plus vite que celui de Coyote. C'était comme passer d'un four manuel lent à un four à convection haute vitesse.
Bruit (Le statique) : Le « bruit » dans la boîte verrouillée a été 2,54 fois moins élevé avec CHEHAB RL. Cela signifie que le résultat final est beaucoup plus clair et moins susceptible d'être gâché.
Temps de compilation (L'écriture de la recette) : Résultat peut-être le plus surprenant : il a fallu 27,9 fois moins de temps à CHEHAB RL pour écrire le code optimisé qu'à Coyote pour le chercher. L'apprenti a appris la stratégie rapidement, tandis que Coyote était encore en train de chercher frénétiquement dans la botte de foin.

Pourquoi est-ce important ?

L'article affirme que c'est la première fois que l'apprentissage par renforcement est utilisé pour résoudre ce problème spécifique d'optimisation du code FHE.

Il gère le code désordonné : Contrairement aux anciens outils qui ne fonctionnent que sur du code propre basé sur des boucles, ce système peut gérer du code désordonné et non structuré (comme une pelote de laine emmêlée).
Il passe à l'échelle : À mesure que les problèmes deviennent plus grands, l'« Apprenti Intelligent » devient meilleur pour les gérer, tandis que les anciennes méthodes de recherche par « force brute » deviennent de plus en plus lentes.

Analogie de résumé

Imaginez que vous essayez d'organiser une immense bibliothèque de livres qui sont tous enfermés dans des vitrines en verre.

L'ancienne méthode (Coyote) : Vous embauchez une équipe de bibliothécaires qui essaient toutes les dispositions possibles de livres pour voir laquelle est la plus rapide pour les trouver. Ils se fatiguent, prennent beaucoup de temps et choisissent souvent une disposition « assez bonne » qui n'est pas la meilleure.
La nouvelle méthode (CHEHAB RL) : Vous embauchez un bibliothécaire de génie qui regarde des milliers de vidéos d'autres bibliothèques en cours d'organisation. Il apprend les schémas de ce qui fonctionne. Quand vous lui donnez une nouvelle bibliothèque, il sait instantanément la meilleure façon de l'organiser, en faisant cela en une fraction du temps et en rendant les livres beaucoup plus faciles à trouver.

L'article conclut qu'en utilisant cette approche d'« apprentissage », nous pouvons rendre la technologie de la « boîte verrouillée » beaucoup plus pratique pour une utilisation réelle, nous permettant d'effectuer des calculs complexes sur des données privées sans attendre des jours pour le résultat.

Résumé Technique : CHEHAB RL : Apprendre à optimiser les calculs en Chiffrement Totalement Homomorphe

1. Énoncé du Problème

Le chiffrement totalement homomorphe (FHE - Fully Homomorphic Encryption) permet d'effectuer des calculs sur des données chiffrées sans les déchiffrer, préservant ainsi la confidentialité. Cependant, le FHE reste coûteux en termes de calcul ; par exemple, une multiplication de texte chiffré peut être $10^6$ fois plus lente que son équivalent en texte clair. Cet écart de performance provient de la complexité inhérente aux opérations homomorphes, qui impliquent des multiplications polynomiales de degré élevé et une croissance significative du bruit.

L'écriture de code FHE efficace est une tâche complexe et sujette aux erreurs, nécessitant une expertise cryptographique approfondie. Bien que des compilateurs aient été développés pour automatiser la génération de code FHE, les solutions existantes font face à des limitations importantes :

Code structuré vs non structuré : Les compilateurs comme HECO et CHET se concentrent sur le code structuré (basé sur des boucles), tandis que d'autres comme Coyote et Porcupine tentent de gérer à la fois le code structuré et le code non structuré (arbitraire, non basé sur des boucles).
Complexité de l'espace de recherche : Les compilateurs de pointe actuels (par exemple, Coyote, Porcupine) cadrent la vectorisation comme un problème de recherche combinatoire. Ils reposent sur des heuristiques ajustées à la main, la programmation linéaire en nombres entiers (ILP) ou la synthèse de programmes pour explorer un vaste espace de conception (par exemple, décider quels sous-expressions regrouper, la disposition des données, l'insertion de rotations).
Scalabilité et optima locaux : Dans cet espace complexe, les décisions locales ont souvent des effets non locaux (par exemple, une décision de regroupement augmentant les coûts de rotation futurs). Les heuristiques simples se retrouvent souvent piégées dans de mauvais optima locaux, et la recherche exhaustive devient informatiquement intenable à mesure que la taille du programme augmente.

2. Méthodologie

Le papier propose CHEHAB RL, un nouveau cadre qui exploite l'apprentissage par renforcement profond (Deep Reinforcement Learning - RL) pour automatiser l'optimisation du code FHE. Au lieu d'une recherche combinatoire, le problème est formulé comme un processus de prise de décision séquentielle où un agent de RL apprend une politique pour appliquer une séquence de règles de réécriture.

2.1 Vue d'ensemble du cadre

CHEHAB RL est intégré au compilateur FHE CHEHAB. Le flux de travail est le suivant :

Entrée : Un programme écrit dans le langage spécifique au domaine (DSL) de CHEHAB, qui est abaissé vers une représentation intermédiaire (IR) sous la forme d'un arbre de syntaxe abstraite (AST) et d'un graphe de flux de données (DAG).
Optimisation par RL : Un agent de RL parcourt l'IR, sélectionnant une séquence de règles de réécriture à partir d'un système de réécriture de termes (TRS) pour vectoriser le code scalaire, simplifier les expressions et minimiser le bruit/la latence.
Sortie : L'IR optimisée est utilisée pour générer du code C++ ciblant le backend Microsoft SEAL (schéma BFV).

2.2 Composants techniques clés

A. Représentation de l'état

Pour représenter l'IR du programme pour l'agent de RL, les auteurs utilisent une tokenisation par Identifiant et Invariant de Constante (ICI).

Normalisation : Les variables sont renommées (ex: $v_0, v_1$ ) et les constantes (sauf 0 et 1) sont abstraites en jetons génériques ( $c_0, c_1$ ). Cela crée une forme canonique invariante au nommage et aux valeurs de constantes spécifiques, regroupant des programmes sémantiquement équivalents dans la même représentation.
Encodage : La séquence tokenisée est traitée par un encodeur Transformer (4 couches, 8 têtes d'attention) pour produire un plongement (embedding) de longueur fixe de 256 dimensions. Cette architecture a été choisie de préférence aux RNN (LSTM/GRU) pour sa capacité supérieure à modéliser les dépendances à longue portée dans les programmes FHE déroulés.

B. Espace d'action

L'espace d'action est conçu pour gérer le grand nombre de règles et de lieux d'application possibles.

Politique hiérarchique : Au lieu d'un espace d'action plat (règle + emplacement), l'agent utilise une politique hiérarchique en deux étapes :
1. Réseau de sélection de règle : Un MLP sélectionne quelle règle de réécriture appliquer parmi un ensemble de 84 règles.
2. Réseau de sélection de lieu : Un second MLP sélectionne l'emplacement spécifique (indice de correspondance) dans l'IR où la règle est appliquée.
Terminaison : Une action spéciale END permet à l'agent de terminer l'épisode d'optimisation.

C. Modèle de récompense

L'agent est entraîné pour minimiser une fonction de coût composite qui équilibre le temps d'exécution et la croissance du bruit.

Fonction de coût : $Cost(e) = w_{ops} \cdot C_{ops}(e) + w_{depth} \cdot D_{circuit}(e) + w_{mult} \cdot D_{mult}(e)$ $C os t (e) = w_{o p s} \cdot C_{o p s} (e) + w_{d e pt h} \cdot D_{c i r c u i t} (e) + w_{m u l t} \cdot D_{m u l t} (e)$ .
- $C_{ops}$ : Somme pondérée des coûts d'opération (Addition Vectorielle : 1, Multiplication Vectorielle : 100, Rotation : 50, Opérations Scalaires : 250).
- $D_{circuit}$ : Profondeur du circuit.
- $D_{mult}$ : Profondeur multiplicative (critique pour la croissance du bruit dans BFV).
Structure de récompense :
- Récompense par étape ( $R_{step}$ ) : Récompense immédiate basée sur le pourcentage de réduction du coût après chaque action.
- Récompense terminale ( $R_{final}$ ) : Récompense globale basée sur la réduction totale du coût entre l'état initial et l'état final. Cela empêche l'agent d'être localement gourmand et l'encourage à trouver des séquences qui produisent des circuits globalement optimaux.

D. Synthèse des données d'entraînement

Reconnaissant l'absence de jeux de données d'optimisation FHE existants, les auteurs ont synthétisé un jeu de données d'entraînement de 15 855 expressions uniques en utilisant un Grand Modèle de Langage (LLM, Gemini 2.5 Flash).

Guidage par LLM : Le LLM a été sollicité avec des règles de syntaxe, des exemples de règles de réécriture et des motifs de noyaux réels (ex: addition de matrices, différence au carré) pour générer des motifs de code diversifiés et optimisables.
Validation : Les expressions générées ont été filtrées pour leur validité syntaxique, leur unicité (via la tokenisation ICI) et l'exclusion de programmes de référence afin de garantir la généralisation.

E. Algorithme d'entraînement

L'agent est entraîné à l'aide de l'algorithme d'Optimisation de la Politique Proximale (PPO) sur un seul processeur multi-cœur pendant 2 millions de pas de temps (timesteps).

3. Contributions Clés

Formulation : La première formulation de l'optimisation du code FHE comme un problème de prise de décision séquentielle résoluble via l'apprentissage par renforcement.
Cadre CHEHAB RL : Un nouveau système qui vectorise automatiquement le code FHE structuré et non structuré tout en minimisant la croissance du bruit et la latence du circuit. Il est plus scalable que les approches de recherche combinatoire existantes.
Jeu de données synthétisé par LLM : La création et la validation d'un vaste jeu de données d'entraînement généré par un LLM, démontrant que l'entraînement sur de telles données produit des agents nettement meilleurs que l'entraînement sur des programmes aléatoires.
Gains de performance : Preuves empiriques montrant que CHEHAB RL génère un code 5,3× plus rapide, accumule 2,54× moins de bruit et possède un temps de compilation 27,9× plus court que le compilateur Coyote (moyennes géométriques).
Open Source : Publication du cadre CHEHAB RL à la communauté.

4. Résultats et Évaluation

Les auteurs ont évalué CHEHAB RL par rapport à Coyote (un compilateur FHE de vectorisation de pointe) sur une suite de benchmarks incluant des filtres de traitement d'image, des noyaux d'algèbre linéaire et des polynômes irréguliers générés aléatoirement.

Temps d'exécution : CHEHAB RL a généré un code qui était, en moyenne, 5,3× plus rapide que Coyote. Dans certains cas (ex: Régression Linéaire 32), l'accélération a atteint 114×. Cela est dû à un nombre réduit d'opérations et à des dispositions de données plus simples trouvées par l'agent de RL.
Budget de bruit : Les circuits générés ont consommé 2,54× moins de budget de bruit en moyenne. Dans les benchmarks où Coyote a épuisé le budget de bruit et échoué à l'exécution, CHEHAB RL a réussi à produire des circuits valides et exécutables.
Temps de compilation : Le processus de compilation par RL était 27,9× plus rapide que l'approche de recherche de Coyote. Bien que l'agent de RL introduise un surcoût pour les petits benchmarks (dû aux étapes d'inférence du réseau neuronal), il a démontré une meilleure scalabilité pour les circuits plus larges où la recherche combinatoire de Coyote devenait prohibitivement lente.
Études d'ablation :
- LLM vs Données Aléatoires : Les agents entraînés sur des données générées par LLM ont produit des circuits 13× plus rapides sur certains benchmarks par rapport à ceux entraînés sur des données aléatoires, soulignant l'importance de motifs de code réalistes.
- Conception de la récompense : La combinaison des récompenses par étape et terminales a surpassé les récompenses par étape uniquement, évitant les optima locaux.
- Architecture : L'encodeur Transformer a surpassé les bases GRU pour apprendre les représentations de programmes, et l'espace d'action hiérarchique a surpassé les espaces d'action plats en termes d'apprentissage de la vitesse et de la récompense.

5. Signification et Revendications

Le papier affirme que CHEHAB RL représente un changement de paradigme dans la compilation FHE. En passant d'une recherche combinatoire pilotée par des heuristiques à une optimisation de politique basée sur l'apprentissage, le cadre répond aux problèmes de scalabilité et d'optima locaux inhérents aux approches précédentes.

Les auteurs soulignent que c'est la première utilisation du RL pour résoudre l'optimisation FHE, naviguant avec succès entre les compromis de la vectorisation, l'accumulation de bruit cryptographique et les coûts d'opération. Ce travail démontre que les agents de RL peuvent apprendre des stratégies globales efficaces pour la transformation de code qui surpassent les heuristiques ajustées à la main et les solveurs ILP, particulièrement pour le code non structuré. L'intégration des LLM pour la synthèse de jeux de données souligne également une voie pour générer des données d'entraînement de haute qualité dans des domaines où de telles données sont rares.

Le papier conclut que CHEHAB RL permet l'adoption pratique du FHE en réduant considérablement à la fois le temps d'exécution des calculs chiffrés et le temps requis pour les compiler, tout en préservant les garanties de sécurité du schéma cryptographique sous-jacent.