💻 computer science

KeyMemRT Compiler and Runtime: Unlocking Memory-Scalable FHE

KeyMemRT is een MLIR-gebaseerd compiler- en runtime-framework dat dataflowanalyse gebruikt om automatisch de levensduur van FHE-rotatiesleutels te beheren, wat het geheugengebruik aanzienlijk vermindert en de executiesnelheid verbetert in vergelijking met bestaande state-of-the-art compilers.

Oorspronkelijke auteurs: Eymen Ünay, Björn Franke, Jackson Woodruff

Gepubliceerd 2026-01-27

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Eymen Ünay, Björn Franke, Jackson Woodruff

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorme, complexe puzzel op te lossen, maar je mag de stukjes alleen bekijken terwijl je een blinddoek draagt. Je moet de stukjes manipuleren zonder ze te zien, gebruikmakend van een speciale set regels die de puzzel verborgen houden voor nieuwsgierige ogen. Dit is in essentie wat Fully Homomorphic Encryption (FHE) doet: het stelt computers in staat om berekeningen uit te voeren op gegevens terwijl die gegevens volledig versleuteld blijven.

Echter, er is een grote vangnet: om dit "blinddoek-rekenen" te kunnen doen, heeft de computer een gigantische bibliotheek aan speciale "magische sleutels" (genaamd rotatiesleutels) nodig.

Het Probleem: De "Sleutel-hoarder"

Denk aan deze magische sleutels als een enorme collectie fysieke sleutels voor een hotel met duizenden kamers.

De Oude Manier (ANT-ACE): Stel je een hotelmanager voor die, nog voordat een gast arriveert, elke enkele sleutel in het gebouw grijpt en ze allemaal op de receptie dumpt. Zelfs als de gast alleen kamer 101 wil bezoeken, houdt de manager de sleutels voor kamer 102 tot en met 5.000 gewoon daar op de balie liggen.
- Het Resultaat: De balie (het geheugen) raakt rommelig en overvol. Als het hotel enorm groot is, wordt de balie zo vol met sleutels dat er geen ruimte meer overblijft voor iets anders. Het systeem crasht of vertraagt omdat het probeert een berg overbodige sleutels te beheren.
De "Trage" Manier (Fhelipe): Een andere manager probeert ruimte te besparen door slechts een paar "meestersleutels" te bewaren. Om kamer 101 te openen, heeft hij niet de directe sleutel, dus moet hij een meestersleutel gebruiken om kamer 1 te openen, dan een andere om kamer 2 te openen, enzovoort, door een keten van sleutels te vormen totdat hij bij 101 is.
- Het Resultaat: De balie is netjes, maar de gast moet lang wachten terwijl de manager een lange keten van sleutels doorzoekt. Het proces is traag.

De Oplossing: KeyMemRT

De auteurs van dit artikel hebben een nieuw systeem gebouwd genaamd KeyMemRT. Zie dit als een super slimme, geautomatiseerde conciërge die de sleutels perfect beheert.

Het weet precies wat je nodig hebt: In plaats van alle sleutels in één keer te pakken, analyseert KeyMemRT de reisroute van de gast (de code van het programma) om te zien welke kamers ze precies zullen bezoeken en in welke volgorde.
Levering op het juiste moment: Het houdt de balie vrij. Het brengt de specifieke sleutel voor kamer 101 pas tevoorschijn vlak voordat de gast deze nodig heeft.
Directe Opruiming: Zodra de gast kamer 101 verlaat, neemt de conciërge die sleutel onmiddellijk weer mee en legt deze weer op een veilige plek, zodat er ruimte wordt gemaakt voor de volgende sleutel.
De "Prefetch"-truc: Om ervoor te zorgen dat de gast nooit hoeft te wachten, begint de conciërge alvast de volgende sleutel te halen terwijl de gast nog in de huidige kamer is. Dit gebeurt op de achtergrond, zodat het proces snel en soepel aanvoelt.

Wat hebben ze bereikt?

De onderzoekers hebben dit nieuwe systeem getest tegen de oude methoden met behulp van diverse complexe taken (zoals het herkennen van afbeeldingen in medische scans of financiële gegevens).

Geheugenbesparing: Vergeleken met de "Sleutel-hoarder"-methode (ANT-ACE), heeft KeyMemRT de hoeveelheid benodigde geheugen met 1,74 keer verminderd. Het is alsof je een hele hotelcollectie aan sleutels in een enkele aktetas past in plaats van in een magazijn.
Snelheid: Vergeleken met de "Trage Keten"-methode (Fhelipe), was KeyMemRT 1,73 keer sneller. Het bespaarde niet alleen ruimte; het maakte het werk ook veel sneller omdat het geen tijd verspilde aan het samenstellen van ketens van sleutels.

Waarom is dit belangrijk?

Momenteel is FHE moeilijk te gebruiken omdat het computers vereist met enorme hoeveelheden geheugen (honderden gigabytes) om alleen al deze sleutels vast te houden. Dit maakt het duur en onpraktisch voor veel echte toepassingen.

KeyMemRT werkt als een vertaler en een verkeerregelaar. Het neemt complexe, rommelige code en optimaliseert deze zodat het op standaardcomputers kan draaien zonder dat er een supercomputer nodig is om alleen al de sleutels vast te houden. Het maakt privacy-bewuste computing (zoals het analyseren van gevoelige medische of financiële gegevens zonder ooit de ruwe cijfers te zien) veel schaalbaarder en efficiënter.

Kortom: Ze hebben een slim systeem gebouwd dat voorkomt dat FHE-programma's nutteloze sleutels verzamelen en dat ze geen tijd verspillen aan het maken van sleutels vanaf nul, waardoor privacy-bewuste computing sneller en op kleinere, goedkopere machines kan draaien.

Technische Samenvatting: KeyMemRT Compiler en Runtime

Probleemstelling

Fully Homomorphic Encryption (FHE) maakt privacy-bewuste berekeningen op versleutelde gegevens mogelijk, maar staat voor aanzienlijke barrières bij echte adoptie vanwege de excessieve computationele en geheugenvereisten. Een primaire bottleneck is het beheer van rotatiesleutels (rotation keys). In gebatchte FHE-schema's (bijv. CKKS, BGV, BFV) zijn rotatie-operaties essentieel voor intra-vector berekeningen en bootstrapping. Echter, deze schema's vereisen een unieke rotatiesleutel voor elke specifieke rotatie-index.

Naarmate FHE-programma's schalen, groeit het aantal vereiste rotatie-indices, wat vaak honderden gigabytes of zelfs terabytes aan geheugen vereist om alle sleutels gelijktijdig op te slaan. Bestaande FHE-compilers behandelen rotatiesleutels over het algemeen als een enkele, statische entiteit, waarbij alle sleutels in het geheugen worden geladen voor de duur van de programma-executie. Deze aanpak mist geheugenschaalbaarheid. Daartegenover staan bestaande strategieën die proberen het geheugen te verminderen, zoals Fhelipe, die vertrouwen op het decomponeren van willekeurige rotatie-indices in ketens van machten van twee. Hoewel dit het aantal opgeslagen sleutels vermindert, verhoogt het de computationele latentie aanzienlijk door de overhead van de ketenvorming (chaining). Er is een gebrek aan compilers die fijnmazig, automatisch sleutelbeheer bieden om het geheugengebruik en de executiesnelheid in balans te houden.

Methodologie

De auteurs presenteren KeyMemRT, een compiler- en runtime-framework ontworpen om de levenscycli van rotatiesleutels individueel te beheren. Het systeem is gebouwd op de MLIR (Multi-Level Intermediate Representation) infrastructuur en introduceert een nieuw dialect en een nieuwe runtime-architectuur.

1. Het `kmrt` MLIR Dialect

KeyMemRT introduceert een nieuw dialect genaamd kmrt om het sleutelbeheer direct binnen de IR (Intermediate Representation) te representeren.

Nieuwe Typen: Het definieert een rot_key type geparametriseerd door de rotatie-index, waardoor de compiler onderscheid kan maken tussen sleutels voor verschillende indices.
Nieuwe Operaties: Het dialect bevat operaties voor expliciet sleutelbeheer:
- kmrt.load_key: Laadt een specifieke rotatiesleutel.
- kmrt.clear_key: Verwijdert een sleutel uit het geheugen.
- kmrt.prefetch_key: Geeft hints aan de runtime voor asynchrone het laden.
- kmrt.use_key / kmrt.assume_key: Beheert de scope en liveness van een sleutel.
Integratie: De compiler verlaagt (lowers) hoog-niveau operaties (bijv. van het ckks dialect via HEIR) naar het openfhe dialect, terwijl het kmrt operaties invoegt om de levenscycli van sleutels te beheren.

2. Compiler Optimalisatie Pipeline

De KeyMemRT compiler voert een reeks lowering- en optimalisatie-passes uit om het geheugenvoetafdruk te verkleinen zonder de prestaties op te offeren:

CKKS naar OpenFHE Lowering: Koppel elke rotatie-operatie aan een specifieke rot_key waarde, waardoor het probleem wordt omgezet van het creëren van liveness-ranges naar het samenvoegen ervan.
Baby-Step Giant-Step (BSGS) Decompositie: Vermindert het aantal vereiste sleutels van $N$ naar $\approx 2\sqrt{N}$ voor opeenvolgende rotatie-indices door rotaties te ketenen. Dit is bijzonder effectief voor matrix-vector vermenigvuldigingspatronen.
Merge Rotatie Sleutels: Gebruikt dataflow-analyse om sequenties te detecteren waarbij een sleutel wordt gewist en onmiddellijk opnieuw wordt geladen met dezelfde index, waardoor redundante load/clear paren worden verwijderd.
Rotatie Hoisting: Identificeert rotatiepatronen die op gemeenschappelijke inputs worden toegepast en transformeert deze naar snellere alternatieven die door de OpenFHE library worden ondersteund.
Bootstrap Sleutel Beheer: Materialiseert de interne rotatiesleutels die worden gebruikt door bootstrap-operaties (die ciphertext-niveaus verversen) in de IR. Dit stelt de compiler in staat om bootstrap-sleutels te beheren met dezelfde fijnmazige controle als expliciete rotatiesleutels, een functie die voorheen onbehandeld bleef.
Common Subexpression Elimination (CSE): Verwijdert dode code die voortvloeit uit sleutel-optimalisaties.
Hint Plaatsing: Voegt prefetch_key hints in om de runtime in staat te stellen de I/O te overlappen met de computation.

3. KeyMemRT Runtime

De runtime fungeert als een tussenpersoon tussen de gecompileerde C++ code en de FHE-library (OpenFHE). Het beheert het dynamische laden en lossen van sleutels van disk naar RAM op basis van door de compiler ingevoegde hints.

Low-Memory Mode: Voert instructies sequentieel uit, waarbij sleutels alleen worden geladen wanneer dat strikt noodzakelijk is om het piekgeheugengebruik te minimaleren.
Balanced Mode: Maakt gebruik van een prefetching-mechanisme om sleutels parallel met de computation te laden. Het onderhoudt een interne wachtrij, waarbij sleutels vooraf worden geladen tot een door de gebruiker gedefinieerde limiet en wordt gewist wanneer ruimte nodig is, waardoor de latentie-overhead wordt verminderd.

Belangrijkste Bijdragen

Nieuw MLIR Dialect (kmrt): Het eerste dialect dat rotatiesleutels blootstelt als IR-elementen met specifieke typen en geheugenbeheer-operaties, wat fijnmazige analyse mogelijk maakt.
Automatisch Fijnmazig Sleutelbeheer: De eerste FHE-compiler die automatisch de liveness van sleutels bijhoudt, bootstrap-sleutels optimaliseert en de levenscycli van sleutels individueel beheert in plaats van als een globale set.
Runtime Framework: Een runtime die on-demand laden en wissen van sleutels ondersteunt, gebruikmakend van compiler-hints om I/O te overlappen met computation.
Integratie: Een post-optimaliserende compiler toolchain die kan worden aangestuurd door bestaande FHE frontends (gedemonstreerd met Orion en HEIR).

Resultaten

De auteurs hebben KeyMemRT geëvalueerd tegen twee state-of-the-art benaderingen: ANT-ACE (die alle sleutels in het geheugen houdt) en Fhelipe (die decompositie gebruikt om sleutels te verminderen maar de latentie verhoogt). De benchmarks omvatten diverse ML-modellen (MLP, LoLa, LeNet, ResNet varianten, AlexNet) met FHE-parameters ingesteld op een ringdimensie van $2^{16}$ en een multiplicatieve diepte van 30.

Geheugen Reductie:
- Vergeleken met ANT-ACE bereikte KeyMemRT een geometrisch gemiddelde geheugenreductie van 1.74x. In specifieke gevallen zoals LeNet werd het geheugengebruik verminderd met 2.59x.
- Vergeleken met Fhelipe bereikte KeyMemRT een geheugenreductie van 1.16x.
Latentie/Snelheidswinst:
- Vergeleken met ANT-ACE bereikte KeyMemRT (Balanced mode) een versnelling van 1.20x.
- Vergeleken met Fhelipe bereikte KeyMemRT een significante versnelling van 1.73x (geometrisch gemiddelde), met verbeteringen tot 2.5x op AlexNet. Dit komt omdat KeyMemRT de computationele overhead vermijdt die nodig is voor de ketenvorming van rotaties die Fhelipe vereist.
Schaalbaarheid: KeyMemRT demonstreerde het vermogen om grote programma's (bijv. ResNet-50) uit te voeren die onder ANT-ACE meer dan 100 GB aan geheugen vereisten, door het geheugengebruik aanzienlijk lager te houden.

Betekenis en Claims

Het artikel claimt dat KeyMemRT de eerste FHE-compiler is die automatisch, fijnmazig sleutelbeheer en bootstrap-sleutelbeheer biedt. De auteurs stellen dat dit werk de geheugenschaalbaarheid voor FHE ontsluit, waardoor willekeurig grote programma's kunnen draaien zonder de verbijsterende geheugenlast van het gelijktijdig opslaan van alle rotatiesleutels.

Door het geheugengebruik los te koppelen van het totaal aantal sleutels en in plaats daarvan sleutels te beheren op basis van hun liveness, stelt KeyMemRT FHE-programma's in staat om beter te schalen op bestaande hardware. De auteurs benadrukken dat hun aanpak de prestaties niet in gevaar brengt; in tegen tegenstelling tot decompositie-gebaseerde methoden die geheugen inruilen voor snelheid, bereikt KeyMemRT zowel geheugenreductie als latentieverbetering door alleen de noodzakelijke sleutels te laden op het exacte moment dat ze nodig zijn. Dit pakt een kritieke barrière aan voor de adoptie van FHE in omgevingen met beperkte middelen of op grote schaal.