Computing Maximal Per-Record Leakage and Leakage-Distortion Functions for Privacy Mechanisms under Entropy-Constrained Adversaries

Resumen Técnico: Computación de Fugas Máximas por Registro y Funciones de Fuga-Distorsión bajo Adversarios con Restricción de Entropía

1. Planteamiento del Problema

El crecimiento exponencial de la recolección de datos ha incrementado la necesidad de protecciones de privacidad robustas que no sacrifiquen la utilidad de los datos. El modelo estándar actual, la Privacidad Diferencial (DP), se basa en una suposición de independencia estadística entre los registros de un conjunto de datos. Sin embargo, esta suposición a menudo es irrealista en escenarios del mundo real, donde un adversario puede tener conocimiento previo correlacionado.

Este trabajo aborda la brecha computacional en el marco de Privacidad de la Información (IP), introducido previamente en [35], el cual reemplaza la suposición de independencia de la DP por un modelo de adversario con conocimiento acotado. En este modelo, el conocimiento del adversario se modela mediante una restricción de entropía: $H(X) \ge b$, donde $X$ es la distribución a priori del adversario sobre el conjunto de datos y $b$ es el mínimo número de bits de incertidumbre que el adversario debe tener.

El artículo se centra en resolver tres problemas de optimización fundamentales que habían quedado como desafíos computacionales abiertos:

1. Fuga Máxima por Registro: Calcular la peor fuga de información sobre cualquier registro individual bajo la restricción de entropía.
2. Función Primal de Fuga-Distorsión: Diseñar mecanismos que minimicen la fuga máxima de información sujeta a una restricción de utilidad (distorsión) $D$.
3. Función Dual de Minimización de Distorsión: Minimizar la distorsión esperada sujeta a un límite estricto de fuga de información $L$.

Estos problemas son análogos a la capacidad de canal y la función tasa-distorsión en la teoría de la información, pero son significativamente más complejos debido a la alta dimensionalidad y la restricción de entropía no lineal.

2. Metodología y Algoritmos

Los autores desarrollan algoritmos de optimización alternada eficientes y con garantías de convergencia, aprovechando la estructura de dualidad convexa-concava de la información mutua.

Propiedades Estructurales Clave:

• Dualidad Convexa-Concava: La información mutua $I(X_i; Y)$ es cóncava en la distribución marginal $p(x_i)$ y convexa en las distribuciones condicionales $p(x_{-i}|x_i)$ y en el mecanismo $q(y|x)$.
• Convexidad de los Conjuntos de Restricción: El conjunto de distribuciones que satisfacen $H(X) \ge b$ es convexo.

Algoritmos Propuestos:

• Algoritmo 1 (Cálculo de Fuga Máxima): Utiliza un esquema de optimización alternada. Alterna entre optimizar la distribución marginal $p(x_i)$ y las distribuciones condicionales $p(x_{-i}|x_i)$.

  • Para la marginal, utiliza una versión modificada del algoritmo Blahut-Arimoto con multiplicadores de Lagrange para manejar la restricción de entropía.
  • Para las condicionales, emplea un método de ascenso de gradiente proyectado por coordenadas, demostrando teóricamente que la solución óptima se encuentra en la frontera del conjunto de entropía.

• Algoritmo 6 (Optimización Primal Fuga-Distorsión): Resuelve el problema de minimizar la fuga máxima sujeta a una distorsión máxima $D$.

  • Alterna entre actualizar la distribución a priori del adversario (usando el Algoritmo 1) y actualizar el mecanismo de privacidad.
  • Para la actualización del mecanismo, utiliza un método de penalización suave adaptativa combinado con descenso de gradiente exponenciado y búsqueda de línea de retroceso (backtracking) para manejar las restricciones de distorsión.

• Algoritmo 9 (Optimización Dual Minimización de Distorsión): Resuelve el problema complementario de minimizar la distorsión sujeta a un límite de fuga $L$.

  • Sigue una estructura similar al Algoritmo 6 pero invierte los objetivos, utilizando una función de penalización suave para la restricción de fuga.

Garantías Teóricas:

• Se demuestra la convergencia local para el problema de fuga máxima y el problema primal.
• Se demuestra la convergencia a un punto estacionario (satisfaciendo las condiciones KKT) para el problema dual.
• Se establece que, en ausencia de la restricción de entropía ($b=0$), el algoritmo converge al óptimo global.

3. Resultados Experimentales

Los autores validaron sus algoritmos mediante experimentos extensos en canales simétricos binarios y consultas de suma modular.

• Comparación con Privacidad Diferencial (DP):

  • Se compararon los mecanismos optimizados bajo el marco IP (basados en canales simétricos binarios) con los mecanismos clásicos de DP (Laplace y Exponencial).
  • Resultado Clave: Bajo la misma restricción de distorsión (utilidad), los mecanismos optimizados en el marco IP requieren un presupuesto de privacidad ($\epsilon$) menor, es decir, generan menos fuga de información que los mecanismos de DP tradicionales.
  • A medida que aumenta la restricción de entropía $b$ (mayor incertidumbre del adversario), la fuga de información disminuye significativamente, demostrando la ventaja de modelar al adversario con conocimiento acotado en lugar de asumir independencia total.

• Curvas de Compensación (Trade-off):

  • Se generaron curvas de Pareto óptimas que muestran la relación entre la fuga máxima por registro y la distorsión esperada.
  • Los algoritmos demostraron capacidad para encontrar mecanismos que satisfacen estrictamente las restricciones de distorsión y fuga, validando la eficacia de la optimización alternada.

4. Contribuciones Clave

1. Algoritmos Eficientes: Desarrollo de algoritmos de optimización alternada novedosos para calcular la fuga máxima y optimizar la compensación privacidad-utilidad bajo restricciones de entropía.
2. Garantías Teóricas: Pruebas rigurosas de convergencia para los algoritmos propuestos, estableciendo que convergen a puntos estacionarios o óptimos locales, llenando el vacío computacional del marco IP.
3. Validación Empírica: Demostración de que los mecanismos diseñados bajo este marco superan a los mecanismos de DP clásicos en términos de compensación privacidad-utilidad, ofreciendo una protección más precisa sin sacrificar la utilidad de los datos.
4. Marco de Auditoría: Proporciona una base computacional para auditar riesgos de privacidad de mecanismos existentes (incluyendo DP) bajo suposiciones de adversarios más realistas.

5. Significado e Impacto

Este trabajo es fundamental porque transita de las garantías teóricas abstractas de la Privacidad Diferencial hacia un marco de Privacidad de la Información más realista y computacionalmente manejable.

• Realismo del Modelo de Amenaza: Al reemplazar la independencia estadística por una restricción de entropía, el modelo refleja mejor la realidad donde los adversarios tienen conocimiento parcial pero correlacionado de los datos.
• Herramientas Prácticas: Ofrece herramientas concretas para diseñar mecanismos de privacidad "certificados" y auditar el riesgo de fuga de información en sistemas de datos reales.
• Futuro: Abre la puerta a la optimización de privacidad en escenarios de alta dimensionalidad y a la integración con pipelines de aprendizaje automático, superando las limitaciones de utilidad de la DP tradicional.

En resumen, el artículo proporciona un marco teórico y computacional robusto para cuantificar y optimizar la privacidad en entornos donde los adversarios tienen conocimientos limitados pero no nulos, logrando mejores equilibrios entre la protección de la privacidad y la utilidad de los datos que los enfoques actuales.