Resumen Técnico: DP4SQL - SQL con Privacidad Diferencial y Políticas de Privacidad Flexibles

Declaración del Problema

La privacidad diferencial (DP, por sus siglas en inglés) está bien establecida para conjuntos de datos de una sola tabla, pero su aplicación a bases de datos relacionales sigue siendo un desafío debido a la complejidad de definir la "denegabilidad plausible" a través de múltiples relaciones. Los sistemas de SQL con privacidad diferencial existentes sufren de modelos de privacidad rígidos y predefinidos que no pueden adaptarse a los requisitos matizados de las aplicaciones del mundo real.

Las limitaciones centrales de los sistemas actuales incluyen:

1. Políticas Inflexibles: No pueden manejar escenarios donde diferentes tablas o incluso diferentes columnas dentro de la misma tabla requieren distintos niveles de protección (por ejemplo, proteger la existencia de registros en una tabla mientras solo se protegen los valores de los atributos en otra).
2. Integración de Conocimiento Público: Tienen dificultades para incorporar información pública (por ejemplo, tamaños de tabla conocidos, valores de columnas públicas como nombres de profesores) en el cálculo de la privacidad. Ignorar el conocimiento público suele llevar a una sobreprotección de los datos (inyección de ruido excesivo) o a una protección insuficiente (no lograr enmascarar la existencia de registros cuando el tamaño de la tabla es conocido).
3. Interacciones Complejas de Entidades: Los modelos existentes a menudo no manejan correctamente las claves foráneas y la propiedad transitiva, particularmente cuando las entidades interactúan (por ejemplo, un profesor asignando calificaciones a un estudiante). Esto conduce a cálculos de sensibilidad incorrectos, lo que resulta en una sensibilidad insuficiente (brechas de privacidad) o en un ruido excesivo (pérdida de utilidad).

Metodología

El artículo propone DP4SQL, un sistema que desacopla la especificación de la política de privacidad de alto nivel del razonamiento automatizado de bajo nivel. La metodología consta de tres componentes principales:

1. Marco de Etiquetado de Privacidad de Alto Nivel

Los administradores de datos especifican las políticas utilizando un sistema de etiquetado sencillo de alto nivel para cada relación en el esquema. Para una relación de entidad distinguida $R^\star$ (por ejemplo, Estudiantes o Profesores), a cada relación $R_i$ se le asigna una de tres etiquetas:

• DEL (Delete/Eliminar): La existencia de los registros es privada. Los mundos contrafácticos se crean eliminando registros. Esto corresponde a vecinos no acotados.
• REPA (Replace/Reemplazar): La existencia de los registros es pública, pero atributos específicos $A$ son privados. Los mundos contrafácticos se crean reemplazando valores en $A$. Esto corresponde a vecinos acotados.
• PUB (Public/Público): La relación completa es pública.

Este marco permite políticas mixtas, como proteger la existencia de estudiantes (DEL) mientras se mantienen los nombres de los profesores como públicos (PUB) pero los salarios de los profesores como privados (REPA).

2. Acciones de Denegabilidad Plausible de Bajo Nivel

Para automatizar el razonamiento, el sistema traduce las etiquetas de alto nivel en un conjunto de acciones de denegabilidad plausible que describen el cambio máximo que un resultado de consulta puede experimentar entre bases de datos vecinas. Las acciones son:

• Add$_a$ / Del$_d$: Añadir o eliminar $a$ o $d$ filas.
• Rep$^A_k$: Reemplazar valores de atributos $A$ en $k$ filas.

El sistema emplea un sistema de inferencia con reglas de producción para derivar estas acciones para consultas SQL complejas que involucran:

• Relaciones Base: Las reglas mapean las etiquetas de privacidad a las acciones iniciales, considerando la propiedad máxima ($\hat{\otimes}$) derivada de las restricciones de clave foránea.
• Transformaciones Unarias: Las reglas para Selección ($\sigma$), Proyección ($\pi$) y Agrupación ($\gamma$) propagan las acciones basándose en si los predicados o las claves de agrupación intersectan con los atributos protegidos.
• Joins (Uniones): El sistema distingue entre Key Joins (uniones sobre pares de clave primaria-foránea) y General Joins (uniones generales). Los key joins aprovechan las restricciones de integridad para derivar límites más estrictos sobre los cambios de registros, evitando la sobreaproximación común en las reglas de unión general.

3. Cálculo de Sensibilidad e Inyección de Ruido

Las acciones inferidas se mapean a un límite superior de sensibilidad global ($\hat{\Delta}$). Este límite determina la escala del ruido añadido mediante el mecanismo de Laplace. El sistema calcula la sensibilidad para funciones de agregación (COUNT, SUM) analizando cómo las acciones inferidas (adiciones, eliminaciones, reemplazos) afectan al vector de salida.

Contribuciones Clave

1. Especificación de Política Flexible: Un marco de etiquetado de columnas de alto nivel que soporta políticas de privacidad mixtas (tamaños públicos, columnas públicas, atributos privados) a través de esquemas relacionales con claves foráneas.
2. Motor de Razonamiento Automatizado: Un sistema de inferencia formal que traduce etiquetas de alto nivel en acciones de denegabilidad plausible de bajo nivel, razonando sólidamente sobre la estabilidad de las consultas de álgebra relacional (uniones, agregaciones, subconsultas).
3. Límites de Sensibilidad más Estrechos: Al modelar explícitamente el conocimiento público (por ejemplo, tamaños de tabla conocidos) y utilizar reglas específicas para key-joins, DP4SQL deriva límites de sensibilidad más estrechos que los sistemas existentes, que a menudo asumen escenarios de peor caso para todos los atributos.
4. Implementación y Validación: El sistema está implementado como un middleware de base de datos (DP4SQL) que intercepta las consultas SQL, calcula el ruido requerido y devuelve respuestas con privacidad diferencial.

Resultados

El artículo evalúa DP4SQL utilizando un estudio de caso de esquema universitario y el benchmark TPC-H, comparándolo con políticas de referencia (vecinos puramente no acotados y puramente acotados) y el sistema Tumult Analytics (basado en PrivateSQL).

• Corrección de Privacidad (Sub-protección): En escenarios donde los tamaños de las tablas son públicos (por ejemplo, el número de pedidos en TPC-H), los modelos no acotados de referencia (como Tumult) asumen incorrectamente que la existencia de registros es privada. Esto conduce a una sub-protección (insuficiente ruido) porque no tienen en cuenta que reemplazar un registro (en lugar de eliminarlo) es el contrafáctico válido cuando el tamaño es conocido. DP4SQL identifica correctamente estos casos y aplica el ruido apropiado.
• Mejora de la Utilidad (Sobre-protección): Los modelos de referencia a menudo tratan todos los atributos como privados, lo que conduce a una sobre-protección (ruido excesivo). Por ejemplo, en el estudio de caso universitario, las consultas sobre puntuaciones de reseñas públicas o nombres de profesores resultaron en cero sensibilidad bajo la política flexible de DP4SQL, mientras que los modelos de referencia inyectaron un ruido significativo. En TPC-H, DP4SQL logró cero sensibilidad para consultas que devuelven información pública (por ejemplo, recuentos de proveedores), mientras que los modelos de referencia añadieron ruido que hizo que los resultados fueran inutilizables (error relativo > 100%).
• Precisión: En casos donde los modelos de referencia sobreprotegieron, DP4SQL demostró un error relativo significativamente menor (por ejemplo, 19.6% frente a errores mucho mayores en los modelos de referencia para consultas específicas de TPC-H).

Significado y Reivindicaciones

El artículo afirma que DP4SQL aborda la limitación de "talla única" de los sistemas actuales de SQL con privacidad diferencial. Al permitir que los curadores de datos personalicen los requisitos de denegabilidad plausible, el sistema evita el compromiso entre las brechas de privacidad (debido a la sub-protección) y la pérdida de utilidad de los datos (debido a la sobre-protección).

Los autores enfatizan que su enfoque es sólido (sound): proporcionan pruebas formales de que el sistema de inferencia deriva correctamente un límite superior de la sensibilidad global, asegurando que el mecanismo resultante satisface la $(PS, R^\star, \epsilon)$-privacidad diferencial. El trabajo destaca que el modelado de la privacidad correcto —específicamente la capacidad de razonar sobre tamaños de tablas públicos, columnas públicas y la protección de atributos granulares— es esencial para desplegar la privacidad diferencial en entornos relacionales complejos de múltiples tablas.