Variational Encrypted Model Predictive Control

Este artículo presenta un protocolo de control predictivo de modelo encriptado variacional (VEMPC) que ejecuta operaciones en línea exclusivamente mediante polinomios encriptados, reformulando el problema como un estimador basado en muestreo para reducir la carga computacional sin necesidad de descifrado intermedio, garantizando escalabilidad y analizando su impacto en la optimalidad.

Lo esencial

Imagina que tienes un robot muy inteligente (un dron, un brazo robótico o incluso un coche autónomo) que necesita tomar decisiones en milisegundos para no chocar. Para hacerlo, el robot usa una "mente maestra" llamada Control Predictivo (MPC). Esta mente calcula el mejor camino posible mirando hacia el futuro, pero tiene un problema: necesita mucha potencia de cálculo.

Para no agotar la batería del robot, le envía los datos a un servidor en la nube (como un superordenador gigante) para que haga los cálculos. Pero aquí surge el dilema: si envías los datos tal cual, el servidor podría espiar tu ubicación, tu velocidad o tus secretos industriales.

Aquí es donde entra la Encriptación. Es como poner los datos en una caja de cristal indestructible. El servidor puede hacer cálculos sobre la caja sin abrirla, pero... ¡hay un truco! Los servidores actuales solo saben sumar y multiplicar cosas simples. No saben hacer cosas complejas como "comparar" (¿es A mayor que B?) o "proyectar" (¿dónde cae este punto si choca contra una pared?), que son esenciales para que el robot no se estrelle.

La Solución: El "MPC Variacional Encriptado" (VEMPC)

Los autores de este paper han creado una nueva forma de pensar el problema, usando una analogía muy divertida: El "Círculo de Probabilidad".

1. El Problema de la "Caja de Cristal"

Normalmente, para encontrar la mejor ruta, el servidor tendría que probar millones de caminos, descartar los que chocan (comparación) y ajustar los que quedan (proyección). En una caja encriptada, hacer eso es como intentar adivinar qué hay dentro de una caja cerrada solo dándole vueltas y golpeándola: es lento y costoso.

2. La Magia del "Sesgo" (Tilting)

En lugar de intentar calcular la ruta perfecta paso a paso, los autores proponen un truco genial: cambiar la suerte.

Imagina que quieres encontrar el tesoro en una isla llena de trampas.

• El método viejo: Envías a 100 exploradores al azar. Si caen en una trampa, les gritas "¡No valen!" (comparación) y les mandas a otra parte. Esto requiere mucha comunicación y es lento.
• El método nuevo (VEMPC): En lugar de enviar exploradores al azar, les das un mapa que ya está sesgado hacia el tesoro. Les dices: "No vayan al azar, vayan en una dirección que ya sabe que es buena".

En términos matemáticos, usan una técnica llamada "Exponential Tilting". Básicamente, cambian la distribución de probabilidad de las muestras (los exploradores) para que, naturalmente, tiendan a caer en las zonas seguras y eficientes. Así, el servidor encriptado no necesita hacer cálculos complejos de "chocar o no chocar" ni multiplicaciones cuadráticas costosas. Solo necesita hacer una operación simple: sumar y multiplicar polinomios (que la caja de cristal sí sabe hacer).

3. El "Polinomio Suave"

A veces, un explorador sigue cayendo en una trampa. En lugar de decir "¡Error! ¡Detenerse!" (lo cual requiere comparar números, algo prohibido en la caja encriptada), usan un "suavizador". Imagina que en lugar de una pared dura, hay una colina suave. Si el explorador se acerca a la pared, la colina lo empuja suavemente hacia atrás.

Matemáticamente, reemplazan la "pared dura" (comparación) por un polinomio (una curva suave) que se puede calcular fácilmente dentro de la caja encriptada. Si la colina es muy suave, el explorador casi nunca llega a la pared.

4. La Velocidad: Dos Niveles de Paralelismo

Para que todo esto sea rápido (necesario para un robot en tiempo real), el sistema usa dos tipos de "fuerza bruta" al mismo tiempo:

1. Nivel de Texto Plano: Envían muchos exploradores (muestras) a la vez.
2. Nivel de Caja Encriptada: Usan una técnica llamada SIMD (como si una sola caja encriptada pudiera contener 100 exploradores apilados y procesarlos todos de una sola vez).

El Resultado Final

Gracias a este método, el servidor en la nube puede calcular la mejor ruta para el robot en menos de 30 milisegundos (¡más rápido que un parpadeo!), todo mientras los datos del robot viajan y se procesan completamente encriptados.

• Sin encriptación: El robot es rápido, pero el servidor puede espiarlo.
• Encriptación vieja: El servidor no puede espiar, pero el robot es tan lento que choca.
• Este nuevo método (VEMPC): El robot es rápido, seguro y el servidor no sabe absolutamente nada de lo que está pasando, porque solo ve cálculos matemáticos en una caja mágica.

En resumen: Han convertido un problema de "buscar la aguja en el pajar" (que requiere mirar todo el pajar) en un problema de "lanzar el pajar hacia la aguja" (sesgando la probabilidad), permitiendo que la magia de la encriptación funcione sin ralentizar el sistema.

Resumen técnico

Resumen Técnico: Control Predictivo de Modelo Encriptado Variacional (VEMPC)

1. Planteamiento del Problema

El Control Predictivo de Modelo (MPC) es una técnica estándar en la industria por su capacidad para manejar restricciones explícitamente. Sin embargo, su implementación en tiempo real requiere resolver un problema de optimización (generalmente un programa cuadrático) en cada paso de tiempo.

• Desafío de Privacidad: Para aliviar la carga computacional, es atractivo delegar este cálculo a servidores en la nube. No obstante, enviar estados del sistema, parámetros del modelo o datos de trayectoria a un tercero plantea riesgos graves de privacidad (eavesdropping o inferencia por parte de servidores semi-honestos).
• Limitaciones de la Criptografía Homomórfica (HE): La HE permite calcular sobre datos encriptados, pero tradicionalmente solo soporta operaciones de suma y multiplicación. Los algoritmos de MPC estándar requieren operaciones no polinómicas (como proyecciones, comparaciones o ramas lógicas) para manejar restricciones, lo que obliga a:
  • Descifrar datos intermedios (rompiendo la privacidad).
  • Realizar múltiples rondas de comunicación (lento).
  • Usar métodos de aproximación que degradan el rendimiento del control.

El objetivo del artículo es desarrollar un protocolo de MPC que opere únicamente con operaciones polinómicas encriptadas, eliminando la necesidad de descifrado intermedio y rondas de comunicación adicionales, manteniendo la privacidad de los datos del cliente.

2. Metodología Propuesta: VEMPC

Los autores proponen un enfoque variacional que transforma el problema de optimización con restricciones en un problema de estimación basado en muestreo.

A. Reformulación Variacional
En lugar de resolver el programa cuadrático (QP) directamente mediante métodos iterativos, el problema se reformula como la minimización de una divergencia de Kullback-Leibler (KL) sobre un espacio de distribuciones de probabilidad.

• Se define un estimador de la solución óptima como la esperanza de una distribución "tiltada" (sesgada) que incorpora la función de costo.
• La solución se aproxima mediante un promedio ponderado de muestras (Monte Carlo).

B. Sesgo Exponencial (Exponential Tilting)
Para evitar el costoso cálculo encriptado del término cuadrático de la función de costo ($U^T H U$), los autores aplican una transformación de cambio de medida:

• Se define una distribución de referencia gaussiana $\kappa_0$.
• Mediante sesgo exponencial, se demuestra que la distribución resultante que incluye el término cuadrático es también una distribución gaussiana cerrada ($\tilde{\kappa}$).
• Resultado clave: El término cuadrático costoso se "absorbe" en la definición de la nueva distribución de muestreo. Esto elimina la necesidad de multiplicaciones de matriz-vector encriptadas durante la fase en línea.

C. Sustitución Polinómica de Restricciones
El desafío restante es manejar las restricciones (factibilidad), que originalmente requieren operaciones de comparación (indica si una restricción se viola o no), las cuales no son polinómicas.

• Se introduce una puntuación de violación agregada basada en la función parte positiva $[ \cdot ]_+$.
• Esta función no polinómica se aproxima mediante polinomios de Chebyshev de bajo grado.
• Se añade un umbral de corrección para asegurar que las muestras factibles no sean penalizadas erróneamente por errores de aproximación.
• El peso de factibilidad se convierte en una función exponencial de este polinomio, permitiendo su evaluación puramente con operaciones de HE (suma y multiplicación).

D. Protocolo Cliente-Nube
El protocolo se divide en dos fases:

1. Preprocesamiento Offline: El cliente encripta y envía matrices derivadas del modelo (independientes del estado actual) a la nube. La nube precalcula muestras de ruido encriptadas.
2. Ejecución Online:
   • El cliente envía el estado actual encriptado.
   • La nube genera trayectorias de control encriptadas y evalúa las puntuaciones de violación de restricciones usando los polinomios de Chebyshev.
   • La nube devuelve las muestras y puntuaciones encriptadas.
   • El cliente descifra, calcula los pesos finales y promedia las trayectorias para obtener la acción de control.

E. Paralelismo
El sistema aprovecha dos niveles de paralelismo para la eficiencia:

• Nivel de Texto Plano: Muestreo independiente de múltiples trayectorias.
• Nivel de Texto Cifrado: Uso de la técnica SIMD (Single Instruction, Multiple Data) de la criptografía CKKS para procesar múltiples muestras dentro de un solo texto cifrado.

3. Contribuciones Clave

1. VEMPC: Primer protocolo que integra un enfoque variacional con MPC encriptado, absorbiendo el costo cuadrático en una distribución gaussiana cerrada.
2. Eficiencia en Encriptación: Demuestran que tanto la trayectoria de control como los residuos de las restricciones son funciones afines del ruido de muestreo, permitiendo un protocolo compatible con HE basado solo en sumas y evaluaciones polinómicas de bajo grado.
3. Arquitectura Escalable: Implementación de dos niveles de paralelismo que permiten tiempos de ejecución en línea de decenas de milisegundos.
4. Código Abierto: Provisión de implementaciones en Python y Go utilizando bibliotecas de HE populares (OpenFHE y Lattigo).

4. Resultados Experimentales

Los autores probaron el protocolo en un sistema de péndulo invertido linealizado.

• Configuración: Horizonte de predicción $N=10$, 60 restricciones, y parámetros de seguridad de 128 bits (CKKS con dimensión de anillo $2^{13}$).
• Rendimiento:
  • El tiempo de cálculo en línea promedio fue de 28.66 ms (con 4 trabajadores paralelos), lo cual es compatible con el tiempo de muestreo de 50 ms del sistema.
  • El control encriptado (VEMPC) mostró un rendimiento casi idéntico al MPC no encriptado, estabilizando el péndulo y respetando las restricciones (ver Fig. 1 del artículo).
  • El análisis de sensibilidad mostró que el tiempo de cálculo crece linealmente con el grado del polinomio y el tamaño del anillo, pero se mantiene constante al aumentar el número de muestras ($K$) gracias al paralelismo SIMD.

5. Significado e Impacto

Este trabajo es significativo porque cierra la brecha entre la teoría de la criptografía homomórfica y la implementación práctica del control en tiempo real.

• Superación de Limitaciones: Resuelve el problema fundamental de que los algoritmos de optimización tradicionales (basados en ramas y proyecciones) son incompatibles con la aritmética encriptada.
• Privacidad sin Sacrificio de Rendimiento: Permite delegar el control a la nube sin revelar estados ni modelos, sin necesidad de descifrar datos intermedios y con un retraso computacional aceptable para aplicaciones de tiempo real.
• Viabilidad Práctica: Al reducir la operación en línea a evaluaciones polinómicas y aprovechar el paralelismo, demuestra que el MPC encriptado es viable para sistemas físicos reales, abriendo la puerta a aplicaciones en IoT industrial, vehículos autónomos y redes de energía donde la privacidad de los datos es crítica.