Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

Resumen Técnico: Filtros de Privacidad Capturados por Residuos

1. Problema y Contexto

La Privacidad Diferencial (DP) es el estándar para proteger datos sensibles. Un desafío central en su implementación práctica es la composición adaptativa: situaciones donde un analista elige las consultas de manera interactiva basándose en los resultados de consultas anteriores. Para gestionar esto, se utilizan filtros de privacidad, algoritmos que monitorean la interacción y detienen el proceso si se supera un presupuesto de privacidad predefinido.

El objetivo ideal es lograr una "composición libre" (free composition): que el costo de privacidad de una composición adaptativa sea idéntico al de una composición no adaptativa (estándar), sin penalizaciones adicionales.

• Se sabe que la composición concurrente es "libre" para muchas formas de DP.
• Para la composición adaptativa, se ha demostrado que es libre para $\epsilon$-DP pura, RDP (basado en Rényi) y zCDP.
• Sin embargo, para formas más precisas de contabilidad, como la Privacidad Natural (que utiliza el Perfil de Pérdida de Privacidad o PLD exacto de cada consulta), la situación es menos clara. La pregunta abierta es: ¿Son los filtros naturales (que usan contabilidad exacta) universalmente libres?

2. Metodología y Marco Teórico

Los autores desarrollan una teoría general basada en la Teoría de la Decisión Estadística y el Orden de Blackwell, utilizando las siguientes herramientas:

• Distribuciones de Pérdida de Privacidad (PLD): Representan las características de privacidad de un mecanismo como una distribución sobre los logaritmos de las razones de verosimilitud.
• Orden de Blackwell: Un orden parcial que permite comparar qué tan "privados" son dos mecanismos. Un mecanismo domina a otro si su información es más difícil de distinguir.
• Curvas de Hockey-Stick y Curvas de Compensación (Tradeoff): Representaciones geométricas de la privacidad que facilitan el análisis de la composición.
• Filtros de Residuo (Residue Filters): Una nueva clase de filtros definida por una regla de actualización de presupuesto $U(B, L)$ que debe satisfacer una condición de residuo: el presupuesto actualizado más el costo de la consulta debe estar dominado por el presupuesto original ($U(B, L) \oplus L \preceq B$).

3. Contribuciones Clave

A. Teoría General de Filtros de Residuo

• Los autores demuestran que los filtros existentes (DP pura, RDP, GDP) son casos particulares de filtros de residuo.
• Introducen el Filtro de Residuo GDP (Gaussian DP), que mejora estrictamente al filtro GDP "ingenuo". Mientras que el filtro ingenuo aproxima la consulta por una distribución Gaussiana y resta el parámetro $\mu$, el filtro de residuo busca el mayor presupuesto residual $\mu'$ tal que la composición de la consulta y el nuevo presupuesto aún esté dentro del límite original. Esto permite un uso más eficiente del presupuesto, especialmente cuando la consulta es difícil de aproximar por una Gaussiana.

B. Caracterización de los Filtros Naturales

• Un filtro natural permite una consulta si la composición exacta de todas las consultas anteriores (usando PLDs) permanece dentro del presupuesto.
• Resultado Principal (Teorema 8): Un filtro natural es universalmente libre (es decir, no tiene costo de adaptividad para ningún presupuesto) si y solo si la familia de consultas es cerrada bajo composición y totalmente ordenada bajo el orden de Blackwell.
• Esto implica que, para consultas generales (como las de DP aproximada $(\epsilon, \delta)$), los filtros naturales no son libres. La falta de un orden total entre las consultas permite que un adversario adaptativo explote la estructura para aumentar la pérdida de privacidad más allá de lo esperado.

C. Costo de la Adaptividad en Filtros Naturales

• Aunque los filtros naturales pueden fallar (no ser libres), los autores cuantifican el daño.
• Para el filtro natural de $(\epsilon, \delta)$-DP, demuestran que, aunque puede violar el presupuesto original, la violación es controlada. El resultado final satisface $(\chi \cdot \epsilon, \chi \cdot \delta)$-DP, donde el factor de degradación $\chi$ es solo polilogarítmico en función del número de rondas $k$ y $1/\delta$.
• Esto significa que el filtro no falla catastróficamente; sigue ofreciendo garantías de privacidad, aunque con parámetros ligeramente más débiles.

D. Nuevas Propiedades Matemáticas

• Demuestran que el conjunto de PLDs, equipado con el orden de Blackwell, posee una propiedad de completitud (existe un supremo único para cualquier familia de PLDs), una propiedad que no estaba documentada previamente en la literatura de contabilidad de privacidad.

4. Resultados Principales

1. Unificación: Los filtros de residuo unifican las técnicas existentes y proporcionan un marco para construir nuevos filtros óptimos.
2. Imposibilidad de Filtros Naturales Libres: Se demuestra que, a diferencia de la DP pura o RDP, los filtros naturales basados en contabilidad exacta no son libres para familias de consultas generales (como $(\epsilon, \delta)$-DP) a menos que las consultas estén totalmente ordenadas.
   • Ejemplo: Para consultas $(\epsilon, \delta)$-DP, un filtro natural puede fallar incluso con 2 rondas de adaptividad.
   • Excepción: Para consultas GDP (Gaussian), que son totalmente ordenadas, el filtro natural es libre.
3. Acotación del Fallo: En el caso de que el filtro natural falle (como en $(\epsilon, \delta)$-DP), el fallo es "bueno": la privacidad se degrada solo por un factor polilogarítmico, no exponencial.
4. Mejora en GDP: El nuevo filtro de residuo para GDP ofrece ahorros significativos de presupuesto en comparación con los métodos de aproximación estándar, especialmente en escenarios de presupuesto bajo o consultas no gaussianas.

5. Significado e Impacto

• Teórico: El trabajo cierra una brecha importante en la teoría de la privacidad diferencial, estableciendo límites fundamentales sobre cuándo la adaptividad puede ser "gratuita". La demostración de que la total ordenación es una condición necesaria para la libertad universal es un resultado profundo que conecta la estructura algebraica de las consultas con la seguridad de los filtros.
• Práctico:
  • Ofrece a los ingenieros de privacidad una guía clara: si se desea usar contabilidad exacta (PLD) en sistemas adaptativos, deben tenerse en cuenta las posibles penalizaciones de privacidad a menos que se restrinja el conjunto de consultas a familias totalmente ordenadas (como GDP).
  • Proporciona el Filtro de Residuo GDP, una herramienta práctica que maximiza la utilidad de los datos al reducir el desperdicio de presupuesto en la composición de mecanismos gaussianos.
  • Asegura que, incluso en el peor de los casos con filtros naturales, la privacidad no colapsa, sino que se mantiene dentro de límites manejables.

En resumen, el artículo establece que la "composición libre" en entornos adaptativos no es una propiedad universal de las técnicas de contabilidad exacta, sino que depende críticamente de la estructura de orden de las consultas utilizadas, y proporciona herramientas matemáticas y algoritmos para gestionar y optimizar estos costos.