Modification to Fully Homomorphic Modified Rivest Scheme

Este documento describe el esquema totalmente homomórfico Rivest modificado (FHMRS), identifica una vulnerabilidad de seguridad en el mismo y propone una modificación (mFHMRS) para mitigar dicha falla.

Lo esencial

¡Claro que sí! Imagina que este documento es como un manual de instrucciones para un castillo de seguridad digital muy especial. Vamos a desglosarlo usando analogías sencillas.

1. El Problema Original: El "Cofre Transparente" (FHMRS)

Imagina que tienes un sistema para enviar mensajes secretos a través de una red pública (como internet). Quieres que las personas puedan hacer cálculos con esos mensajes (sumar o multiplicar) sin tener que abrir el cofre y ver el mensaje real. Esto se llama Cifrado Homomórfico.

• La idea original (FHMRS): Los autores crearon un sistema donde el mensaje se esconde dentro de un "cofre" matemático usando dos llaves secretas (números primos gigantes).
• El truco: Para que las sumas y multiplicaciones funcionen sin abrir el cofre, el mensaje se mezcla con un número aleatorio y un secreto más grande.
• El fallo: Los investigadores descubrieron un agujero en este castillo. Si un espía veía dos mensajes: uno que sabía que era "5" y su cofre cifrado, y otro que sabía que era "10" y su cofre, podía hacer una operación matemática sencilla (como restar y buscar un divisor común) para descubrir la llave maestra del sistema.
  • Analogía: Es como si alguien te dijera: "Mira, esta caja contiene 5 manzanas y esta otra 10. Si restas las cajas, el residuo me dice exactamente cuántas llaves usaste para cerrarlo". ¡El sistema original era demasiado predecible!

2. La Solución: El "Castillo de las Nueve Llaves" (mFHMRS)

Para arreglar esto, los autores (Sona Alex y Bian Yang) diseñaron una versión mejorada llamada mFHMRS. Aquí es donde entra la creatividad:

A. De dos guardias a muchos (De 2 primos a N+S primos)

En el sistema viejo, usabas solo dos números secretos (dos guardias) para proteger el mensaje. El espía podía engañarlos fácilmente.
En el nuevo sistema, usan muchos números secretos (digamos, 5, 10 o más guardias).

• Analogía: Imagina que en lugar de tener un cofre con dos cerraduras, tienes un cofre gigante que se abre solo si tienes todas las llaves de un set de 10 cerraduras diferentes. Si un espía intenta adivinar una llave basándose en un mensaje, se encuentra con que necesita adivinar 10 a la vez, lo cual es matemáticamente imposible en la vida humana.

B. El "Ruido" Aleatorio (Los números $g_i$)

El sistema añade una capa extra de "ruido" o desorden. Cada vez que se cifra un mensaje, se mezcla con un número aleatorio gigante que cambia cada vez.

• Analogía: Es como si cada vez que enviaras una carta, la metieras en un sobre, le añadieras arena, papel picado y un poco de agua, y luego la sellaras. Aunque el espía sepa qué carta enviaste, el "ruido" (la arena y el agua) es tan grande y variable que no puede limpiarlo para ver la llave secreta detrás.

C. La Regla de Oro: "Más grande que el mensaje"

El sistema tiene una regla estricta: El secreto principal ($u$) debe ser mucho más grande que cualquier mensaje que se vaya a procesar.

• Analogía: Imagina que el mensaje es un ratón y el secreto es un elefante. Si intentas esconder al ratón dentro del elefante, nadie puede decir "¡Ahí está el ratón!" solo mirando al elefante. El elefante es tan grande que el ratón se pierde en su interior.

3. ¿Cómo funciona la magia? (Las Operaciones)

Lo increíble de este sistema es que puedes hacer matemáticas con los cofres cerrados:

• Suma: Si tienes un cofre con "5 manzanas" y otro con "3 manzanas", puedes unir los cofres y el resultado será un nuevo cofre que, al abrirlo, dirá "8 manzanas". ¡Nadie vio las manzanas individuales!
• Multiplicación: Si multiplicas el cofre de "5" por el cofre de "3", el resultado es un cofre que dirá "15".
• El truco de la corrección: Al final, cuando el dueño legítimo abre el cofre, usa una herramienta matemática llamada Teorema Chino del Resto (imagina un rompecabezas donde tienes piezas de diferentes colores y debes armar la imagen completa). Como tienen todas las llaves secretas, pueden reconstruir el mensaje original perfectamente, eliminando todo el "ruido" y la arena que añadimos al principio.

4. ¿Por qué es seguro ahora?

El documento explica que, aunque un espía intente:

1. Adivinar a ciegas (Fuerza bruta): Tendría que probar más combinaciones de llaves que átomos en el universo.
2. Usar superordenadores (Ataques de retícula): Los matemáticos han diseñado el sistema para que, incluso usando las técnicas más avanzadas de computación cuántica o algoritmos de reducción de retículas, el "ruido" aleatorio sea tan grande que los cálculos fallen.
3. Ver patrones (Ataques de texto conocido): Como ahora hay muchas llaves y el ruido es enorme, no importa cuántos mensajes el espía vea, no puede deducir las llaves secretas.

En Resumen

Este papel presenta un sistema de encriptación superpoderoso que permite hacer cálculos sobre datos secretos sin revelar los datos.

• Antes: Tenía un agujero por el que un espía podía robar las llaves si veía dos mensajes.
• Ahora: Han cambiado el diseño para usar muchas llaves y mucho ruido aleatorio, haciendo que el castillo sea inexpugnable incluso para los espías más inteligentes.

Es como pasar de un candado de dos dígitos que cualquiera puede adivinar, a un sistema de seguridad que requiere que resuelvas un rompecabezas de 1000 piezas en el tiempo que tarda en caer una gota de lluvia. ¡Una mejora enorme para la privacidad en la nube!

Resumen técnico

Aquí tienes un resumen técnico detallado del documento en español, estructurado según los puntos solicitados:

Resumen Técnico: Modificación al Esquema Rivest Modificado de Homomorfismo Total (FHMRS)

Autores: Sona Alex y Bian Yang (NTNU, Noruega).
Contexto: El documento presenta una mejora de seguridad sobre el Esquema Rivest Modificado de Homomorfismo Total (FHMRS), identificando una vulnerabilidad crítica y proponiendo una versión modificada (mFHMRS) para mitigarla.

---

1. El Problema

El esquema original FHMRS es un sistema de cifrado simétrico basado en el Teorema del Resto Chino (CRT) que soporta operaciones homomórficas (suma, resta, multiplicación y multiplicación por constante). Sin embargo, el análisis del documento revela una vulnerabilidad crítica ante ataques de texto plano conocido (KPA) cuando el esquema soporta multiplicación homomórfica.

• La Vulnerabilidad: En el FHMRS original, si un atacante posee pares de (texto cifrado, texto plano), puede deducir el parámetro secreto $u$.
• El Mecanismo del Ataque:
  • El cifrado se realiza como $c_i = (m_i + g_i \cdot u) \pmod p$ y $\pmod q$.
  • Cuando el esquema soporta multiplicaciones consecutivas ($N$), los parámetros $p$ y $q$ deben ser lo suficientemente grandes para evitar desbordamientos. Esto implica que $p, q > (m_i + g_i \cdot u)$.
  • Como resultado, la operación de módulo no reduce el valor: $c_i = m_i + g_i \cdot u$.
  • Si un atacante conoce $m_i$ y $c_i$, puede calcular $c_i - m_i = g_i \cdot u$.
  • Al tener dos o más pares, el atacante puede calcular el Máximo Común Divisor (MCD) de $(c_1 - m_1)$ y $(c_2 - m_2)$, revelando directamente el secreto $u$. Una vez obtenido $u$, todo el sistema se compromete.

---

2. Metodología: Modificación a mFHMRS

Para mitigar esta vulnerabilidad, los autores proponen el mFHMRS (Modified FHMRS). La metodología central consiste en cambiar la arquitectura de dos primos secretos a un esquema de múltiples primos secretos y ajustar estrictamente los tamaños de los bits de los parámetros.

Cambios Clave en el Diseño:

1. Generación de Claves (KeyGen):

   • En lugar de dos primos ($p, q$), se generan $N+S$ primos secretos ($p_1, p_2, ..., p_{N+S}$) de tamaño similar, y un secreto $u$.
   • El módulo total $n$ es el producto de todos los primos: $n = p_1 \cdot p_2 \cdot ... \cdot p_{N+S}$.
   • Se introduce un parámetro $S$ (número de componentes extra) para asegurar que el tamaño de cada primo individual ($p_i$) sea lo suficientemente grande para resistir ataques, pero lo suficientemente pequeño para que la reducción módulo $p_i$ ocurra, evitando que el valor sea igual a $m + g \cdot u$.

2. Cifrado (Encrypt):

   • El mensaje $m_i$ se cifra como un vector de comparticiones: $c_i = (c_{i1}, c_{i2}, ..., c_{i(N+S)})$.
   • Cada componente se calcula como: $c_{ij} = (m_i + g_i \cdot u) \pmod {p_j}$.
   • Crucial: Se asegura que $p_j < (m_i + g_i \cdot u)$, por lo que la operación de módulo sí reduce el valor, impidiendo que el atacante obtenga directamente $g_i \cdot u$.

3. Propiedades Homomórficas:

   • El esquema mantiene la capacidad de realizar sumas, restas y multiplicaciones sobre los vectores de cifrado componente a componente.
   • La corrección de la decodificación depende de que el resultado de las operaciones homomórficas, antes de la reducción final por $u$, sea menor que $n$.

4. Restricciones de Seguridad (Tamaños de Bits):

   • Se definen relaciones estrictas entre los tamaños de bits de los mensajes ($l_m$), el secreto $u$ ($l_u$), los números aleatorios $g$ ($l_g$) y los primos $p$ ($l_p$).
   • Se exige que $l_p \ge \lambda$ (parámetro de seguridad) para evitar adivinanzas.
   • Se exige $l_u > l_p$ para evitar ataques basados en la resolución de ecuaciones lineales.
   • Se exige $l_g \ge \lambda/4$ para aumentar la complejidad de los ataques de fuerza bruta sobre los coeficientes aleatorios.

---

3. Contribuciones Clave

• Identificación de la Falta de Seguridad: Demostración formal de que el FHMRS original es inseguro bajo ataques de texto plano conocido debido a la falta de reducción modular en los primos grandes.
• Propuesta mFHMRS: Un nuevo esquema que utiliza múltiples primos secretos y una estructura de comparticiones CRT para garantizar que la reducción modular siempre ocurra, ocultando la relación lineal entre el texto plano y el cifrado.
• Análisis de Seguridad Exhaustivo: Evaluación del nuevo esquema contra múltiples vectores de ataque:
  • Ataque de Fuerza Bruta: Se demuestra que el espacio de claves es exponencialmente grande ($2^{490}$ en ejemplos dados).
  • Ataques Basados en Retículos (Lattice-based): Se analiza la resistencia contra algoritmos LLL (Lenstra–Lenstra–Lovász). Los autores demuestran que, debido a la elección de los tamaños de los primos y los errores introducidos, los vectores cortos necesarios para recuperar los secretos no son encontrables por LLL.
  • Ataques de Ecuaciones Lineales: Se muestra que resolver el sistema de ecuaciones para encontrar $u$ y los $p_i$ requiere probar un número prohibitivo de combinaciones de los valores aleatorios $g_i$ y los coeficientes de reducción $k_i$.

---

4. Resultados

• Corrección Matemática: Se demuestra que el esquema modificado permite la recuperación correcta del mensaje tras $N$ multiplicaciones y $A$ adiciones, siempre que se cumplan las desigualdades de tamaño de bits (ej. $l_p > \frac{(N+1)(l_g + l_u + 1) + A}{N+S}$).
• Resistencia a KPA: El ataque de MCD que rompió el esquema original ya no es viable porque $c_{ij} \neq m_i + g_i \cdot u$; la operación de módulo introduce un término de error desconocido ($k_{ij} \cdot p_j$) que impide aislar $u$.
• Complejidad Computacional:
  • Para un escenario con $\lambda=128$, $N=1$ y $A=20$, se requieren primos de 128 bits y $u$ de 130 bits.
  • La complejidad de un ataque de fuerza bruta se estima en aproximadamente $2^{490}$ operaciones, lo cual es computacionalmente inviable.
  • La complejidad de los ataques de texto plano conocido mediante resolución de ecuaciones lineales se reduce a un espacio de búsqueda de $2^{4 \cdot l_g + 2 \cdot (l_u - l_p)}$, que se mantiene alto gracias a la selección de$l_g \ge \lambda/4$.

---

5. Significado e Impacto

Este trabajo es significativo en el campo de la criptografía de homomorfismo total (FHE) por las siguientes razones:

1. Corrección de un Esquema Existente: No solo propone un nuevo algoritmo, sino que salva un esquema existente (FHMRS) que era prometedor por su simplicidad pero inseguro en su forma original.
2. Equilibrio entre Seguridad y Eficiencia: mFHMRS logra seguridad robusta sin depender de estructuras matemáticas extremadamente complejas (como los ideales en anillos de polinomios usados en FHE estándar como BGV/BFV), manteniendo una estructura basada en aritmética modular y CRT.
3. Análisis Riguroso: Proporciona una de las primeras evaluaciones detalladas de la seguridad de esquemas FHE basados en CRT frente a ataques de retículos y ecuaciones lineales, estableciendo guías claras sobre cómo dimensionar los parámetros ($l_p, l_u, l_g$) para garantizar seguridad.
4. Aplicabilidad: Al ser un esquema de clave simétrica, ofrece una alternativa potencialmente más eficiente en términos de gestión de claves para entornos específicos donde la sobrecarga de los esquemas de clave pública es un obstáculo, siempre que se apliquen las correcciones de seguridad propuestas.

En conclusión, el documento transforma un esquema vulnerable en una propuesta criptográfica sólida mediante una modificación estructural inteligente y un análisis de seguridad matemática riguroso.