A Privacy-Preserving Approach to Conformance Checking

Aquí se presenta un resumen técnico detallado del artículo "Un enfoque de preservación de la privacidad para la verificación de conformidad".

1. Planteamiento del Problema

La verificación de conformidad es una operación central en la minería de procesos que compara un modelo de proceso (comportamiento esperado) contra un registro de eventos (comportamiento observado) para identificar discrepancias. Tradicionalmente, tanto el modelo como el registro son accesibles para el analista. Sin embargo, en contextos sensibles (por ejemplo, fabricación a medida o líneas de producción propietarias), el propietario del modelo de proceso debe proteger su propiedad intelectual, mientras que el cliente (propietario del registro) debe proteger sus datos operativos.

El problema central abordado es: ¿Cómo realizar la verificación de conformidad entre un modelo de proceso y un registro de eventos sin revelar el modelo al propietario del registro, ni el registro al propietario del modelo?

2. Metodología

Los autores proponen una técnica de Verificación de Conformidad Segura basada en una arquitectura Cliente-Servidor, que utiliza Cifrado Homomórfico Total (FHE) y algoritmos de procesamiento de cadenas.

A. Conceptos Centrales

• Redes de Petri y Despliegue: El modelo de proceso se representa como una red de Petri. Para convertir esto en un formato adecuado para la búsqueda de cadenas, los autores utilizan el despliegue de prefijo causalmente completo. Esto transforma el comportamiento potencialmente infinito de una red de Petri (debido a los bucles) en una estructura finita y acíclica que contiene todas las posibles "ejecuciones" (ejecuciones completas).
• Representación de Cadena: Las ejecuciones del despliegue se linealizan y concatenan en una sola cadena de texto, separadas por delimitadores especiales.
• Índice FM y Búsqueda hacia Atrás: La cadena concatenada se indexa utilizando el Índice FM (basado en la Transformada de Burrows-Wheeler y la Matriz de Ondas). Esto permite una búsqueda eficiente de subcadenas (encontrar si una traza existe dentro de las ejecuciones del modelo) en tiempo $O(m)$.
• Cifrado Homomórfico (FHE): El sistema utiliza un esquema de cifrado de clave pública (específicamente ElGamal elevado) que permite realizar cálculos (suma y multiplicación) directamente sobre datos cifrados.

B. El Protocolo Seguro

El enfoque mapea el problema de encontrar alineaciones óptimas (minimizando desviaciones) a la búsqueda aproximada de subcadenas.

1. Lado del Servidor (Propietario del Modelo):

   • Toma el modelo de proceso, lo despliega, concatena las ejecuciones y construye el Índice FM (BWT y Matriz de Ondas).
   • Almacena las estructuras de datos del índice (específicamente los vectores 0-RANK y 1-SRANK) en memoria.
   • No ve la traza del cliente.

2. Lado del Cliente (Propietario del Registro):

   • Posee la traza de eventos que debe ser verificada.
   • Cifra los datos de la traza y el estado de búsqueda (índices) antes de enviar consultas al servidor.

3. La Interacción (Búsqueda Segura hacia Atrás):

   • El cliente itera a través de los caracteres de la traza en orden inverso.
   • Para cada carácter, el cliente realiza una Búsqueda hacia Atrás en el Índice FM. Esto implica recorrer la Matriz de Ondas fila por fila (bit a bit) para actualizar el intervalo de búsqueda $[f, g]$.
   • Mecanismo de Privacidad:
     • El cliente envía vectores cifrados que representan los índices de búsqueda actuales.
     • El servidor realiza productos punto homomórficos y sumas para actualizar estos índices basándose en las filas de la Matriz de Ondas.
     • Para evitar que el cliente aprenda los intervalos intermedios (lo cual podría filtrar información sobre el modelo), el servidor añade un desplazamiento aleatorio a los resultados antes de devolverlos.
   • Manejo de Discrepancias (Movimientos del Registro):
     • Si un carácter en la traza no coincide con el modelo (un "movimiento del registro"), el cliente restaura los índices de búsqueda anteriores (almacenados antes de la iteración) e inserta una operación de "salto" en la alineación.
     • Esto se realiza sin que el servidor sepa qué carácter causó la discrepancia, ya que el cliente controla el flujo lógico basándose en resultados descifrados (pero ofuscados).

3. Contribuciones Clave

1. Primera Aplicación de FHE a la Verificación de Conformidad: El artículo afirma ser el primer trabajo que aplica el cifrado homomórfico específicamente al problema de la verificación de conformidad.
2. Alineación Segura mediante Búsqueda de Cadenas: Mapea de manera innovadora el complejo problema de la alineación de trazas a la búsqueda de subcadenas utilizando el Índice FM, permitiendo el uso de algoritmos de cadenas eficientes en un dominio cifrado.
3. Modelo de Privacidad Cliente-Servidor: Establece un protocolo donde el propietario del modelo nunca ve la traza, y el propietario del registro nunca ve el modelo, sin embargo, se puede calcular una puntuación de alineación (y la propia alineación).
4. Manejo de Movimientos del Registro: El algoritmo soporta específicamente los "movimientos del registro" (desviaciones donde el registro tiene un evento que no está en el modelo) permitiendo que el cliente revierta estados de búsqueda de forma segura.

4. Resultados y Evaluación

El método se implementó en C++ utilizando la biblioteca mcl para el cifrado homomórfico y se evaluó en una estación de trabajo de portátil estándar.

• Conjuntos de Datos: Evaluado utilizando un registro de eventos del mundo real y dos registros sintéticos (de tamaño pequeño a mediano con concurrencia, elección y bucles).
• Rendimiento:
  • Precisión: El método calculó con éxito alineaciones para trazas que se ajustan al modelo y aquellas con desviaciones inyectadas.
  • Sobrecarga: El principal cuello de botella es el costo computacional de las operaciones homomórficas.
  • Complejidad: La complejidad teórica es $O(C \cdot |q| \cdot |T|)$, donde $C$ es la constante grande para el cifrado/descifrado, $|q|$ es la longitud de la traza y $|T|$ es el tamaño de las ejecuciones del modelo indexadas.
  • Tiempo de Ejecución: Para un modelo pequeño con 144 ejecuciones y 9 eventos por traza, el tiempo promedio de alineación fue de 1.12 minutos. El tiempo por símbolo fue de aproximadamente 0.11 minutos.
  • Escalabilidad: El tiempo de ejecución mostró una tendencia cuasi-lineal en relación con la longitud de la traza, pero los tiempos absolutos son actualmente demasiado altos para aplicaciones industriales en tiempo real y a gran escala debido a la pesada sobrecarga criptográfica.

5. Significado y Trabajo Futuro

• Significado: Este trabajo cierra la brecha entre la Minería de Procesos y la Minería de Datos con Preservación de la Privacidad. Demuestra que los procesos comerciales sensibles pueden ser auditados sin exponer la lógica propietaria ni los datos operativos, un requisito crítico para industrias como la fabricación a medida y la atención sanitaria.
• Limitaciones:
  • Actualmente solo soporta movimientos del registro (saltar eventos en el registro). Aún no soporta movimientos del modelo (saltar eventos en el modelo), lo cual requeriría una lógica más compleja.
  • Los altos requisitos de memoria y procesamiento lo hacen actualmente poco práctico para modelos muy grandes o sistemas en tiempo real.
• Direcciones Futuras:
  • Extender el enfoque para manejar movimientos del modelo.
  • Mejorar el manejo de bucles (actualmente limitado por la profundidad del despliegue).
  • Optimizar la implementación criptográfica para reducir la brecha computacional entre la ejecución en texto plano y la cifrada.

En conclusión, el artículo presenta un prototipo teóricamente sólido y técnicamente viable para la verificación de conformidad segura, demostrando que la privacidad puede preservarse a costa de recursos computacionales significativos.