Resumen Técnico: HE-DAP

Planteamiento del Problema

El cifrado homomórfico (HE) permite el análisis de preservación de la privacidad sobre datos cifrados, pero sufre de una alta sobrecarga computacional. Un cuello de botella crítico en las cargas de trabajo estadísticas y de aprendizaje automático es el cálculo de la raíz cuadrada inversa ($1/\sqrt{a}$), una operación fundamental requerida para funciones tales como la normalización Z-score, la asimetría (skewness), la curtosis y el coeficiente de correlación de Pearson.

Los métodos actuales de vanguardia, como PP-STAT [13] y HEaaN-STAT [24], dependen de configuraciones de parámetros fijos para el cálculo de la raíz cuadrada inversa. Estas configuraciones típicamente involucran un grado específico para la aproximación del polinomio de Chebyshev (utilizado para inicializar el método de Newton) y un número fijo de iteraciones de Newton-Raphson. Los autores identifican un fallo fundamental en este enfoque estático: los costos computacionales relativos de las dos operaciones principales de HE —la evaluación del polinomio de Chebyshev y el bootstrapping (gestión de ruido)— varían drásticamente (hasta 6$\times$) entre diferentes librerías de HE (por ejemplo, Lattigo frente a HEaaN) y entornos de hardware (CPU frente a GPU).

Consecuentemente, una configuración optimizada para un entorno (por ejemplo, Lattigo en CPU, donde el bootstrapping es lento y se prefieren polinomios de grado alto) resulta subóptima o ineficiente en otro (por ejemplo, HEaaN-GPU, donde el bootstrapping es rápido y la evaluación de polinomios es el cuello de botella). Esta dependencia ambiental hace que los marcos de trabajo existentes no sean generalizables y sean ineficientes cuando se despliegan en sistemas heterogéneos.

Metodología: HE-DAP

Para abordar esto, los autores proponen HE-DAP (Optimización de Parámetros Adaptativa Dinámica basada en Cifrado Homomórfico), un marco de trabajo multiplataforma que determina automáticamente los parámetros óptimos para el cálculo de la raíz cuadrada inversa basándose en las características del entorno de ejecución específico.

Mecanismo Central

HE-DAP opera durante una etapa de aprovisionamiento (previo al procesamiento de datos real) para perfilar las características de rendimiento del servidor de destino. Selecciona dinámicamente tres parámetros clave para el algoritmo CryptoInvSqrt:

1. $d$: El grado de la aproximación del polinomio de Chebyshev.
2. $c$: Un indicador binario para el Pre-Bootstrapping (aplicar bootstrapping al texto cifrado de entrada antes del cálculo de la raíz cuadrada inversa).
3. $i$: El número de iteraciones de Newton-Raphson.

Flujo de Trabajo Algorítmico

1. Perfilado: HE-DAP evalúa todos los niveles posibles de texto cifrado de entrada ($l$) que van desde $l_{BTS} + 1$ hasta $l_{max}$.
2. Exploración del Espacio de Búsqueda: Para cada nivel, prueba combinaciones de grados de polinomio ($d$), indicadores de Pre-BTS ($c$) y conteos de iteraciones ($i$).
   • Si el nivel de entrada es insuficiente para la profundidad del polinomio, considera el Pre-BTS ($c=1$).
   • Si el nivel es suficiente, procede sin Pre-BTS ($c=0$).
3. Criterio de Optimización: Para cada combinación, el sistema mide el Error Relativo Medio (MRE) y el tiempo de ejecución. Identifica el conteo de iteraciones ($i$) óptimo que satisface un umbral de MRE objetivo.
4. Selección de Parámetros: El marco registra dos tuplas óptimas para cada nivel:
   • Orientada a la Precisión: Minimiza el tiempo de ejecución sujeto a una restricción estricta de MRE.
   • Orientada a la Velocidad: Minimiza el tiempo de ejecución independientemente del MRE (útil para aplicaciones que toleran un mayor error).
5. Aplicación en Tiempo de Ejecución: Durante el análisis estadístico real, el servidor utiliza los parámetros óptimos precalculados correspondientes al nivel actual del texto cifrado, eliminando la necesidad de ajuste manual o valores por defecto subóptimos.

Contribuciones Clave

1. Marco de Trabajo HE-DAP: La introducción de un nuevo optimizador adaptativo que configura automáticamente la operación de raíz cuadrada inversa para diversas librerías de HE y hardware, alejándose de los parámetros estáticos dependientes del entorno.
2. Ganancias de Rendimiento: Demostración de que HE-DAP acelera significativamente el cálculo central de la raíz cuadrada inversa. En el entorno HEaaN-GPU, logra una aceleración de hasta 2.35$\times$ sobre la configuración fija en PP-STAT manteniendo una alta precisión numérica (MRE $\le 3.1 \times 10^{-8}$).
3. Evaluación Exhaustiva: Una evaluación rigurosa a través de tres entornos distintos (Lattigo, HEaaN-CPU y HEaaN-GPU) y cuatro medidas estadísticas principales (Z-score, asimetría, curtosis, coeficiente de correlación de Pearson). Los resultados confirman que HE-DAP descubre consistentemente configuraciones óptimas tanto para entornos CPU como GPU.
4. Código Abierto: El lanzamiento de la implementación completa de HE-DAP para asegurar la reproducibilidad.

Resultados Experimentales

Los autores evaluaron HE-DAP contra PP-STAT (basado en Lattigo) y HEaaN-STAT (basado en GPU) utilizando el esquema CKKS.

• Rendimiento de la Raíz Cuadrada Inversa:

  • HEaaN-GPU: HE-DAP aceleró PP-STAT en 2.35$\times$ en el nivel 12 y 1.79$\times$ en el nivel 7 (orientado a la precisión) comparado con la configuración fija de PP-STAT. Comparado con HEaaN-STAT, logró un tiempo de ejecución hasta 2.15$\times$ más rápido con un MRE menor.
  • HEaaN-CPU: Logró una aceleración de 2.18$\times$ sobre PP-STAT en el nivel 12.
  • Lattigo: Logró una aceleración de 1.96$\times$ sobre PP-STAT en el nivel 11, reduciendo simultáneamente el MRE en 79$\times$ en comparación con la línea base de PP-STAT.

• Análisis Estadístico de Extremo a Extremo:

  • La aplicación de HE-DAP a medidas estadísticas (ZNorm, Skew, Kurt, PCC) en conjuntos de datos del mundo real (UCI Adult y Medical Cost Insurance) resultó en una aceleración constante.
  • En el conjunto de datos Adult, HE-DAP redujo el tiempo de ejecución entre un 42% y un 44% en comparación con PP-STAT manteniendo un MRE similar.
  • En el conjunto de datos Insurance, las reducciones de tiempo alcanzaron el 44.6%.

• Análisis de Compromiso (Trade-off): El modo "Orientado a la Velocidad" permitió una aceleración aún mayor (hasta 6.34$\times$ sobre HEaaN-STAT en GPU) a costa de un mayor MRE, demostrando la flexibilidad del marco para diferentes requisitos de aplicación.

Significancia y Reivindicaciones

El artículo afirma que HE-DAP demuestra que la optimización de parámetros basada en principios puede hacer que el análisis estadístico con preservación de la privacidad sea práctico a escala. Al automatizar la adaptación a entornos de ejecución heterogéneos, HE-DAP resuelve la ineficiencia causada por los parámetros fijos en los marcos de trabajo existentes.

Los autores enfatizan que su enfoque es consciente del entorno, reconociendo que el equilibrio óptimo entre la evaluación de polinomios y el bootstrapping no es universal, sino que depende de la librería de HE y el hardware específicos. Al navegar dinámicamente este compromiso, HE-DAP asegura que el bloque de construcción fundamental del análisis estadístico (raíz cuadrada inversa) se ejecute con la máxima eficiencia, mejorando así el rendimiento de flujos de trabajo estadísticos complejos de extremo a extremo sin comprometer las garantías de privacidad del Cifrado Homomórfico.

El artículo concluye que, si bien la fase de aprovisionamiento (búsqueda de parámetros) incurre en un costo de tiempo (particularmente en librerías de CPU como Lattigo), este es un costo de configuración único que genera beneficios de rendimiento significativos y sostenidos durante la fase de procesamiento de datos real. Se sugiere como trabajo futuro reducir este tiempo de exploración aprovechando indicadores de rendimiento medibles en lugar de una evaluación exhaustiva.