PAC to the Future: Zero-Knowledge Proofs of PAC Private Systems

1. El Problema

El aumento en la dependencia de datos sensibles del usuario para entrenar modelos de aprendizaje automático a gran escala (como los modelos de lenguaje grandes) ha generado preocupaciones sobre la privacidad y una falta de confianza en los sistemas propietarios.

• Limitaciones de las técnicas actuales: Las técnicas tradicionales de privacidad, como la Privacidad Diferencial (DP), a menudo sacrifican significativamente la utilidad de los datos para garantizar fuertes garantías de privacidad, especialmente en conjuntos de datos pequeños o grandes.
• El desafío de la verificación: Aunque existen métodos para computar sobre datos encriptados o enmascarados, los usuarios no tienen forma de verificar que las operaciones se estén realizando correctamente o que el ruido de privacidad se haya aplicado adecuadamente sin revelar la información subyacente.
• El vacío en la confianza: En entornos de computación sin confianza (como la nube), los usuarios deben confiar ciegamente en que el proveedor de servicios aplica correctamente los mecanismos de privacidad.

2. Metodología

Los autores proponen un marco novedoso que combina la Privacidad Probablemente Aproximadamente Correcta (PAC) con Pruebas de Conocimiento Cero (ZKPs), específicamente utilizando zk-STARKs (Zero-Knowledge Scalable, Transparent Arguments of Knowledge).

Conceptos Clave:

• Privacidad PAC: A diferencia de la DP, PAC Privacy ofrece garantías de privacidad rigurosas para algoritmos de "caja negra" determinando automáticamente la cantidad mínima de ruido necesaria para proteger los datos, manteniendo un mejor equilibrio entre privacidad y utilidad.
• ZKPs y zk-STARKs: Se utilizan pruebas de conocimiento cero no interactivas para permitir que un proveedor (Prover) demuestre a un cliente (Verifier) que cumplió con el protocolo de privacidad sin revelar los datos privados ni los parámetros del ruido. Se eligen zk-STARKs por su seguridad post-cuántica y por no requerir una configuración confiable (trusted setup).

Flujo del Sistema:

El sistema se divide en dos funciones deterministas principales para adaptarse a las restricciones de los circuitos aritméticos de ZKP:

1. Generación de Ruido ($f_h$): El servidor calcula una matriz de covarianza $\Sigma$ basada en los datos de entrada para determinar la distribución de ruido gaussiano necesaria. En lugar de revelar $\Sigma$, el servidor calcula y prueba en ZK el hash $h(\Sigma)$.
2. Aplicación de Privacidad ($f_{PAC}$): El servidor toma un punto de datos $x$ y una semilla aleatoria $s$ (proporcionada por el verificador) para generar determinísticamente el ruido $B$ basado en $\Sigma$. Luego computa $M(x) + B$ (donde $M$ es el mecanismo, ej. entrenamiento de un modelo).
3. Verificación: El verificador recibe el resultado $M(x) + B$ y una prueba ZK que atestigua que:
   • Se utilizó la matriz de covarianza correcta (verificada mediante el hash).
   • El ruido se aplicó correctamente según la distribución PAC.
   • No se filtró información sobre los datos crudos ni los parámetros del ruido.

Implementación Técnica:

• Plataforma: Se utiliza RISC-Zero, un framework zk-STARK que ejecuta programas en una máquina virtual (zkVM).
• Restricciones: Dado que los programas en RISC-Zero deben ser deterministas y no pueden depender de la entrada para el número de iteraciones (bucles), los algoritmos de aprendizaje automático (como K-means) se adaptan:
  • Se fijan el número de iteraciones.
  • Se utilizan estructuras de datos de tamaño fijo (ej. listas con booleanos para indicar validez) para evitar dependencias de la entrada en la estructura del circuito.
  • La aleatoriedad es gestionada por el verificador (semillas) para mantener la determinismo en el generador de pruebas.

3. Contribuciones Clave

1. Marco End-to-End: Presentación del primer marco que integra PAC Privacy con pruebas ZK no interactivas y seguras post-cuánticas para computación externalizada.
2. Verificabilidad de Ruido: Capacidad de generar pruebas que atestigüen la correcta aplicación del ruido de privacidad PAC sin revelar los parámetros del ruido ni los datos sensibles.
3. Evaluación Extensiva: Implementación y prueba del sistema en tres escenarios distintos:
   • K-means: Algoritmo de clustering no supervisado.
   • SVM (Máquinas de Vectores de Soporte): Algoritmo de clasificación supervisada.
   • Estadísticas de Bases de Datos: Consultas agregadas (medias, medianas) sobre filtros de datos privados.
4. Eficiencia: Demostración de que es posible lograr privacidad verificable con una sobrecarga computacional manejable y una utilidad cercana a la de los datos en texto plano.

4. Resultados Experimentales

Los experimentos se realizaron en el framework RISC-Zero variando el tamaño de los conjuntos de datos, la dimensión de los puntos y los parámetros de los algoritmos.

• K-means: Se observó un crecimiento afín perfecto en el número de ciclos de la CPU simulada (RISC cycles) en función del número de muestras ($M$) y el número de clusters ($K$). Esto se debe a la naturaleza determinista y estructurada del algoritmo adaptado.
• SVM: Mostró un comportamiento generalmente afín, aunque con ligeras fluctuaciones debido a operaciones intensivas en memoria y el uso de caché en el zkVM, lo que introduce variabilidad en los conteos de ciclos.
• Estadísticas de Bases de Datos: Confirmó el comportamiento afín esperado al ejecutar consultas sobre diferentes tamaños de bases de datos.
• Utilidad vs. Privacidad: El sistema logra mantener una utilidad alta (resultados cercanos a los del mecanismo original sin ruido) mientras garantiza las propiedades de privacidad PAC, con una sobrecarga de generación de pruebas que es factible para aplicaciones de pequeña a mediana escala.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Confianza en la Nube: Resuelve el problema de la "caja negra" en la computación en la nube, permitiendo a los usuarios verificar que sus datos se procesan con las garantías de privacidad prometidas sin tener que confiar ciegamente en el proveedor.
• Superioridad sobre la DP: Al utilizar PAC Privacy en lugar de Privacidad Diferencial, el sistema evita la degradación severa de la utilidad que suele ocurrir con la DP, ofreciendo un enfoque más práctico para proteger datos sensibles en modelos de aprendizaje automático.
• Seguridad Futura: La elección de zk-STARKs asegura que el sistema sea resistente a ataques de computación cuántica, a diferencia de muchas implementaciones actuales basadas en zk-SNARKs que dependen de curvas elípticas.
• Nueva Paradigma: Establece un precedente para la creación de sistemas de privacidad verificables donde la integridad computacional y la protección de datos se garantizan matemáticamente mediante pruebas criptográficas.

En resumen, el artículo demuestra la viabilidad práctica de combinar la flexibilidad de la Privacidad PAC con la verifiabilidad de las pruebas de conocimiento cero, ofreciendo una solución robusta para la privacidad en la era de la computación externalizada y el aprendizaje automático.