💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

Este artículo presenta Sparse Roots of Unity (SPRU), un novedoso algoritmo de bootstrapping para el esquema de cifrado homomórfico CKKS que integra la aritmética modular en raíces de la unidad complejas para reducir significativamente la profundidad multiplicativa y lograr una mejora de hasta 5 veces en la latencia en comparación con los métodos tradicionales.

Autores originales: Jean-Sebastien Coron, Robin Koestler

Publicado 2026-07-31

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Jean-Sebastien Coron, Robin Koestler

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 enviar un mensaje secreto a un amigo, pero no puedes confiar en la oficina de correos. Guardas tu carta en una caja con llave, pero la oficina de correos necesita clasificarla, apilarla y quizás incluso abrirla para revisar la dirección sin ver nunca lo que hay dentro. Esta es la magia del Cifrado Totalmente Homomórfico (FHE). Permite que las computadoras realicen cálculos sobre datos que aún están en su forma cifrada y cerrada. Piensa en ello como una cocina mágica donde puedes hornear un pastel usando ingredientes que todavía están en sus paquetes sellados y sin abrir; el horno hace el trabajo, y cuando finalmente abres la caja al final, tienes un pastel fresco, pero el horno nunca supo cuáles eran los ingredientes.

Sin embargo, hay un inconveniente. Cada vez que la computadora realiza una operación matemática en estos datos bloqueados, se añade un poco de "ruido" o estática, como si se asentara polvo sobre una lente. Si realizas demasiados cálculos, el ruido se vuelve tan fuerte que el mensaje se vuelve confuso e ilegible. Para solucionar esto, los científicos utilizan un proceso llamado bootstrapping (reinicio de cifrado). Es como un botón de reinicio mágico: la computadora toma la caja ruidosa y bloqueada, realiza un truco complejo para limpiar el polvo y coloca el mensaje de nuevo en una caja nueva y limpia para que los cálculos puedan continuar. El problema es que este truco de limpieza es increíblemente lento y pesado, como intentar lavar un coche con un cepillo de dientes. Requiere tanta potencia de cómputo que ralentiza todo, haciendo que las aplicaciones del mundo real se sientan pesadas.

Aquí es donde entra en juego un nuevo artículo de Jean-Sébastien Coron y Robin Köstler. Ellos introducen una nueva y astuta forma de realizar este proceso de "limpieza", llamada bootstrapping por Raíces de la Unidad Dispersas (SPRU). En lugar de usar el método antiguo, pesado y tosco, que intenta aproximar una curva compleja (como una onda senoidal), ellos encontraron una forma de mapear los datos directamente en un círculo de números llamado "raíces de la unidad". Imagina que, en lugar de fregar el coche con un cepillo de dientes, simplemente deslizas el coche sobre un carrusel gigante que gira y limpia el polvo de forma natural mientras gira. Su método es mucho más rápido y ligero, especialmente cuando se trata de un pequeño número de elementos de datos a la vez. Al usar este nuevo enfoque, demostraron que el tiempo necesario para reiniciar el cifrado puede reducirse hasta en un 5 veces en comparación con el método estándar, haciendo que la magia de la computación secreta se sienta mucho más como una realidad que como un sueño lejano.

La forma antigua: El cargador pesado

Para entender por qué este nuevo truco es tan especial, veamos cómo funcionaba el método antiguo. En el esquema de cifrado CKKS estándar (el más popular para hacer matemáticas con decimales), el proceso de bootstrapping era como intentar adivinar la forma de una montaña dibujando una línea suave sobre ella. La computadora tenía que evaluar un polinomio complicado (una fórmula matemática elegante) que aproximaba una "reducción modular". Piensa en la reducción modular como una forma de envolver una línea numérica larga en un círculo para que quepa de nuevo en una caja pequeña. El método antiguo intentaba dibujar una onda senoidal (una línea ondulada) para imitar este proceso de envolver.

Aunque esto funcionaba, era un esfuerzo pesado. Requería una profunda pila de operaciones matemáticas, lo que significaba que la computadora tenía que usar un "dimensión de anillo" muy grande (una medida del tamaño del patio de juegos matemático). Esto era como intentar correr un maratón cargando una mochila pesada; ralentizaba todo y limitaba cuánto trabajo útil se podía realizar después del reinicio. Los autores señalan que esta alta "profundidad multiplicativa" (el número de capas de matemáticas por las que tienes que pasar) era el principal cuello de botella, haciendo que el proceso fuera demasiado lento para su uso práctico, especialmente cuando solo necesitabas procesar unos pocos números a la vez.

La nueva forma: El carrusel de las raíces

La nueva idea de los autores, el bootstrapping SPRU, cambia las reglas del juego al saltarse la pesada aproximación por completo. En lugar de intentar dibujar una línea ondulada para imitar el envoltorio, se dieron cuenta de que simplemente podían embeber los datos directamente en las "raíces de la unidad".

Aquí hay una analogía sencilla: imagina que el método antiguo era como intentar traducir un código secreto escribiendo una entrada de diccionario larga y complicada para cada letra. Tomaba una eternidad. El nuevo método es como darse cuenta de que el código secreto es en realidad un conjunto de llaves que encajan perfectamente en una cerradura específica. En lugar de traducir, simplemente giras la llave.

En términos técnicos, mapean el grupo aditivo (la forma en que los números se suman) directamente en las raíces de la unidad compleja (puntos en un círculo dentro del sistema de números complejos). Debido a que el esquema de cifrado CKKS entiende nativamente estos números complejos, la computadora puede realizar la operación de "limpieza" directamente, sin necesidad de aproximar una onda senoidal. Es como cambiar la construcción de un puente con ladrillos individuales por el uso de un arco prefabricado que encaja perfectamente.

La salsa secreta: Dispersión y empaquetado

El artículo no se detiene solo en el nuevo mapa; también introdujeron dos optimizaciones ingeniosas para hacerlo aún más rápido, especialmente cuando se trata de un pequeño número de ranuras de datos (como una lista de pocos números).

Empaquetar los bits: En los viejos tiempos, si tenías una clave secreta de 1,000 bits, la computadora tenía que manejar cada bit uno por uno. Los autores se dieron cuenta de que podían "empaquetar" estos bits en las ranuras del cifrado, como meter 1,000 cartas en un único buzón súper eficiente. Esto redujo la cantidad de cálculos pesados necesarios de una cantidad masiva a una cantidad logarítmica (piensa en ello como reducir una lista larga a un resumen corto).
El truco del bloque disperso: También asumieron que la clave secreta tenía una estructura especial: en lugar de bits aleatorios, la clave se dividía en bloques donde solo un bit de cada bloque era un "1" y el resto eran "0". Esto es como tener una fila de interruptores de luz donde solo uno está encendido en cada grupo de diez. Al usar esta estructura "dispersa", pudieron reemplazar muchas operaciones de multiplicación difíciles por simples pasos de suma. Es la diferencia entre multiplicar una lista larga de números y simplemente sumar unos pocos de ellos. Esto redujo la "profundidad" del cálculo aún más, pasando de una torre profunda a una pequeña escalera.

Los resultados: Acelerando la magia

Los autores probaron su nuevo método utilizando la biblioteca OpenFHE, una herramienta popular para construir software de cifrado. Compararon su bootstrapping SPRU contra el método original y pesado.

Los resultados fueron sorprendentes para escenarios específicos. Cuando se realizaba el bootstrapping de cifrados con un pequeño número de ranuras (algo común en muchas aplicaciones del mundo real), su nuevo método fue hasta 5 veces más rápido (una reducción de latencia de 5x). Esto es algo enorme porque significa que el "botón de reinicio" no tiene que esperar tanto tiempo, permitiendo que la computadora vuelva a realizar trabajo útil mucho más rápido.

Sin embargo, el artículo es cuidadoso al notar que esto no es una solución mágica para cada situación. Si intentas procesar un número masivo de ranuras (una lista enorme de datos), el método original podría seguir siendo más eficiente. Pero para los muchos casos en los que manejamos lotes de datos más pequeños, este nuevo enfoque ofrece una aceleración significativa.

Por qué es importante

La belleza de este trabajo es que no solo ajusta los números; cambia fundamentalmente la forma en que pensamos sobre el proceso de bootstrapping. Al alejarse de las pesadas aproximaciones polinómicas y abrazar las capacidades nativas del esquema de cifrado, los autores han demostrado que podemos hacer que el cifrado totalmente homomórfico sea mucho más práctico.

Demostraron que, al usar estas "raíces de la unidad" y técnicas de empaquetado inteligente, podemos reducir significativamente el tiempo y la potencia de cómputo necesarios para mantener los datos cifrados utilizables. Aunque el artículo se centra en los detalles técnicos y las matemáticas detrás de escena, la conclusión es clara: la posibilidad de realizar cálculos complejos sobre datos secretos sin ralentizarse está un poco más cerca de la realidad. Los autores han proporcionado una forma más ligera y rápida de mantener viva la magia, haciendo posible imaginar un futuro donde tus datos privados puedan ser procesados en la nube sin ser vistos jamás, y sin tener que esperar una eternidad por el resultado.

Resumen Técnico: Arranque de Bajo Latencia para CKKS mediante Raíces de la Unidad

Planteamiento del Problema

El esquema de cifrado homomórfico CKKS soporta aritmética aproximada sobre números complejos, lo que lo hace adecuado para el aprendizaje automático seguro y la computación en la nube. Sin embargo, un cuello de botella crítico en CKKS es el procedimiento de bootstrapping (arranque), el cual es necesario para refrescar los cifrados y permitir una profundidad de computación ilimitada.

El método original de bootstrapping de CKKS [CHK+18a] depende de la evaluación homomórfica de una aproximación polinómica de la función de reducción modular (específicamente, una función seno escalada). Este enfoque sufre de dos desventajas principales:

Alta Profundidad Multiplicativa: La aproximación polinómica requiere un circuito profundo, lo que exige un módulo de cifrado grande.
Ineficiencia para Pocos Slots: La complejidad del método original escala con el número de slots ( $n$ ) y la dimensión del anillo ( $N$ ), requiriendo a menudo $O(\log n + \log N)$ operaciones. Esta alta profundidad obliga al uso de dimensiones de anillo más grandes para mantener la seguridad, lo que aumenta la latencia.

Los autores identifican la necesidad de un algoritmo de bootstrapping que reduzca la profundidad multiplicativa, permitiendo así dimensiones de anillo más pequeñas y una latencia significativamente menor, particularmente para cifrados con un pequeño número de slots.

Metodología: Raíces de la Unidad Dispersas (SPRU)

El artículo introduce el bootstrapping de Raíces de la Unidad Dispersas (SPRU), un nuevo algoritmo que cambia fundamentalmente la forma en que se realiza la reducción modular en CKKS.

Concepto Central: Inmersión Nativa

En lugar de aproximar la reducción modular mediante una función seno, el bootstrapping SPRU inserta directamente el grupo aditivo $\mathbb{Z}_q$ en el grupo multiplicativo de las raíces de la unidad complejas. Los autores utilizan el homomorfismo:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

Para una ecuación de decodificación tipo LWE $m = \langle s, c \rangle \pmod q$ , los autores observan que:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Dado que los bits de la clave secreta $s_k \in \{0, 1\}$ actúan como selectores, este producto puede reescribirse como:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
Al aislar la parte imaginaria y aplicar un factor de escala lineal, se puede recuperar el mensaje original $m$ . Esta ecuación puede evaluarse homomórficamente dentro del esquema CKKS sin la aproximación polinómica de la función seno.

Optimizaciones Clave

Para hacer práctico este enfoque, los autores introducen dos optimizaciones críticas:

Empaquetado de Bits de la Clave Secreta:
En lugar de cifrar cada bit de la clave secreta individualmente, los $N$ bits se empaquetan en los $N/2$ slots de dos cifrados CKKS. Los términos $(\exp(2i\pi \cdot c_k/q) - 1)$ son igualmente empaquetados. El producto de estos términos se calcula utilizando el Operador de Producto ( $Pr_{N/2 \to 1}$ ), el cual reduce el número de multiplicaciones homomórficas de $O(N)$ a $O(\log N)$ .
Clave Secreta de Bloque Disperso:
Los autores asumen una clave secreta estructurada dividida en $h$ bloques de tamaño $B = N/h$ , donde cada bloque contiene exactamente un bit no nulo (un '1'). Esta estructura permite que el producto dentro de cada bloque sea reemplazado por una suma.
- La suma dentro de los bloques se calcula mediante el Operador de Traza ( $Tr_{N/2 \to h}$ ), que involucra únicamente sumas y automorfismos (sin profundidad multiplicativa).
- El producto final se toma sobre los $h$ resultados de los bloques.
- Resultado: La profundidad multiplicativa se reduce de $\log_2 N + 2$ a $\log_2 h + 1$ . Dado que $h \ll N$ , esto reduce significativamente el tamaño del módulo requerido.

Extensión a Múltiples Slots

El método se generaliza para manejar $n$ slots (donde $n \le N/2$ ). Se extrae la matriz de decodificación y la ecuación de bootstrapping se aplica en paralelo a cada uno de los $n$ componentes del mensaje. La complejidad es $O(n + \log N)$ , la cual es asintóticamente mayor que el bootstrapping original de CKKS ( $O(\log n + \log N)$ ) para valores grandes de $n$ . Sin embargo, para valores pequeños de $n$ , la reducción en la profundidad multiplicativa produce un rendimiento práctico superior.

Contribuciones Clave

Algoritmo de Bootstrapping SPRU: Una nueva técnica de bootstrapping para CKKS que reemplaza la aproximación de la función seno por la evaluación nativa de las raíces de la unidad.
Reducción de la Profundidad Multiplicativa: Al aprovechar las claves secretas de bloques dispersos y el operador de traza, el algoritmo logra una profundidad multiplicativa de $O(\log h)$ , significativamente menor que la $O(\log N)$ del método original.
Implementación Optimizada: Los autores proporcionan una implementación de código abierto utilizando la biblioteca C++ OpenFHE, demostrando compatibilidad con la aritmética de Sistema de Número Residuo (RNS) y las optimizaciones existentes de transformación lineal (SlotToCoeff).
Análisis de Seguridad: Un análisis formal de la distribución de la clave binaria de bloque, mostrando que no debilita la seguridad del problema RLWE frente a ataques conocidos (ataques híbridos duales y de encuentro en el medio), siempre que los parámetros se ajusten correctamente.

Resultados

Los autores compararon el rendimiento del bootstrapping SPRU frente al bootstrapping original de CKKS utilizando la biblioteca OpenFHE con parámetros de seguridad de 128 bits.

Reducción de Latencia: Para cifrados con un número pequeño de slots, el bootstrapping SPRU logra una reducción de hasta 5 veces en la latencia.
Eficiencia: La reducción en la profundidad multiplicativa permite el uso de dimensiones de anillo más pequeñas, contribuyendo aún más a la aceleración.
Paralelismo: El método es altamente paralelizable; con $n$ procesadores, puede alcanzar una complejidad de $O(\log N)$ comparable a la del método original.

Significado y Reivindicaciones

El artículo afirma que el bootstrapping SPRU ofrece una alternativa práctica al bootstrapping original de CKKS, apuntando específicamente a escenarios donde la baja latencia es crítica y el número de slots es pequeño. Al evitar costosas aproximaciones polinómicas y reducir la profundidad multiplicativa, el método permite un refresco de cifrado más eficiente.

Los autores posicionan su trabajo como un paso significativo hacia la viabilidad de la computación totalmente homomórfica para aplicaciones del mundo real que requieren un bootstrapping frecuente. Señalan que, si bien su método está optimizado para conteos pequeños de slots, complementa el trabajo existente (como el trabajo independiente de Cheon et al. [CHKS25] que se centra en el bootstrapping completo de $N/2$ slots) al ofrecer un compromiso diferente que favorece la latencia sobre el paralelismo masivo para conjuntos de datos pequeños.

El artículo concluye que la reducción en la profundidad multiplicativa es el motor principal de la eficiencia, liberando más niveles de computación para operaciones útiles después del bootstrapping y permitiendo el uso de dimensiones de anillo más pequeñas y rápidas.