🤖 machine learning

CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations

Dieses Paper stellt CHEHAB RL vor, ein Deep-Reinforcement-Learning-Framework, das die Optimierung von Code für Fully Homomorphic Encryption automatisiert, indem es lernt, Umschreibungsregeln für die Vektorisierung anzuwenden, was im Vergleich zu aktuellen State-of-the-Art-Methoden zu einer signifikant schnelleren Ausführung, reduziertem Rauschwachstum und einer wesentlich schnelleren Kompilierung führt.

Ursprüngliche Autoren: Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

Veröffentlicht 2026-01-28

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Das „verschlossene Kisten“-Problem

Stellen Sie sich vor, Sie haben ein sehr wertvolles Geheimnis, wie Ihr Bankpasswort oder eine Krankenakte. Sie möchten dieses Geheimnis an einen Fremden (einen Cloud-Server) senden, damit dieser damit mathematische Berechnungen durchführt, aber Sie haben schreckliche Angst, dass dieser hineinspäht und Ihr Geheimnis stiehlt.

Vollständig homomorphe Verschlüsselung (FHE) ist eine magische Lösung für dieses Problem. Es ist, als würde man Ihre Daten in eine verschlossene, transparente Box legen. Sie können diese Box dem Fremden geben, und dieser kann sie schütteln, schlagen und den Inhalt darin vermischen (Berechnungen durchführen), ohne jemals das Schloss zu öffnen oder zu sehen, was sich im Inneren befindet. Wenn er fertig ist, gibt er die Box an Sie zurück, und Sie öffnen sie, um das Ergebnis zu sehen.

Der Haken: Diese Magie ist unglaublich langsam und unordentlich. Rechnungen an einer verschlossenen Box durchzuführen, dauert tausendmal länger als bei normalen Daten. Es ist, als würde man versuchen, einen Kuchen zu backen, während man dicke, klobige Ofenhandschuhe trägt und eine Augenbinde aufhat.

Das Problem: Das Rezept zu schreiben, ist schwer

Um diese „verschlossene Kisten“-Mathematik schneller zu machen, müssen Experten sehr spezifischen, Low-Level-Code schreiben. Es ist, als würde man versuchen, ein Rezept für einen Kuchen zu schreiben, während man diese Ofenhandschuhe trägt.

Zu komplex: Man muss genau entscheiden, wie man die Zutaten (Daten) in die Box packt, damit sie sich nicht vermischen.
Zu langsam: Wenn man sie falsch verpackt, dauert die Mathematik ewig oder das „Rauschen“ (das statische Signal) in der Box wird so laut, dass das Endergebnis unbrauchbar ist.
Die Suchfalle: Den perfekten Weg zu finden, die Daten zu verpacken, ist wie die Suche nach der Nadel im Heuhaufen. Bestehende Werkzeuge versuchen, die Nadel zu finden, indem sie jeden einzelnen Punkt nacheinander überprüfen (eine „Brute-Force“-Suche). Das dauert sehr lange und bleibt oft an einem „gut genug“-Punkt hängen, der eigentlich gar nicht der beste ist.

Die Lösung: CHEHAB RL (Der „kluge Lehrling“)

Die Autoren dieser Arbeit haben ein neues Werkzeug namens CHEHAB RL entwickelt. Anstatt zu versuchen, jede einzelne Möglichkeit zu prüfen, haben sie einem Computer beigebracht, wie man lernt, unter Verwendung einer Technik namens Reinforcement Learning (RL).

Stellen Sie es sich wie das Training eines klugen Lehrlings-Chefs vor:

Das Ziel: Die Aufgabe des Lehrlings ist es, die Zutaten in der verschlossenen Box so umzuordnen, dass die Mathematik so schnell wie möglich abläuft und mit dem geringsten Maß an „Rauschen“.
Das Training: Anstatt dem Lehrling ein Regelbuch zu geben, lassen die Autoren den Lehrling Millionen verschiedener Möglichkeiten ausprobieren, die Zutaten umzuordnen.
- Wenn eine Umordnung die Mathematik schneller macht, bekommt der Lehrling eine „Belohnung“ (ein Leckerli).
- Wenn es die Dinge langsamer oder verrauschter macht, bekommt er einen „Strafpunkt“ (einen Ärger).
Der Datensatz: Um den Lehrling zu lehren, haben die Autoren nicht einfach nur zufälligen Müll verwendet. Sie haben ein Large Language Model (LLM) genutzt – eine super-intelligente KI, die auf realweltlichem Code trainiert wurde – um tausende realistische „Übungsrezepte“ zu generieren. Das ist, als würde man dem Lehrling das Üben an echten Kuchen erlauben, anstatt an zufälligen Haufen aus Mehl und Eiern.

Wie es funktioniert: Das „Umschreib“-Spiel

Der Kern des Systems ist ein Spiel mit Lego.

Sie haben eine Struktur, die aus Lego-Steinen gebaut ist (Ihr verschlüsselter Code).
Sie haben einen Satz von Regeln (wie „tausche diese zwei Steine aus“ oder „kombiniere diese drei zu einem“).
Der RL-Agent (der Lehrling) betrachtet die Struktur und entscheidet: "Wenn ich Regel A hier anwende und dann Regel B dort, wird das Ganze dann stabiler und schneller?"

Der Agent lernt eine Policy (eine Strategie), um diese Regeln in der perfekten Reihenfolge anzuwenden. Er betrachtet nicht nur einen einzelnen Schritt, sondern das gesamte Bild, um den besten Weg zu finden.

Die Ergebnisse: Geschwindigkeit, Stille und Effizienz

Das Paper vergleicht ihr „kluges Lehrlings-Modell“ (CHEHAB RL) mit dem derzeit besten Werkzeug namens Coyote. Hier ist das Ergebnis:

Ausführungsgeschwindigkeit (Das Kuchenbacken): Der von CHEHAB RL generierte Code lief 5,3-mal schneller als Coyote. Es war, als würde man von einem langsamen, manuellen Ofen auf einen Hochgeschwindigkeits-Umluftofen umsteigen.
Rauschen (Das statische Signal): Das „Rauschen“ in der verschlossenen Box wuchs mit CHEHAB RL 2,54-mal weniger. Das bedeutet, das Endergebnis ist viel klarer und weniger wahrscheinlich ruiniert.
Kompilierungszeit (Das Rezeptschreiben): Vielleicht das überraschendste Ergebnis: Es dauerte 27,9-mal weniger Zeit, für CHEHAB RL den optimierten Code zu schreiben, als für Coyote, ihn zu suchen. Der Lehrling hat die Strategie schnell gelernt, während Coyote noch hektisch den Heuhaufen absuchte.

Warum das wichtig ist

Das Paper behauptet, dass dies das erste Mal ist, dass Reinforcement Learning verwendet wurde, um dieses spezifische Problem der Optimierung von FHE-Code zu lösen.

Es bewältigt unordentlichen Code: Im Gegensatz zu älteren Werkzeugen, die nur mit sauberem, schleifenbasiertem Code funktionieren, kann dieses System unordentlichen, unstrukturierten Code bewältigen (wie ein verheddertes Wollknäuel).
Es skaliert: Wenn die Probleme größer werden, wird der „kluge Lehrling“ immer besser darin, während die alten „Brute-Force“-Suchmethoden immer langsamer werden.

Zusammenfassende Analogie

Stellen Sie sich vor, Sie versuchen, eine riesige Bibliothek von Büchern zu organisieren, die alle in Glasvitrinen verschlossen sind.

Der alte Weg (Coyote): Sie stellen ein Team von Bibliothekaren ein, die jede mögliche Anordnung der Bücher ausprobiert, um zu sehen, welche am schnellsten zu finden ist. Sie werden müde, brauchen lange Zeit und wählen oft eine „gute“ Anordnung, die aber nicht die beste ist.
Der neue Weg (CHEHAB RL): Sie stellen einen genialen Bibliothekar ein, der tausende Videos von anderen Bibliotheken beobachtet hat, die organisiert wurden. Er lernt die Muster dessen, was funktioniert. Wenn Sie ihm eine neue Bibliothek geben, weiß er sofort den besten Weg, sie zu organisieren, und macht es in einem Bruchteil der Zeit und sorgt dafür, dass die Bücher viel leichter zu finden sind.

Das Paper kommt zu dem Schluss, dass durch diesen „lernenden“ Ansatz die „verschlossene Kisten“-Technologie für den realen Gebrauch viel praktischer gemacht werden kann, sodass komplexe Berechnungen an privaten Daten durchgeführt werden können, ohne tagelang auf das Ergebnis warten zu müssen.

Technisches Resümee: CHEHAB RL: Lernen zur Optimierung von Fully Homomorphic Encryption Berechnungen

1. Problemstellung

Vollhomomorphe Verschlüsselung (Fully Homomorphic Encryption, FHE) ermöglicht Berechnungen auf verschlüsselten Daten ohne deren Entschlüsselung, wodurch die Privatsphäre gewahrt bleibt. FHE ist jedoch rechenintensiv; so kann beispielsweise eine Chiffretext-Multiplikation $10^6$ -mal langsamer sein als ihre Klartext-Entsprechung. Diese Performance-Lücke resultiert aus der inhärenten Komplexität homomorpher Operationen, die hochgradige Polynommultiplikationen und ein signifikantes Rauschwachstum beinhalten.

Das Schreiben von effizientem FHE-Code ist eine komplexe, fehleranfällige Aufgabe, die tiefes kryptographisches Fachwissen erfordert. Obwohl Compiler entwickelt wurden, um die FHE-Codegenerierung zu automatisieren, stehen bestehende Lösungen vor erheblichen Einschränkungen:

Strukturierter vs. unstrukturierter Code: Compiler wie HECO und CHET konzentrieren sich auf strukturierten (schleifenbasierten) Code, während andere wie Coyote und Porcupine versuchen, sowohl strukturierten als auch unstrukturierten (beliebigen, nicht schleifenbasierten) Code zu handhaben.
Komplexität des Suchraums: Aktuelle State-of-the-Art-Compiler (z. B. Coyote, Porcupine) formulieren die Vektorisierung als kombinatorisches Suchproblem. Sie verlassen sich auf handoptimierte Heuristiken, Integer Linear Programming (ILP) oder Programmsynthese, um einen riesigen Designraum zu explorieren (z. B. die Entscheidung, welche Teilausdrücke gepackt werden, das Datenlayout, die Einfügung von Rotationen).
Skalierbarkeit und lokale Optima: In diesem komplexen Raum haben lokale Entscheidungen oft nicht-lokale Auswirkungen (z. B. eine Packing-Entscheidung, die zukünftige Rotationskosten erhöht). Einfache Heuristiken geraten oft in schlechte lokale Optima fest, und eine erschöpfende Suche wird mit zunehmender Programmgröße rechnerisch unpraktikabel.

2. Methodik

Das Paper schlägt CHEHAB RL vor, ein neuartiges Framework, das Deep Reinforcement Learning (RL) nutzt, um die FHE-Codeoptimierung zu automatisieren. Anstatt einer kombinatorischen Suche formuliert das Framework das Problem als sequenziellen Entscheidungsprozess, bei dem ein RL-Agent lernt, eine Sequenz von Umformungsregeln (Rewriting Rules) anzuwenden.

2.1 Framework-Übersicht

CHEHAB RL ist in den CHEHAB FHE-Compiler integriert. Der Workflow gestaltet sich wie folgt:

Input: Ein Programm, das in der CHEHAB Domain-Specific Language (DSL) geschrieben wurde, welches in eine Intermediate Representation (IR) in Form eines Abstract Syntax Tree (AST) und eines Dataflow-Graphen (DAG) überführt wird.
RL-Optimierung: Ein RL-Agent durchläuft die IR und wählt eine Sequenz von Umformungsregeln aus einem Term Rewriting System (TRS) aus, um skalaren Code zu vektorisieren, Ausdrücke zu vereinfachen sowie Rauschen und Latenz zu minimieren.
Output: Die optimierte IR wird verwendet, um C++-Code zu generieren, der auf das Microsoft SEAL Backend (BFV-Schema) abzielt.

2.2 Zentrale technische Komponenten

A. Zustandsrepräsentation

Um die Program-IR für den RL-Agenten darzustellen, verwenden die Autoren eine Identifier and Constant Invariant (ICI) Tokenisierung.

Normalisierung: Variablen werden umbenannt (z. B. $v_0, v_1$ ) und Konstanten (außer 0 und 1) werden zu generischen Token abstrahiert ( $c_0, c_1$ ). Dies schafft eine kanonische Form, die invariant gegenüber Benennungen und spezifischen Konstantenwerten ist, wodurch semantisch äquivalente Programme in dieselbe Repräsentation kollabieren.
Kodierung: Die tokenisierte Sequenz wird von einem Transformer-Encoder (4 Schichten, 8 Attention-Heads) verarbeitet, um ein festes 256-dimensionales Embedding zu erzeugen. Diese Architektur wurde gegenüber RNNs (LSTM/GRU) aufgrund ihrer überlegenen Fähigkeit gewählt, langfristige Abhängigkeiten in ungerollten (unrolled) FHE-Programmen zu modellieren.

B. Aktionsraum

Der Aktionsraum ist darauf ausgelegt, die große Anzahl möglicher Regeln und Anwendungspositionen zu handhaben.

Hierarchische Policy: Anstatt eines flachen Aktionsraums (Regel + Ort) verwendet der Agent eine zweistufige hierarchische Policy:
1. Rule Selection Network: Ein MLP wählt, welche Umformungsregel aus einem Satz von 84 Regeln anzuwenden ist.
2. Location Selection Network: Ein zweites MLP wählt den spezifischen Ort (Match Index) in der IR aus, an dem die Regel angewendet wird.
Terminierung: Eine spezielle END-Aktion ermöglicht es dem Agenten, die Optimierungs-Episode zu beenden.

C. Belohnungsmodell

Der Agent wird trainiert, um eine zusammengesetzte Kostenfunktion zu minimieren, die Ausführungszeit und Rauschwachstum ausbalanciert.

Kostenfunktion: $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}$ : Gewichtete Summe der Operationskosten (Vektor-Add: 1, Vektor-Mul: 100, Rotation: 50, Skalar-Ops: 250).
- $D_{circuit}$ : Schaltungstiefe (Circuit Depth).
- $D_{mult}$ : Multiplikative Tiefe (kritisch für das Rauschen in BFV).
Belohnungsstruktur:
- Schritt-Belohnung ( $R_{step}$ ): Unmittelbare Belohnung basierend auf der prozentualen Kostenreduktion nach jeder Aktion.
- Terminal-Belohnung ( $R_{final}$ ): Eine globale Belohnung basierend auf der gesamten Kostenreduktion vom Ausgangs- zum Endzustand. Dies verhindert, dass der Agent lokal gierig agiert, und fördert Sequenzen, die global optimale Schaltungen ergeben.

D. Synthetisierung von Trainingsdaten

In Anerkennung des Mangels an existierenden FHE-Optimierungsdatensätzen haben die Autoren einen Trainingsdatensatz von 15.855 einzigartigen Ausdrücken unter Verwendung eines Large Language Models (LLM, Gemini 2.5 Flash) synthetisiert.

LLM-Steuerung: Das LLM wurde mit Syntaxregeln, Beispielen für Umformungsregeln und realen Kernel-Motiven (z. B. Matrixaddition, quadratische Differenz) instruiert, um diverse, optimierbare Codemuster zu generieren.
Validierung: Generierte Ausdrücke wurden auf syntaktische Gültigkeit, Einzigartigkeit (via ICI-Tokenisierung) und den Ausschluss von Benchmark-Programmen geprüft, um die Generalisierung zu gewährleisten.

E. Trainingsalgorithmus

Der Agent wird unter Verwendung des Proximal Policy Optimization (PPO) Algorithmus auf einer einzelnen Multi-Core-CPU über 2 Millionen Zeitschritte trainiert.

3. Zentrale Beiträge

Formulierung: Die erste Formulierung der FHE-Codeoptimierung als sequenzielles Entscheidungsproblem, das mittels Reinforcement Learning lösbar ist.
CHEHAB RL Framework: Ein neuartiges System, das sowohl strukturierten als auch unstrukturierten FHE-Code automatisch vektorisiert und gleichzeitig das Rauschen sowie die Latenz minimiert. Es skaliert besser als bestehende kombinatorische Suchansätze.
LLM-synthetisierter Datensatz: Die Erstellung und Validierung eines großen, diversen Trainingsdatensatzes, der von einem LLM generiert wurde, was zeigt, dass das Training auf solchen Daten deutlich bessere Agenten liefert als das Training auf zufälligen Programmen.
Performance-Gewinne: Empirische Belege dafür, dass CHEHAB RL Code generiert, der in der Ausführung 5,3× schneller ist, im Durchschnitt 2,54× weniger Rauschen akkumuliert und eine Kompilationszeit hat, die 27,9× schneller ist als die des State-of-the-Art Coyote-Compilers (geometrisches Mittel).
Open Source: Veröffentlichung des CHEHAB RL Frameworks für die Community.

4. Ergebnisse und Evaluierung

Die Autoren evaluierten CHEHAB RL gegen Coyote (einen State-of-the-Art Vektorisierungs-FHE-Compiler) anhand einer Suite von Benchmarks, die Bildverarbeitungsfilter, lineare Algebra-Kernel und zufällig generierte irreguläre Polynome umfassten.

Ausführungszeit: CHEHAB RL generierte Code, der im Durchschnitt 5,3× schneller war als Coyote. In spezifischen Fällen (z. B. Linear Regression 32) erreichte der Beschleunigungseffekt 114×. Dies wurde auf weniger Operationen und einfachere Datenlayouts zurückgeführt, die vom RL-Agenten gefunden wurden.
Rauschbudget: Die generierten Schaltungen verbrauchten im Durchschnitt 2,54× weniger Rauschbudget. In Benchmarks, in denen Coyote das Rauschbudget erschöpfte und die Ausführung fehlschlug, produzierte CHEHAB RL erfolgreich valide, ausführbare Schaltungen.
Kompilationszeit: Der RL-basierte Kompilierungsprozess war 27,9× schneller als der Suchansatz von Coyote. Während der RL-Agent bei kleinen Benchmarks einen Overhead verursachte (aufgrund der neuronalen Inferenzschritte), zeigte er eine überlegene Skalierbarkeit für größere Schaltungen, bei denen der kombinatorische Suchansatz von Coyote prohibitiv langsam wurde.
Ablationsstudien:
- LLM vs. Zufallsdaten: Agenten, die auf LLM-generierten Daten trainiert wurden, produzierten auf spezifischen Benchmarks 13× schnellere Schaltungen als Agenten, die auf Zufallsdaten trainiert wurden, was die Bedeutung realistischer Codemuster unterstreicht.
- Reward-Design: Die Kombination aus Schritt- und Terminal-Belohnungen übertraf die Verwendung von reinen Schritt-Belohnungen, da dies lokale Optima verhinderte.
- Architektur: Der Transformer-Encoder übertraf die GRU-Baselines bei der Erlernen von Programmberechnungen, und der hierarchische Aktionsraum übertraf flache Aktionsräume hinsichtlich der Lerngeschwindigkeit und der Belohnung.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass CHEHAB RL einen Paradigmenwechsel in der FHE-Kompilierung darstellt. Durch den Übergang von heuristikgesteuerter kombinatorischer Suche zu lernbasierter Policy-Optimierung adressiert das Framework die Probleme der Skalierbarkeit und der lokalen Optima, die bisherigen Ansätzen eigen sind.

Die Autoren betonen, dass dies die erste Verwendung von RL zur Lösung der FHE-Optimierung ist, wobei das Framework erfolgreich die Abwägungen zwischen Vektorisierung, kryptographischer Rauschakkumulation und Operationskosten navigiert. Die Arbeit zeigt, dass RL-Agenten effektive globale Strategien für Code-Transformationen erlernen können, die handoptimierte Heuristiken und ILP-Solver übertreffen, insbesondere für unstrukturierten Code. Die Integration von LLMs zur Datensynthetisierung unterstreicht zudem einen Weg zur Generierung hochwertiger Trainingsdaten in Domänen, in denen solche Daten knapp sind.

Das Paper schließt mit der Feststellung, dass CHEHAB RL die praktische Anwendung von FHE ermöglicht, indem es sowohl die Laufzeit verschlüsselter Berechnungen als auch die Zeit für deren Kompilierung signifikant reduziert, während die Sicherheitsgarantien des zugrunde liegenden kryptographischen Schemas gewahrt bleiben.