💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Este artículo propone un método optimizado de multiplicación de cifrados de múltiples entradas para el cifrado homomórfico que se extiende más allá de dos entradas mediante cálculos reformulados, claves de evaluación adicionales y un enfoque de reescalado multinivel, dando como resultado arquitecturas de hardware que reducen significativamente el área lógica y la latencia en comparación con diseños anteriores.

Autores originales: Sajjad Akherati, Xinmiao Zhang

Publicado 2026-05-19

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Sajjad Akherati, Xinmiao Zhang

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 eres un chef maestro intentando hornear un pastel, pero hay un truco: debes hacer toda la mezcla y el horneado mientras llevas puestos guantes de horno gruesos y pesados que te impiden sentir los ingredientes o ver el tazón. Esto es la Cifrado Homomórfico (HE). Permite que las computadoras realicen operaciones matemáticas sobre datos "cifrados" (la masa del pastel dentro de los guantes) sin descifrarlos nunca (quitarse los guantes). Esto mantiene los secretos a salvo, ya sean tus registros médicos o tu saldo bancario.

Sin embargo, hacer matemáticas con estos "guantes" es increíblemente lento y desordenado. El mayor cuello de botella es la multiplicación. En el cifrado estándar, solo puedes multiplicar dos ingredientes a la vez. Pero muchas tareas modernas, como entrenar una IA para reconocer una enfermedad o analizar tendencias financieras complejas, requieren multiplicar muchos ingredientes (textos cifrados) juntos a la vez.

Este artículo presenta una nueva forma super eficiente de multiplicar estos ingredientes cifrados, específicamente para un método de cifrado popular llamado CKKS. Aquí está el desglose de su avance utilizando analogías simples:

1. El Problema: La "Cocina Desordenada"

Cuando multiplicas números cifrados, el "ruido" (el desorden creado por los guantes de horno) se vuelve cada vez más fuerte. Si multiplicas demasiados números a la vez sin limpiar, el ruido ahoga los datos reales y el resultado se convierte en basura.

Para solucionarlo, el sistema de cifrado debe realizar un paso de "limpieza" llamado Reescalado después de cada multiplicación. Piensa en esto como detenerse a limpiar la encimera y volver a ordenar los ingredientes.

La Vieja Forma: Si necesitabas multiplicar 10 ingredientes, el método antiguo era como una cinta transportadora donde multiplicabas dos, te detenías a limpiar, multiplicabas dos más, te detenías a limpiar, y así sucesivamente. Era lento y requería muchos suministros de limpieza (recursos de hardware).
El Intento Previo de "Tres Ingredientes": El trabajo anterior de los autores mostró que podías multiplicar tres ingredientes a la vez, lo cual era más rápido. Pero aún tenía muchos pasos de limpieza innecesarios.

2. La Solución: La "Línea de Ensamblaje Inteligente"

Los autores proponen dos mejoras mayores para hacer este proceso más rápido y pequeño:

A. La "Limpieza de Un Solo Paso" (Multiplicación Mejorada de 3 Entradas)

En su nuevo diseño para multiplicar tres ingredientes, se dieron cuenta de que estaban realizando la limpieza (Reescalado) y el reordenamiento (Relinealización) de una manera torpe y indirecta.

La Analogía: Imagina que tienes tres tazones de masa. El método antiguo era mezclarlos, verter la mezcla en un tazón nuevo, limpiar los tazones viejos, verter la mezcla de nuevo y limpiar de nuevo.
La Solución: Rediseñaron el proceso para que puedas mezclar y limpiar en un solo movimiento fluido. Descubrieron cómo combinar los pasos de limpieza para que no tengas que detenerte y limpiar la encimera tantas veces.
El Resultado: Su nuevo "mezclador de tres tazones" es un 50% más rápido (latencia) y ocupa un 15% menos de espacio en el chip (área) en comparación con su diseño anterior más eficiente.

B. La "Limpieza en Grupo" (Multiplicación de Múltiples Entradas)

¿Qué pasa si necesitas multiplicar cuatro, cinco o incluso doce ingredientes a la vez?

La Vieja Forma: Construirías una larga fila de "mezcladores de dos tazones". Mezclas dos, limpias, mezclas dos más, limpias, luego mezclas los resultados, limpias de nuevo. Esto crea una fila muy larga (alta "profundidad multiplicativa"), lo que significa que el ruido se acumula demasiado rápido.
La Nueva Estrategia: Los autores se dieron cuenta de que si agrupas tus ingredientes de manera diferente, puedes realizar una "Limpieza en Grupo".
- En lugar de limpiar después de cada paso individual, desarrollaron un truco matemático (llamado Multi-Reescalado) que te permite esperar y limpiar múltiples capas de desorden a la vez.
- La Analogía: Imagina que estás lavando platos. En lugar de lavar un plato, secarlo y guardarlo, luego lavar una taza, secarla y guardarla, lavas toda una pila de platos, luego secas toda la pila y luego guardas todo. Haces la "secado" (la parte costosa y lenta) solo una vez para todo el grupo.
El Resultado: Al reorganizar cómo agrupan los ingredientes (la "partición"), pueden combinar estos pasos de limpieza. Para multiplicar entre 4 y 12 ingredientes, su nuevo método ahorra un 32% del espacio y reduce el tiempo a la mitad (45% más rápido) en comparación con la antigua línea "de dos en dos".

3. Por Qué Esto Importa (Según el Artículo)

El artículo se centra estrictamente en la arquitectura de hardware—el diseño físico del chip de computadora que realiza estas matemáticas.

Demostraron que al cambiar cómo se organiza la matemática (el algoritmo) y cómo se construye el chip (la arquitectura), se puede realizar matemáticas cifradas complejas mucho más rápido.
Mencionan específicamente que esto ayuda con aplicaciones como el aprendizaje automático, el diagnóstico médico y el análisis financiero, porque estos campos a menudo requieren multiplicar muchos puntos de datos cifrados juntos.

Resumen

Piensa en este artículo como la invención de una nueva cocina super eficiente para un chef que no puede quitarse los guantes de horno.

Descubrieron cómo mezclar tres ingredientes a la vez sin hacer un desastre.
Inventaron una forma de limpiar múltiples capas de desorden al mismo tiempo, en lugar de una por una.
El resultado es una cocina que es más pequeña, más rápida y requiere menos energía para mantener los secretos a salvo mientras se realiza matemáticas complejas.

Los autores no probaron esto en pacientes reales ni en cuentas bancarias reales en este artículo; solo demostraron que la máquina diseñada para hacer este trabajo es significativamente mejor que las máquinas que teníamos antes.

Resumen Técnico: Multiplicación de Cifrado con Múltiples Entradas para Criptografía Homomórfica

Enunciado del Problema
La criptografía homomórfica (HE), particularmente el esquema RNS-CKKS, permite operaciones aritméticas sobre datos cifrados, lo cual es crítico para aplicaciones que preservan la privacidad como el aprendizaje automático y el diagnóstico médico. Sin embargo, los esquemas HE estándar definen la multiplicación de cifrados únicamente para dos entradas. Muchas aplicaciones prácticas, como aproximaciones polinómicas de alto orden para funciones de activación de redes neuronales (por ejemplo, ReLU), árboles de decisión y secuenciación genómica, requieren la multiplicación de múltiples cifrados ( $n > 2$ ).

Los enfoques existentes para manejar la multiplicación con múltiples entradas suelen encadenar múltiples multiplicadores de dos entradas en una estructura de árbol binario. Este método adolece de dos ineficiencias principales:

Alta Latencia y Área: Multiplicar secuencialmente $n$ cifrados utilizando unidades de dos entradas resulta en una sobrecarga de hardware y una latencia significativas.
Crecimiento del Ruido y Sobrecarga de Reescalado: Cada multiplicación aumenta el nivel de ruido, lo que hace necesaria una operación de reescalado para restaurar la escala del mensaje. En un árbol binario estándar, el reescalado debe ocurrir después de cada paso de multiplicación para evitar un crecimiento exponencial del ruido. Esto resulta en un gran número de unidades de reescalado, cada una requiriendo costosas operaciones de Transformada Numérica Teórica (NTT) y Transformada Numérica Teórica Inversa (INTT), aumentando significativamente la complejidad computacional y el uso de recursos de hardware.

Metodología
El artículo propone un marco para la multiplicación directa de $n$ cifrados que minimiza la profundidad multiplicativa y la complejidad del hardware. La metodología se divide en dos contribuciones principales:

Multiplicador de Tres Entradas Mejorado:
Los autores reformulan primero el proceso de multiplicación de tres entradas. En el trabajo preliminar [26], la relinearización y el reescalado se realizaban por separado, requiriendo múltiples operaciones ModUp/ModDown y numerosos bloques (I)NTT. El nuevo diseño:
- Reformula la Relinearización: Al mover el factor de escala $P^{-1}$ a la conversión de base (BConv) y a la multiplicación de la clave de evaluación, el diseño elimina los pasos de escala separados.
- Optimiza el Reescalado: Los autores reestructuran la ruta de datos para realizar el reescalado en el dominio original antes de la NTT final, en lugar de en el dominio NTT. Esto permite eliminar operaciones (I)NTT redundantes.
- Resultado: Estos cambios reducen el número de bloques (I)NTT en la ruta de datos de ocho a cuatro, reduciendo efectivamente a la mitad la longitud de la ruta de datos.
Extensión a Múltiples Entradas con Reescalado Combinado:
Para extender la multiplicación a $n > 3$ entradas sin aumentar la profundidad multiplicativa, el artículo introduce:
- Claves de Evaluación Generalizadas: Se introducen nuevas claves de evaluación ( $ek_t$ ) para relinearizar los términos polinómicos de grado superior ( $d_t s^t$ ) generados al multiplicar $n$ cifrados, reduciendo el resultado nuevamente a un formato de dos polinomios.
- Algoritmo de Reescalado Múltiple (Multi-RS): Un análisis teórico identifica las condiciones bajo las cuales múltiples operaciones de reescalado pueden retrasarse y combinarse. Los autores proponen un algoritmo que realiza $\mu$ operaciones de reescalado concatenadas utilizando el mismo número de operaciones (I)NTT que un solo reescalado. Esto se logra transformando la entrada al dominio INTT, realizando reescalado iterativo en el dominio de coeficientes y transformando de nuevo, utilizando constantes precalculadas para fusionar las operaciones.
- Directrices de Partición de Entradas: El artículo proporciona directrices para particionar $n$ entradas en grupos (por ejemplo, $(n_1, n_2, \dots, n_m)$ ) para maximizar el número de operaciones de reescalado combinadas mientras se mantiene la profundidad multiplicativa óptima de $\lceil \log_2 n \rceil$ . Esto implica crear estructuras de árbol desequilibradas siempre que sea posible para agrupar más entradas antes de un paso de reescalado.

Contribuciones Clave

Reformulación Algorítmica: Una nueva formulación para la multiplicación de tres entradas que combina cálculos intermedios, reduciendo el número de operaciones (I)NTT y acortando la ruta de datos.
Marco de Múltiples Entradas: Una extensión de la multiplicación de cifrados a $n$ entradas arbitrarias utilizando claves de evaluación generalizadas y un multiplicador con estructura de árbol.
Reescalado Combinado: Un algoritmo novedoso de reescalado múltiple que reduce la complejidad de realizar múltiples reescalados a la de un solo reescalado, independientemente del número de pasos combinados ( $\mu$ ).
Arquitectura de Hardware: Diseño de arquitecturas de hardware totalmente pipelineadas para los multiplicadores propuestos, incluidas unidades de ModUp, ModDown y reescalado optimizadas.

Resultados
Los diseños propuestos fueron sintetizados utilizando el proceso GlobalFoundries 22FDX con parámetros $N=2^{16}$ , $L=K=24$ y $w=64$ .

Multiplicador de Tres Entradas: En comparación con el trabajo anterior [26], el multiplicador de tres entradas mejorado logra una reducción del 15% en el área lógica y una reducción del 50% en la latencia. También reduce los requisitos de memoria en aproximadamente un 20% debido a la menor cantidad de unidades (I)NTT.
Multiplicadores de Múltiples Entradas ( $n=4$ a $12$): En comparación con una implementación de referencia que utiliza un árbol binario de multiplicadores de dos entradas, el método propuesto logra una reducción promedio del 32% en el área total y una reducción del 45% en la latencia.
Eficiencia de Reescalado: Para entradas que no son potencias de dos (por ejemplo, $n=17$ ), la partición optimizada combinada con el reescalado múltiple reduce el número total de unidades de reescalado (y las operaciones (I)NTT asociadas) en aproximadamente un 47% en comparación con el enfoque estándar de árbol binario.

Significado
El artículo afirma que estas mejoras abordan el cuello de botella de la multiplicación con múltiples entradas en HE, lo cual es esencial para aplicaciones complejas de preservación de la privacidad. Al reducir la complejidad del hardware y la latencia de la multiplicación de cifrados, la arquitectura propuesta hace más factible el despliegue de HE en entornos con recursos limitados o de alto rendimiento. El trabajo demuestra que, mediante la reformulación algorítmica y una partición cuidadosa de las entradas, la sobrecarga de la gestión del ruido (reescalado) puede minimizarse significativamente sin comprometer la seguridad o la corrección del esquema de cifrado. Los autores señalan que el trabajo futuro se centrará en simplificar aún más los multiplicadores para un número aún mayor de entradas.