Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Título: Más allá de Épsilon: Un Marco QIF Principiado para la Privacidad Diferencial Local

Enunciado del Problema
La Privacidad Diferencial Local (LDP) se ha convertido en el estándar para la recopilación de datos que preservan la privacidad en sistemas a gran escala, particularmente para la estimación de frecuencias. Sin embargo, el panorama actual para comparar protocolos LDP depende en gran medida de dos enfoques limitados:

1. El parámetro $\epsilon$: Este acota la distinguibilidad en el peor de los casos, pero no captura la fuga de información real bajo ataques de inferencia realistas (por ejemplo, reconstrucción de datos o reidentificación). Dos protocolos que satisfacen la misma garantía de $\epsilon$-LDP pueden exhibir comportamientos de fuga significativamente diferentes.
2. Análisis impulsado por la utilidad: Los protocolos se clasifican en función del error de estimación (por ejemplo, Error Cuadrático Medio) para un $\epsilon$ fijo. Esta visión depende de la métrica y no proporciona un ordenamiento principiado de la fuerza de la privacidad independiente de la función de utilidad específica.

En consecuencia, existe una falta de un método sistemático e independiente del adversario para determinar cuándo un protocolo LDP es intrínsecamente más privado que otro.

Metodología
Los autores proponen un marco basado en el Flujo Cuantitativo de Información (QIF) para analizar protocolos de estimación de frecuencias LDP. La metodología central implica:

• Modelado de Canales: Representar los mecanismos LDP como canales probabilísticos de teoría de la información definidos por matrices de canal estocásticas por filas ($C_{x,y} = \Pr[Y=y|X=x]$).
• Relaciones de Refinamiento (Ordenamiento de Blackwell): Utilizar el concepto de refinamiento de canales ($B \sqsubseteq A$) para establecer un orden parcial. El protocolo $A$ refina a $B$ si $A$ no filtra más información que $B$ ante cualquier adversario del caso promedio, independientemente de su conocimiento previo o función de ganancia específica. Esto es equivalente a que $A$ sea un "emborronamiento" de $B$ (es decir, $B \cdot W = A$ para algún canal $W$).
• Conexión con la Privacidad Diferencial $f$: Aprovechar la equivalencia entre el refinamiento QIF y el ordenamiento de las funciones de compromiso en $f$-DP (derivado del lema de Neyman-Pearson) para comparar mecanismos, particularmente para canales binarios.
• Medidas de Vulnerabilidad: Analizar protocolos utilizando la capacidad de Bayes (fuga máxima del caso promedio) y vincular los ataques de reconstrucción de datos directamente a la vulnerabilidad de Bayes bajo una distribución previa uniforme.

Los autores aplican este marco a siete protocolos de última generación: Respuesta Aleatoria Generalizada (GRR), Selección de Subconjuntos (SS), Hashing Local Binario (BLH), Hashing Local Optimizado (OLH), Codificación Unaria Simétrica (SUE), Codificación Unaria Optimizada (OUE) y Umbralización con Codificación de Histograma (THE).

Contribuciones Clave

1. Marco QIF Unificado: El artículo proporciona un marco independiente de la métrica para comparar protocolos LDP mediante matrices de canal y relaciones de refinamiento, permitiendo comparaciones entre adversarios diversos y funciones de utilidad.
2. Puente entre LDP y QIF: Los autores demuestran formalmente que los ataques de reconstrucción de datos estudiados en la literatura previa coinciden con las nociones estándar de QIF de vulnerabilidad de Bayes. Específicamente, la tasa de éxito esperada de tales ataques corresponde a la capacidad de Bayes del canal LDP.
3. Corrección del Análisis de Hashing Local: El artículo identifica y corrige un error en el análisis esperado del ataque de reconstrucción de datos para protocolos de Hashing Local (LH) (específicamente BLH y OLH) reportado en trabajos anteriores [8]. Los autores derivan el riesgo de Bayes correcto mediante vulnerabilidad promediada, proporcionando una fórmula que coincide con las evaluaciones experimentales para todos los tamaños de dominio, a diferencia de la aproximación anterior que fallaba para dominios pequeños.
4. Análisis de Refinamiento: El estudio establece relaciones de refinamiento entre protocolos, descubriendo que:
   • Las familias GRR, SUE, OUE y THE forman "familias de refinamiento" donde la monotonía de la privacidad se cumple con respecto a $\epsilon$.
   • OUE y SUE son incomparables (ninguno refina al otro) en el contexto de bits.
   • THE refina a SUE para todo $\theta$, pero la relación entre THE y OUE depende del umbral $\theta$ y de $\epsilon$.
   • Los protocolos previamente considerados "óptimos" basados en métricas de error a veces están estrictamente dominados por o son incomparables con otros protocolos cuando se observan a través de la lente de la fuga de información.

Resultados

• Validación Experimental: Utilizando el conjunto de datos Kosarak, los autores corroboraron experimentalmente las relaciones de refinamiento teóricas. Por ejemplo, confirmaron que cuando el umbral $\theta$ en THE satisface condiciones específicas en relación con $\epsilon$, OUE filtra más información que THE; de lo contrario, la relación no es de refinamiento.
• Convergencia de la Capacidad de Bayes: El análisis de las capacidades de Bayes reveló comportamientos de convergencia distintos a medida que aumenta $\epsilon$:
  • GRR, SS y THE convergen a $k$ (el tamaño del dominio).
  • SUE converge a un valor ligeramente superior a $k$.
  • BLH converge a 2 (debido a su salida binaria).
  • OLH y OUE convergen a aproximadamente $k/2$.
• Corrección de Fórmulas LH: La nueva fórmula para la Tasa de Éxito del Adversario (ASR) de Hashing Local (Ecuación 26) mostró coincidir con los resultados experimentales para todos los $k$ y $\epsilon$, mientras que la fórmula anterior (Ecuación 25) se desviaba significativamente para tamaños de dominio pequeños.

Significado
El artículo afirma cerrar la brecha entre las comunidades de LDP y métodos formales. Al ir más allá del único parámetro $\epsilon$ y las métricas específicas de la utilidad, el enfoque propuesto basado en QIF permite un "razonamiento principiado y consciente del adversario" sobre sistemas localmente privados. Revela que las clasificaciones basadas únicamente en el error de estimación pueden ser engañosas, ya que pueden pasar por alto casos donde un protocolo está estrictamente dominado por otro en términos de fuga de privacidad. El marco ofrece un método más robusto y comprehensivo para evaluar la superioridad de los protocolos, asegurando que las garantías de privacidad se entiendan no solo como cotas del peor de los casos, sino como medidas precisas del flujo de información frente a diversos modelos de amenazas.