Secure Two-Party Matrix Multiplication from Lattices and Its Application to Encrypted Control

1. Planteamiento del Problema

El control encriptado es un paradigma que busca garantizar la seguridad y privacidad de los sistemas ciberfísicos ejecutando algoritmos de control directamente sobre datos cifrados. Esto permite a un cliente delegar la computación del controlador a recursos no confiables sin revelar mediciones de sensores, acciones de control o parámetros del controlador.

Sin embargo, existen limitaciones significativas en las arquitecturas actuales:

• Configuración de un solo servidor (Homomórfica): Aunque teóricamente sólida, la sobrecarga computacional en el cliente (cifrado/descifrado) suele ser mayor que la del cálculo original, incluso para controladores simples de retroalimentación de estado.
• Arquitecturas de múltiples partes (Secret Sharing):
  • Los esquemas existentes a menudo requieren múltiples rondas de comunicación interactiva.
  • Algunos métodos requieren al menos tres partes no colusorias (aumentando costos y complejidad).
  • El uso de "triples de Beaver" o la generación de datos de ayuda por parte del cliente incrementa la complejidad computacional y de comunicación del cliente.

El desafío principal: Lograr un protocolo de computación segura de dos partes que sea de una sola ronda de comunicación, mantenga una baja complejidad computacional en el cliente (inferior a la del controlador original) y preserve la privacidad de las entradas, salidas y parámetros.

2. Metodología Propuesta

El autor propone un protocolo de computación segura de dos partes para la multiplicación matricial aproximada de números de punto fijo, basado en problemas de criptografía de retículos.

Fundamentos Criptográficos

El protocolo integra dos problemas estándar de retículos:

1. Learning With Errors (LWE): Utilizado para la encriptación. Permite ocultar vectores de datos en cifrados que parecen distribuciones uniformes.
2. Short Integer Solution (SIS): Utilizado para esquemas de compromiso (commitment). Garantiza que un mensaje no pueda ser alterado una vez comprometido y oculta el valor original hasta su apertura.

Estructura del Protocolo (Mult)

El protocolo se divide en tres fases:

1. Setup (Configuración): El cliente genera matrices públicas aleatorias ($A, B$) y las publica como una cadena de referencia común (CRS).
2. Offline (Fase fuera de línea):
   • El cliente toma la matriz de entrada $X$ (por ejemplo, la ganancia de retroalimentación $K$).
   • Codifica $X$ a enteros ($\bar{X} = 2^\ell X$).
   • Genera cifrados LWE ($C, C'$) y comparte la matriz de clave secreta $S$ mediante un esquema de secreto compartido aditivo ($\llbracket S \rrbracket$).
   • Envía los cifrados y las partes de $S$ a los dos servidores no confiables ($P_0, P_1$).
3. Online (Fase en línea):
   • El cliente codifica la segunda entrada $Y$ (por ejemplo, el estado del sistema $x$) y genera sus partes compartidas ($\llbracket \bar{Y} \rrbracket$).
   • Los servidores $P_0$ y $P_1$ generan localmente partes de un vector aleatorio corto $R$ ($\llbracket R \rrbracket$).
   • Los servidores calculan localmente un compromiso SIS ($H$) basado en las partes de $Y$ y $R$.
   • Cálculo de una sola ronda: Los servidores calculan localmente las partes del resultado $\llbracket \bar{Z} \rrbracket$ utilizando la siguiente relación lineal sobre los compartidos:
     $$\llbracket \bar{Z} \rrbracket = C^\top \llbracket \bar{Y} \rrbracket + (C')^\top \llbracket R \rrbracket - \llbracket S \rrbracket^\top H$$
     Esta operación elimina los términos de ruido y secretos, dejando una aproximación del producto matricial.
   • Los servidores envían $\llbracket \bar{Z} \rrbracket$ al cliente, quien reconstruye el resultado $Z = 2^{-2\ell} \text{Reconst}(\llbracket \bar{Z} \rrbracket)$.

Análisis de Precisión y Parámetros

El artículo deriva condiciones matemáticas para los parámetros de punto fijo ($k$ bits enteros, $\ell$ bits fraccionarios) y los parámetros de retículo ($n, q, \sigma, t$):

• Se establecen límites superiores para evitar el desbordamiento modular (wrap-around).
• Se establecen límites inferiores para el número de bits fraccionarios ($\ell$) para garantizar que el error de aproximación (ruido de LWE y SIS) permanezca por debajo de un umbral $\epsilon$ deseado.

3. Contribuciones Clave

1. Protocolo de Una Ronda: Propone el primer protocolo de dos partes para multiplicación matricial aproximada que requiere solo una ronda de comunicación entre los servidores y el cliente.
2. Baja Complejidad en el Cliente: En la fase en línea, el cliente solo realiza operaciones de generación y reconstrucción de compartidos ($O(n_x + n_u)$), lo cual es significativamente menor que la complejidad de la multiplicación matricial directa ($O(n_x n_u)$).
3. Privacidad Completa: Garantiza la confidencialidad de las entradas ($X, Y$), la salida ($Z$) y los parámetros del controlador bajo las suposiciones de LWE y SIS.
4. Análisis Teórico de Errores: Proporciona condiciones suficientes para que el error de aproximación y cuantificación sea controlable, asegurando la viabilidad para aplicaciones de control.

4. Resultados y Evaluación

El protocolo se aplicó a la implementación segura de una ley de control lineal ($u = Kx + v$).

• Escenario de Prueba: Se utilizó un sistema lineal invariante en el tiempo con una ganancia de retroalimentación específica.
• Parámetros: Se configuraron parámetros de LWE para 128 bits de seguridad ($n=212, q=2^{108}$) y se seleccionaron longitudes de bits $k=53$ y $\ell=44$.
• Rendimiento:
  • Los resultados numéricos mostraron que el error de control $\|u(\tau) - \hat{u}(\tau)\|_{max}$ se mantuvo por debajo del límite teórico $\epsilon = 2^{-10}$.
  • El comportamiento del sistema encriptado fue indistinguible del sistema original, preservando el rendimiento de control a pesar de los errores de cuantificación y aproximación.
  • Se confirmó que el cliente logra una complejidad computacional en línea reducida en comparación con el cálculo original del controlador.

5. Significado e Impacto

Este trabajo representa un avance significativo en el campo del control encriptado:

• Viabilidad Práctica: Demuestra que es posible delegar el control de sistemas físicos a servidores no confiables sin incurrir en una sobrecarga computacional prohibitiva para el cliente.
• Eficiencia: Al eliminar la necesidad de múltiples rondas de comunicación y reducir la carga del cliente, el protocolo hace que la implementación de controladores encriptados en tiempo real sea más factible.
• Seguridad: Ofrece una solución robusta basada en retículos (resistente a ataques cuánticos) que protege tanto las señales del sistema como los parámetros del controlador (la "propiedad intelectual" del controlador).
• Futuro: Abre la puerta para extender este marco a controladores dinámicos y redes neuronales, optimizando aún más los costos computacionales.

En resumen, el artículo presenta una solución elegante que combina criptografía de retículos y esquemas de secreto compartido para resolver el dilema entre seguridad, privacidad y eficiencia en el control de sistemas ciberfísicos.