💻 computer science

KeyMemRT Compiler and Runtime: Unlocking Memory-Scalable FHE

KeyMemRT es un marco de trabajo de compilación y tiempo de ejecución basado en MLIR que utiliza el análisis de flujo de datos para gestionar automáticamente los tiempos de vida de las claves de rotación de FHE, reduciendo significativamente el consumo de memoria y mejorando la velocidad de ejecución en comparación con los compiladores de vanguardia existentes.

Autores originales: Eymen Ünay, Björn Franke, Jackson Woodruff

Publicado 2026-01-27

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Eymen Ünay, Björn Franke, Jackson Woodruff

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando resolver un rompecabezas masivo y complejo, pero solo se te permite mirar las piezas mientras llevas una venda en los ojos. Tienes que manipular las piezas sin verlas, utilizando un conjunto especial de reglas que mantienen el rompecabezas oculto a ojos curiosos. Esto es esencialmente lo que hace el Cifrado Totalmente Homomórfico (FHE): permite que las computadoras realicen cálculos sobre datos mientras esos datos permanecen completamente cifrados.

Sin embargo, hay un gran inconveniente. Para realizar estas matemáticas "con la venda en los ojos", la computadora necesita una biblioteca gigante de "llaves mágicas" especiales (llamadas llaves de rotación).

El Problección: El "Acaparador de Llaves"

Piensa en estas llaves mágicas como una enorme colección de llaves físicas para un hotel con miles de habitaciones.

La forma antigua (ANT-ACE): Imagina a un gerente de hotel que, incluso antes de que llegue un huésped, agarra todas las llaves del edificio y las vuelca todas sobre el mostrador de recepción. Aunque el huésped solo necesite visitar la Habitación 101, el gerente mantiene las llaves de las Habitaciones 102 hasta la 5,000 allí mismo en el mostrador.
- El resultado: El mostrador (la memoria) se desordena y se desborda. Incluso si el hotel es enorme, el mostrador se llena tanto de llaves que no queda espacio para nada más. El sistema falla o se ralentiza porque está intentando gestionar una montaña de llaves innecesarias.
La forma "lenta" (Fhelipe): Otro gerente intenta ahorrar espacio manteniendo solo unas pocas "llaves maestras". Para abrir la Habitación 101, no tiene la llave directa, por lo que debe usar una llave maestra para abrir la Habitación 1, luego otra para abrir la Habitación 2, y así sucesivamente, encadenándolas hasta llegar a la 101.
- El resultado: El mostrador está ordenado, pero el huésped tiene que esperar mucho tiempo mientras el gerente busca entre una larga cadena de llaves. El proceso es lento.

La Solución: KeyMemRT

Los autores de este artículo construyeron un nuevo sistema llamado KeyMemRT. Piensa en esto como un servicio de conserjería súper inteligente y automatizado que gestiona las llaves perfectamente.

Sabe exactamente lo que necesitas: En lugar de agarrar todas las llaves a la vez, KeyMemRT analiza el itinerario del huésped (el código del programa) para ver exactamente qué habitaciones visitará y en qué orden.
Entrega justo a tiempo: Mantiene el mostrador despejado. Solo trae la llave específica para la Habitación 101 justo antes de que el huésped la necesite.
Limpieza instantánea: Tan pronto como el huésped sale de la Habitación 101, el conserje retira inmediatamente esa llave y la guarda, haciendo espacio para la siguiente llave.
El truco del "Prefetch": Para asegurar que el huésped nunca tenga que esperar, el conserje comienza a traer la siguiente llave mientras el huésped todavía está en la habitación actual. Esto sucede en segundo plano, para que el proceso se sienta rápido y fluido.

¿Qué lograron?

Los investigadores probaron este nuevo sistema contra los métodos antiguos utilizando diversas tareas complejas (como reconocer imágenes en escaneos médicos o datos financieros).

Ahorro de memoria: Comparado con el método del "Acaparador de Llaves" (ANT-ACE), KeyMemRT redujo la cantidad de memoria necesaria en 1.74 veces. Es como meter todas las llaves de un hotel en un solo maletín en lugar de en un almacén.
Velocidad: Comparado con el "Método de la Cadena Lenta" (Fhelipe), KeyMemRT fue 1.73 veces más rápido. No solo ahorró espacio; también hizo que el trabajo ocurriera mucho más rápido porque no perdió tiempo encadenando llaves.

¿Por qué es esto importante?

Actualmente, el FHE es difícil de usar porque requiere computadoras con cantidades enormes de memoria (cientos de gigabytes) solo para contener estas llaves. Esto lo hace costoso e impracticable para muchos usos del mundo real.

KeyMemRT actúa como un traductor y un controlador de tráfico. Toma códigos complejos y desordenados y los optimiza para que puedan ejecutarse en computadoras estándar sin necesidad de una supercomputadora solo para contener las llaves. Hace que la computación que preserva la privacidad (como analizar datos médicos o financieros sensibles sin ver nunca los números reales) sea más escalable y eficiente.

En resumen: Construyeron un sistema inteligente que evita que los programas de FHE acaparen llaves inútiles y evita que pierdan tiempo creando llaves desde cero, permitiendo que la computación privada se ejecute más rápido y en máquinas más pequeñas y económicas.

Resumen Técnico: Compilador y Entorno de Ejecución KeyMemRT

Declaración del Problema

El Cifrado Completamente Homomórfico (FHE) permite la computación preservadora de la privacidad sobre datos cifrados, pero enfrenta barreras significativas para su adopción en el mundo real debido a sus excesivos requisitos computacionales y de memoria. Un cuello de botella primario es la gestión de las claves de rotación. En los esquemas FHE con procesamiento por lotes (por ejemplo, CKKS, BGV, BFV), las operaciones de rotación son esenciales para las computaciones intra-vectoriales y el bootstrapping. Sin embargo, estos esquemas requieren una clave de rotación única para cada índice de rotación específico.

A medida que los programas FHE escalan, el número de índices de rotación requeridos crece, lo que a menudo hace necesario almacenar cientos de gigabytes o incluso terabytes de memoria para guardar todas las claves simultáneamente. Los compiladores FHE existentes generalmente tratan las claves de rotación como una entidad única y estática, cargando todas las claves en memoria durante la duración de la ejecución del programa. Este enfoque carece de escalabilidad de memoria. Por el contrario, las estrategias existentes que intentan reducir la memoria, como Fhelipe, se basan en la descomposición de índices de rotación arbitrarios en cadenas de potencias de dos. Si bien esto reduce el número de claves almacenadas, aumenta significativamente la latencia computacional debido a la sobrecarga de la encadenación. Existe una falta de compiladores que ofrezcan una gestión de claves automática y de grano fino para equilibrar el uso de memoria y la velocidad de ejecución.

Metodología

Los autores presentan KeyMemRT, un marco de trabajo de compilador y entorno de ejecución diseñado para gestionar los ciclos de vida de las claves de rotación de forma individual. El sistema está construido sobre la infraestructura MLIR (Multi-Level Intermediate Representation) e introduce un nuevo dialecto y arquitectura de tiempo de ejecución.

1. El dialecto MLIR `kmrt`

KeyMemRT introduce un nuevo dialecto llamado kmrt para representar la gestión de claves directamente dentro de la IR.

Nuevos Tipos: Define un tipo rot_key parametrizado por el índice de rotación, lo que permite al compilador distinguir entre claves para diferentes índices.
Nuevas Operaciones: El dialecto incluye operaciones para la gestión explícita de claves:
- kmrt.load_key: Carga una clave de rotación específica.
- kmrt.clear_key: Elimina una clave de la memoria.
- kmrt.prefetch_key: Proporciona pistas al tiempo de ejecución para la carga asíncrona.
- kmrt.use_key / kmrt.assume_key: Gestionan el alcance y la vivacidad de la clave.
Integración: El compilador reduce las operaciones de alto nivel (por ejemplo, desde el dialecto ckks vía HEIR) al dialecto openfhe, insertando operaciones kmrt para gestionar los ciclos de vida de las claves.

2. Pipeline de Optimización del Compilador

El compilador KeyMemRT realiza una serie de pasadas de reducción y optimización para reducir la huella de memoria sin sacrificar el rendimiento:

Reducción de CKKS a OpenFHE: Asocia cada operación de rotación con un valor rot_key específico, invirtiendo el problema de la creación de rangos de vivacidad hacia la fusión de los mismos.
Descomposición Baby-Step Giant-Step (BSGS): Reduce el número de claves requeridas de $N$ a $\approx 2\sqrt{N}$ para índices de rotación consecutivos mediante la encadenación de rotaciones. Esto es particularmente efectivo para patrones de multiplicación de matriz-vector.
Fusión de Claves de Rotación (Merge Rotation Keys): Utiliza análisis de flujo de datos para detectar secuencias donde una clave es eliminada y acto seguido recargada con el mismo índice, eliminando pares redundantes de carga/eliminación.
Elevación de Rotación (Rotation Hoisting): Identifica patrones de rotación aplicados a entradas comunes y los transforma en alternativas más rápidas soportadas por la librería OpenFHE.
Gestión de Claves de Bootstrap: Materializa las claves de rotación internas utilizadas por las operaciones de bootstrap (que refrescan los niveles del criptograma) en la IR. Esto permite al compilador gestionar las claves de bootstrap con el mismo control de grano fino que las claves de rotación explícitas, una característica que no había sido abordada previamente.
Eliminación de Subexpresiones Comunes (CSE): Elimina el código muerto resultante de las optimizaciones de claves.
Colocación de Pistas (Hint Placement): Inserta pistas de prefetch_key para permitir que el tiempo de ejecución superponga la carga de claves con la computación.

3. Entorno de Ejecución (Runtime) de KeyMemRT

El entorno de ejecución actúa como intermediario entre el código C++ compilado y la librería FHE (OpenFHE). Gestiona la carga y descarga dinámica de claves desde el disco a la RAM basándose en las pistas insertadas por el compilador.

Modo de Baja Memoria (Low-Memory Mode): Ejecuta las directivas secuencialmente, cargando las claves solo cuando son estrictamente necesarias para minimizar el uso pico de memoria.
el Modo Equilibrado (Balanced Mode): Utiliza un mecanismo de prelectura (prefetching) para cargar las claves en paralelo con la computación. Mantiene una cola interna, cargando claves por adelantado hasta un límite definido por el usuario y eliminándolas cuando se necesita espacio, reduciendo así la sobrecarga de latencia.

Contribuciones Clave

Nuevo Dialecto MLIR (kmrt): El primer dialecto que expone las claves de rotación como elementos de la IR con tipos específicos y operaciones de gestión de memoria, permitiendo un análisis de grano fino.
Gestión Automática de Claves de Grano Fino: El primer compilador FHE que rastrea automáticamente la vivacidad de las claves, optimiza las claves de bootstrap y gestiona los ciclos de vida de las claves individualmente en lugar de como un conjunto global.
Marco de Trabajo de Tiempo de Ejecución: Un entorno de ejecución que soporta la carga y eliminación de claves bajo demanda, utilizando pistas del compilador para superponer la E/S con la computación.
Integración: Una cadena de herramientas de compilación post-optimización que puede ser objetivo de los frontends FHE existentes (demostrado con Orion y HEIR).

Resultados

Los autores evaluaron KeyMemRT frente a dos enfoques de vanguardia: ANT-ACE (que mantiene todas las claves en memoria) y Fhelipe (que utiliza la descomposición para reducir las claves pero aumenta la latencia). Los benchmarks incluyeron varios modelos de ML (MLP, LoLa, LeNet, variantes de ResNet, AlexNet) con parámetros FHE configurados con una dimensión de anillo de $2^{16}$ y una profundidad multiplicativa de 30.

Reducción de Memoria:
- Comparado con ANT-ACE, KeyMemRT logró una reducción de memoria de media geométrica de 1.74x. En casos específicos como LeNet, el uso de memoria se redujo en 2.59x.
- Comparado con Fhelipe, KeyMemRT logró una reducción de memoria de 1.16x.
Latencia/Aceleración (Speedup):
- Comparado con ANT-ACE, KeyMemRT (modo Balanced) logró una aceleración de 1.20x.
- Comparado con Fhelipe, KeyMemRT logró una aceleración significativa de 1.73x (media geométrica), con mejoras de hasta 2.5x en AlexNet. Esto se debe a que KeyMemRT evita la sobrecarga computacional de la encadenación de rotaciones requerida por Fhelipe.
Escalabilidad: KeyMemRT demostró la capacidad de ejecutar programas grandes (por ejemplo, ResNet-50) que excedían los 100 GB de requisitos de memoria bajo ANT-ACE, manteniendo el uso de memoria significativamente más bajo.

Significado y Reivindicaciones

El artículo afirma que KeyMemRT es el primer compilador FHE que proporciona gestión automática y de grano fino de las claves y de las claves de bootstrap. Los autores sostienen que este trabajo desbloquea la escalabilidad de memoria para FHE, permitiendo que programas arbitrariamente grandes se ejecuten sin la carga prohibitiva de almacenar todas las claves de rotación simultáneamente.

Al desacoplar el uso de memoria del número total de claves y, en su lugar, gestionar las claves basadas en su vivacidad, KeyMemRT permite que los programas FHE escalen mejor en el hardware existente. Los autores enfatizan que su enfoque no compromete el rendimiento; a diferencia de los métodos basados en la descomposición que intercambian memoria por velocidad, KeyMemRT logra tanto la reducción de memoria como la mejora de la latencia al cargar solo las claves necesarias en el momento preciso en que se necesitan. Esto aborda una barrera crítica para la adopción de FHE.