💻 computer science

Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption

Este artículo presenta Recifhe, un nuevo compilador multinivel para el Cifrado Totalmente Homomórfico que logra una aceleración de 1.25x mediante la realización de optimizaciones globales al nivel del criptograma y la eliminación de computaciones redundantes al nivel polinómico de grano más fino.

Autores originales: Seongho Kim, Heelim Choi, Jaemin Kim, Seonyoung Cheon, Dongkwan Kim, Jaeho Lee, Hoyun Youm, Dongyoon Lee, Hanjun Kim, Yongwoo Lee

Publicado 2026-07-20

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Seongho Kim, Heelim Choi, Jaemin Kim, Seonyoung Cheon, Dongkwan Kim, Jaeho Lee, Hoyun Youm, Dongyoon Lee, Hanjun Kim, Yongwoo Lee

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 gigante, pero no se te permite mirar las piezas. En su lugar, tienes que resolver el rompecabezas usando unas gafas gruesas y empañadas que desenfocan cada forma y color. Este es el mundo del Cifrado Totalmente Homomórfico (FHE). Es un tipo de matemática mágica que permite a las computadoras procesar números sobre datos secretos sin llegar a ver realmente los datos en sí. Piensa en ello como una caja fuerte de un banco donde un robot puede contar tu dinero, sumar intereses y calcular tu saldo, todo mientras la puerta de la caja fuerte permanece cerrada y el robot nunca ve ni un solo billete.

Para que esta magia funcione, los datos secretos se transforman en algo llamado texto cifrado (ciphertext). Dentro de la computadora, este texto cifrado no es solo un gran bloque; es en realidad un polinomio masivo y complejo (una ecuación matemática elegante con muchos términos). Cuando la computadora realiza una tarea simple como "sumar estos dos números", en realidad está ejecutando una secuencia larga y sinuosa de pasos polinómicos más pequeños. El problema es que las herramientas de software que usamos para decirle a la computadora qué hacer han sido un poco torpes. Han estado tratando todo el texto cifrado como si fuera una única maleta pesada. Saben cómo empacar la maleta de manera eficiente, pero no miran dentro para ver si pueden reorganizar los artículos dentro de la maleta para ahorrar espacio o tiempo. Se pierden las pequeñas y ocultas oportunidades para hacer la matemática más rápida porque están mirando el problema desde demasiado lejos.

Aquí entra Recifhe, un nuevo y superinteligente compilador (un programa que traduce instrucciones humanas a código de máquina) creado por Seongho Kim y su equipo. Piensa en Recifhe como un organizador maestro que no solo mira la maleta; abre la maleta, saca cada uno de los artículos y reorganiza todo el montón para que el viaje sea más fluido.

Los investigadores descubrieron que, al observar el problema en dos niveles diferentes, podían acelerar las cosas significativamente. Primero, miraron el "nivel de texto cifrado", que es la visión general. Aquí, organizaron el flujo de datos para asegurarse de que el trabajo pesado ocurriera en los momentos adecuados. Pero la verdadera magia ocurrió en el "nivel de polinomio". Esta es la vista microscópica donde observaron los pasos matemáticos individuales. Notaron que la computadora a menudo estaba haciendo la misma matemática dos veces o cargando con "peso" extra (cálculos redundantes) que no era necesario.

Recifhe utiliza una estrategia ingeniosa llamada "elevación consciente del rendimiento" (performance-aware hoisting). Imagina que llevas una mochila pesada subiendo una colina. A veces, es mejor quitarse el objeto pesado de la espalda antes de empezar a caminar, llevarlo por separado y volver a ponérselo solo cuando sea absolutamente necesario. Recifhe hace esto con las operaciones matemáticas. Determina exactamente cuándo vale la pena mover un cálculo pesado a un lugar diferente en la secuencia. Si la matemática muestra que mover el cálculo ahorra más tiempo de lo que cuesta moverlo, el compilador lo hace. Si no, lo deja tal cual. Esto no es una suposición; el equipo midió el tiempo que tarda cada pequeño paso matemático en su hardware específico para asegurarse de que cada movimiento fuera rentable.

Los resultados son impresionantes. Cuando probaron Recifhe en 12 tareas diferentes, que iban desde problemas matemáticos simples hasta modelos de IA complejos como redes neuronales, funcionó 1.25 veces más rápido que los mejores métodos anteriores que solo miraban la visión general. Lo que es más importante, no solo se volvió más rápido; se volvió más inteligente con la memoria. Mientras que otros métodos que intentaban reorganizar la matemática a menudo causaban que la computadora se quedara sin memoria (como intentar meter demasiadas maletas en un coche diminuto), la programación cuidadosa de Recifhe mantuvo bajo el uso de memoria, utilizando solo 0.93 veces la memoria de las versiones optimizadas manualmente que se encuentran en las librerías existentes.

En resumen, el artículo muestra que al desvelar las capas de cifrado y optimizar los diminutos pasos matemáticos en su interior, podemos hacer que la computación secreta sea mucho más rápida y eficiente. Demuestra que no tienes que elegir entre seguridad y velocidad; con las herramientas adecuadas, puedes tener ambas.

Resumen Técnico: Recifhe – Optimización a Nivel de Cifrado y de Polinomio para el Cifrado Totalmente Homomórfico

Planteamiento del Problema
Los esquemas de Cifrado Totalmente Homomórfico (FHE), particularmente RNS-CKKS, permiten la computación preservadora de la privacidad sobre datos cifrados pero imponen cargas significativas de programación y rendimiento. Los programadores deben insertar manualmente operaciones de gestión de los cifrados (por ejemplo, Rescale, Bootstrap) para manejar atributos del cifrado como el nivel y la escala. Si bien los compiladores recientes de FHE automatizan este proceso, operan principalmente al nivel del cifrado, donde cada operación de cifrado se trata como una unidad atómica que comprende una secuencia de operaciones polinómicas. Esta granularidad gruesa provoca que los compiladores pierdan oportunidades de optimización de grano fino, como la eliminación de computaciones polinómicas redundantes que ocurren a través de diferentes operaciones de cifrado. Por el contrario, los enfoques existentes que descomponen las operaciones en secuencias polinómicas suelen limitar la optimización a una sola operación de cifrado debido a la complejidad, o dependen de optimizaciones de librerías manuales que utilizan algoritmos fijos. Estas optimizaciones manuales no logran adaptarse a flujos de datos variables, incurriendo a menudo en una sobrecarga de rendimiento innecesaria o en un crecimiento excesivo de la memoria al elevar incondicionalmente las operaciones a una base RNS más pesada (la base $PQ$) sin evaluar su rentabilidad.

Metodología
El artículo presenta Recifhe, un compilador multinivel diseñado para cerrar la brecha entre la optimización de nivel de cifrado de grano grueso y la optimización de nivel de polinomio de grano fino. Recifhe emplea una estrategia de Representación Intermedia (IR) de dos niveles:

Optimización a Nivel de Cifrado: Recifhe primero transforma un programa de entrada no-FHE (escrito en un DSL de Python) en un programa FHE. En este nivel, realiza optimizaciones globales como la colocación de operaciones de gestión de cifrado (Rescale, Bootstrap) y la aplicación de elevación de Rescale (Rescale hoisting). Este enfoque de grano grueso reduce la complejidad de la optimización global en comparación con operar directamente sobre toda la secuencia polinómica.
Optimización a Nivel de Polinomio: Después de reducir las operaciones de cifrado a sus secuencias polinómicas correspondientes, Recifhe realiza optimizaciones de grano fino a través de los límites de los cifrados. Las técnicas clave incluyen:
- Eliminación de Subexpresiones Comunes (CSE): Elimina computaciones polinómicas redundantes para entradas idénticas a través de diferentes secuencias reducidas.
- Elevación de ModDown Sensible al Rendimiento (Performance-Aware ModDown Hoisting): Esta es la innovación central. Recifhe identifica regiones donde múltiples operaciones ModDown (que reducen la base RNS de $PQ $a$ Q$) pueden consolidarse. A diferencia de los enfoques previos de algoritmo fijo, Recifhe utiliza perfilado offline para estimar la latencia de las operaciones tanto en las bases $Q$ como en $PQ$. Calcula el compromiso entre el beneficio de eliminar las operaciones ModDown y la sobrecarga de ejecutar operaciones insensibles (como sumas) en la base $PQ$ más pesada. La elevación se aplica solo cuando el beneficio de latencia estimado supera la sobrecarga.
- Fusión de Operaciones: Recifhe fusiona operaciones adyacentes (por ejemplo, ModDown y Rescale) para cancelar pares internos de Transformada de Número Teórico (NTT) e inversa NTT (iNTT), manteniendo los polinomios en el dominio de evaluación. Utiliza invModDown para elevar los operandos a la base $PQ$ cuando es necesario para permitir la fusión a través de operaciones intermedias.
- Programación Basada en la Vitalidad (Liveness-Driven Scheduling): Para contrarrestar el crecimiento de memoria inherente a la optimización a nivel de polinomio (causado por la extensión de la vida útil de los valores intermedios), Recifhe programa las operaciones para que sigan inmediatamente a sus operandos definidos más recientemente. Esto reduce los rangos de vida y permite la reutilización de buffers para valores muertos, mitigando la presión de memoria.

Contribuciones Clave

Arquitectura Multinivel: Un diseño de compilador novedoso que integra optimizaciones globales de nivel de cifrado con optimizaciones de grano fino de nivel de polinomio, abordando las limitaciones de los enfoques de granularidad única.
Elevación Adaptativa al Flujo de Datos: Un algoritmo de elevación de ModDown sensible al rendimiento que evalúa dinámicamente la rentabilidad de las transformaciones basándose en flujos de datos específicos y latencias de operación, evitando los problemas de las optimizaciones de algoritmo fijo.
Gestión de Memoria: Un mecanismo de programación basado en la vitalidad que apunta específicamente a la sobrecarga de memoria introducida por la optimización a nivel de polinomio, asegurando que las ganancias de rendimiento no se produzcan a costa de un uso excesivo de la memoria.
Suite de Optimización Integral: La integración de CSE, fusión de operaciones y programación sensible a la base para eliminar computaciones redundantes a través de los límites de las operaciones de cifrado.

Resultados
Recifhe fue evaluado en 12 benchmarks (incluyendo modelos de aprendizaje automático como LeNet, ResNet y VGG16) contra dos líneas base: un optimizador de solo nivel de cifrado y la librería optimizada manualmente Cheddar.

Rendimiento: Recifhe logró una aceleración de 1.25× sobre la línea base de solo nivel de cifrado en los 12 benchmarks. Comparado con la línea base de Cheddar, logró una aceleración de 1.36× en los 9 benchmarks donde Cheddar completó exitosamente. Notablemente, la línea base de Cheddar se ralentizó en 3 benchmarks (promediando 0.92× la velocidad de la línea base de solo cifrado) debido a optimizaciones incondicionales no rentables.
Huella de Memoria: Recifhe redujo el consumo de memoria en comparación con Cheddar, logrando 0.93× la huella de memoria de la línea base de Cheddar y 1.14× la de la línea base de solo cifrado. En contraste, Cheddar no pudo completar 3 benchmarks debido a errores de falta de memoria (OOM) causados por rangos de vida no gestionados.
Tiempo de Compilación: Los pasos de nivel de polinomio aumentaron el tiempo de compilación, representando en promedio el 39.0% del tiempo total de compilación (2.92× la media geométrica de la línea base de solo cifrado), siendo la elevación sensible al rendimiento y la fusión responsables del 1.31% y 14.3% del tiempo total, respectivamente.

Significancia
El artículo afirma que Recifhe demuestra la necesidad de la optimización multinivel en los compiladores FHE. Al ir más allá del nivel de cifrado, logra eliminar computaciones polinómicas redundantes que los compiladores anteriores y las optimizaciones de librerías manuales pasaron por alto. Crucialmente, demuestra que las optimizaciones a nivel de polinomio pueden aplicarse eficazmente sin incurrir en costos de memoria prohibitivos o penalizaciones de rendimiento, siempre que las transformaciones sean guiadas por el análisis de flujo de datos y el perfilado de latencia, en lugar de heurísticas fijas. Este trabajo establece un nuevo estándar para la compilación de FHE, ofreciendo un enfoque equilibrado que maximiza la velocidad de ejecución mientras gestiona las restricciones de memoria inherentes a las operaciones polinómicas complejas.

Más como este