Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

1. Problema Identificado

El esquema de cifrado homomórfico (HE) CKKS es ampliamente utilizado para el cálculo aproximado sobre números reales debido a su eficiencia. Sin embargo, presenta limitaciones críticas:

• Falta de soporte nativo para operaciones no lineales: CKKS soporta nativamente solo sumas y multiplicaciones. Funciones discontinuas o periódicas esenciales en criptografía y procesamiento de datos, como la función módulo (mod), son difíciles de calcular directamente sobre datos cifrados.
• Limitaciones de aproximación existente: Los métodos actuales para aproximar la función mod mediante polinomios solo son precisos en subrangos limitados del dominio de entrada. Fuera de estos rangos, el error de aproximación crece significativamente, lo que impide un uso global y preciso.
• Ineficiencia en el empaquetado de datos: En entornos con recursos limitados (como IoT o dispositivos móviles), la sobrecarga de comunicación y computación al cifrar y subir múltiples pequeños enteros a un servidor es alta. Las técnicas de empaquetado (packing) existentes no aprovechan eficientemente el espacio del texto plano de CKKS para datos de rango pequeño.

2. Metodología Propuesta

Los autores proponen una solución integral basada en la aproximación polinómica y nuevas técnicas de empaquetado de datos:

A. Aproximación Precisa de la Función mod

• Enfoque: En lugar de aproximar la función en todo el dominio continuo, el método se centra en la precisión en puntos enteros dentro de un intervalo acotado $[0, B]$.
• Técnica: Utilizan interpolación polinómica combinada con una serie de Chebyshev.
  • Mapean el intervalo de entrada a $[-1, 1]$.
  • Construyen un sistema de ecuaciones lineales basado en pares de muestras $(x, x \mod p)$ para enteros $x$.
  • Resuelven el sistema (subdeterminado cuando el grado del polinomio $D > B$) utilizando el método de mínimos cuadrados para obtener coeficientes con la norma $\ell_2$ mínima, garantizando estabilidad numérica.
• Estabilidad: Para evitar la amplificación de errores durante la evaluación homomórfica, introducen un factor de escala ($\delta$). Dividen los coeficientes de Chebyshev por $\delta$ para asegurar que los valores intermedios en la evaluación (usando el método Paterson-Stockmeyer) permanezcan por debajo de 1, minimizando el crecimiento del ruido.

B. Esquemas de Empaquetado de Datos (Data Packing)

Para datos de enteros pequeños, proponen dos métodos que aprovechan la función mod homomórfica para desempaquetar (unpacked) datos en el servidor:

1. BitStack:
   • Principio: Representa los datos como cadenas binarias y las concatena en un solo entero grande.
   • Desempaquetado: Utiliza la función mod homomórfica para extraer capas de bits secuencialmente.
   • Ventaja: Estructura compacta.
   • Desventaja: Desempaquetado serial que acumula errores y consume profundidad multiplicativa.
2. CRTStack (Basado en Teorema Chino del Resto):
   • Principio: Codifica los datos como un sistema de congruencias con módulos primos entre sí ($P_1, P_2, \dots, P_d$).
   • Desempaquetado: Permite el desempaquetado paralelo de las diferentes capas de datos utilizando mod con diferentes módulos, ya que las capas son independientes.
   • Ventaja: Mayor precisión y paralelismo, aunque requiere un rango de aproximación más amplio.

C. Combinación con otras técnicas

Los autores integran sus métodos con VecConcat (concatenación de vectores) e ImgConcat (uso de la parte imaginaria de CKKS para empaquetar dos vectores reales en uno complejo) para maximizar la utilización de los "slots" (huecos) del cifrado.

3. Contribuciones Clave

1. Aproximación Polinómica Global: Primer método que logra una aproximación precisa de la función mod en todos los puntos enteros de un intervalo acotado, superando las limitaciones de rangos parciales de trabajos anteriores.
2. Nuevos Esquemas de Empaquetado: Diseño de BitStack y CRTStack, optimizados para enteros pequeños, que reducen drásticamente la sobrecarga de comunicación y computación en el cliente.
3. Operación de Redondeo Homomórfica: Implementación de funciones de redondeo (Floor, Ceil, Round) precisas para enteros pequeños utilizando la aproximación mod propuesta.
4. Conversión de Secretos a Cifrado: Realización de la primera transformación completa y basada únicamente en operaciones CKKS para convertir comparticiones secretas aditivas (secret shares) en cifrados CKKS, sin modificar el esquema de compartición subyacente.

4. Resultados Experimentales

Los experimentos se realizaron utilizando la librería OpenFHE en un entorno de servidor estándar.

• Precisión de Aproximación:
  • El método propuesto logra errores de aproximación de hasta $10^{-8}$ (y hasta $10^{-10}$ para funciones de redondeo) con grados polinómicos moderados (ej. grado 45-50).
  • Supera significativamente a los métodos baselines (Lee et al. [LLL+21] y OpenFHE nativo), que muestran errores altos ($>1$) en gran parte del dominio.
• Rendimiento de Empaquetado (BitStack vs. CRTStack):
  • BitStack: Más rápido en desempaquetado serial (ej. ~12s) pero con mayor acumulación de error en capas intermedias.
  • CRTStack: Permite desempaquetado paralelo (más rápido en tiempo total si se paraleliza) y mantiene una precisión uniforme en todas las capas (error ~$10^{-7}$), aunque requiere polinomios de mayor grado.
• Comparación con Transcipher (Rubato):
  • La propuesta reduce el tiempo de cifrado en el cliente y el tiempo total de latencia en escenarios de ancho de banda moderado (400-600 KB/s).
  • Es aproximadamente 1.6 veces más rápida en el proceso de desempaquetado que Rubato.
  • Logra un error de reconstrucción un orden de magnitud menor que las soluciones de Transcipher existentes.
• Conversión de Secretos: La conversión de comparticiones secretas a cifrados CKKS se realiza con errores en el orden de $10^{-8}$, validando la viabilidad de este nuevo paradigma de interoperabilidad.

5. Significado e Impacto

Este trabajo es fundamental para la viabilidad práctica de la computación homomórfica en escenarios del mundo real:

• Eficiencia en Dispositivos Limitados: Al reducir drásticamente el tamaño de los datos cifrados que deben subir los usuarios (hasta dos órdenes de magnitud en algunos casos), hace que HE sea viable para dispositivos IoT, móviles y sistemas de salud.
• Ampliación de Funcionalidades: Permite realizar operaciones no lineales críticas (como módulo y redondeo) dentro de CKKS, expandiendo el conjunto de algoritmos que pueden ejecutarse sobre datos cifrados.
• Interoperabilidad: La capacidad de convertir comparticiones secretas a cifrados CKKS sin claves adicionales o preprocesamiento offline complejo cierra una brecha importante entre la Computación Multi-Partícipe Segura (MPC) y el Cifrado Homomórfico, facilitando arquitecturas híbridas más eficientes.
• Limitación: El método está restringido a enteros pequeños (rango de entrada limitado, típicamente decenas o cientos), lo que lo hace ideal para datos genómicos, imágenes o contadores, pero no para cifrados de bootstrapping con rangos masivos.

En resumen, el artículo presenta un avance técnico sólido que combina teoría de aproximación polinómica con ingeniería de sistemas criptográficos para resolver cuellos de botella de comunicación y funcionalidad en el cifrado homomórfico.