La privacidad diferencial saltó de los trabajos de investigación a los titulares de noticias tecnológicas el año pasado cuando, en el discurso de apertura de WWDC, Craig Federighi, vicepresidente de Ingeniería de Apple, anunció el uso de Apple del concepto para proteger la privacidad del usuario en iOS.

Fue el último ejemplo de una tendencia general: los usuarios e ingenieros despertaron a la importancia de la protección de la privacidad en el software. Las violaciones de privacidad de alto perfil, como el «modo Dios» de Uber, han demostrado en términos contundentes la facilidad con la que los empleados de una empresa pueden hacer un mal uso de los datos confidenciales recopilados de sus clientes.

La cantidad de datos confidenciales que se registran digitalmente está aumentando rápidamente. Ahora, las personas confían más que nunca en los servicios digitales para sus pagos, transporte, navegación, compras y salud. Esta nueva recopilación de datos crea formas cada vez mayores de violar la privacidad.

Pero también crea oportunidades emocionantes-para mejorar las redes de transporte, reducir la delincuencia, curar enfermedades—si se pone a disposición de los científicos e investigadores de datos adecuados. Existe una tensión natural entre proteger la privacidad de las personas en el conjunto de datos y permitir el análisis que podría conducir a un mundo mejor.

Los algoritmos diferencialmente privados son una solución técnica prometedora que podría aliviar esta tensión, permitiendo a los analistas realizar análisis agregados benignos al tiempo que garantizan una protección significativa de la privacidad de cada individuo.

Este campo de la tecnología en desarrollo vale la pena considerarlo en cualquier sistema que busque analizar datos confidenciales. Aunque la garantía de privacidad diferencial se concibió hace solo diez años, ha tenido éxito en la academia y la industria. Los investigadores están inventando y mejorando rápidamente algoritmos diferencialmente privados, algunos de los cuales se han adoptado tanto en iOS de Apple como en Chrome de Google.

Este artículo analiza los factores históricos que conducen a la privacidad diferencial en su forma actual, junto con una definición de privacidad diferencial y un ejemplo de algoritmos diferencialmente privados. Luego analiza algunas implementaciones recientes de alto perfil de algoritmos diferencialmente privados por parte de Google, Apple y otros.

Background

Los algoritmos diferencialmente privados son los últimos en un campo de tecnologías de décadas de antigüedad para el análisis de datos que preservan la privacidad. Dos conceptos anteriores influyeron directamente en la privacidad diferencial:

1. Tamaño mínimo del conjunto de consultas
2. La definición de divulgación estadística de Dalenius.

Explicaremos primero estos, ya que proporcionan un fondo útil para la privacidad diferencial.

Tamaño mínimo de conjunto de consultas El primer concepto es un tamaño mínimo de conjunto de consultas, que, al igual que los algoritmos diferencialmente privados, tiene como objetivo garantizar la seguridad de las consultas agregadas. Las consultas agregadas son aquellas en las que el valor devuelto se calcula en un subconjunto de registros del conjunto de datos, como recuentos, promedios o sumas. Puede ser útil pensar en consultas agregadas como consultas SQL que comienzan con «SELECCIONAR SUMA», «SELECCIONAR RECUENTO»o» SELECCIONAR PROMEDIO». Otros tipos de consultas agregadas incluyen tablas de contingencia e histogramas.

Un tamaño mínimo de conjunto de consultas es una restricción que busca garantizar que las consultas agregadas no puedan filtrar información sobre individuos. Dado algún número de umbral configurado T, se asegura de que cada consulta agregada se realice en un conjunto de al menos registros T. Un tamaño mínimo de conjunto de consultas bloquearía consultas agregadas dirigidas a menos de T individuos. Por ejemplo, si T=2, bloquearía lo siguiente:

«SELECCIONAR PROMEDIO (salario) DONDE name = ‘Troy Brown’;».

porque esta consulta conduciría un promedio sobre un registro (suponemos que solo hay un Troy Brown).

El uso de tamaños de conjuntos de consultas mínimos evita ciertos ataques, pero no viene con una garantía de privacidad y, en la práctica, puede ser eludido por atacantes expertos. Por ejemplo, el atacante podría realizar el ataque anterior con:

«SELECCIONAR SUMA(salario);».

» SELECCIONE SUMA (salario) DONDE nombre != ‘Troy Brown’;».

O incluso, si conocemos la edad de Troy Brown (45) y la posición (WR), lo identificamos de manera única:

«SELECCIONE SUM(salario) DONDE position = ‘WR’;».

«SELECCIONE SUM(salario) DONDE position = ‘WR’ Y age != 45;

Estos ataques se denominan ataques de seguimiento, y no se pueden detener mediante una restricción de tamaño de conjunto de consultas mínimo. Debido a estos ataques, los tamaños mínimos de los conjuntos de consultas se consideraron una defensa inadecuada para proteger los sistemas de consultas (véase el trabajo de Denning). Se necesita algo mejor, con garantías, para garantizar la privacidad.

Definición de divulgación estadística de Dalenius

En 1977, el estadístico Tore Dalenius propuso una definición estricta de privacidad de datos: que el atacante no debería aprender nada sobre un individuo que no conociera antes de usar el conjunto de datos confidenciales. Aunque esta garantía falló (y veremos por qué), es importante para comprender por qué la privacidad diferencial se construye de la manera en que está.

La definición de Dalenius falló porque, en 2006, la científica informática Cynthia Dwork demostró que esta garantía era imposible de dar, en otras palabras, cualquier acceso a datos confidenciales violaría esta definición de privacidad. El problema que encontró fue que ciertos tipos de información de antecedentes siempre podían llevar a una nueva conclusión sobre un individuo. Su prueba se ilustra en la siguiente anécdota: Sé que Alice es dos pulgadas más alta que la mujer lituana promedio. Luego interactúo con un conjunto de datos de mujeres lituanas y computo la altura promedio, que no sabía antes. Ahora sé exactamente la altura de Alice, a pesar de que no estaba en el conjunto de datos. Es imposible dar cuenta de todo tipo de información de fondo que pueda llevar a una nueva conclusión sobre un individuo a partir del uso de un conjunto de datos.

Dwork, tras probar lo anterior, propuso una nueva definición: privacidad diferencial.

¿Qué es la privacidad diferencial?

La privacidad diferencial garantiza lo siguiente: que el atacante no puede aprender prácticamente nada más sobre un individuo de lo que aprendería si el registro de esa persona estuviera ausente del conjunto de datos. Aunque es más débil que la definición de privacidad de Dalenius, la garantía es lo suficientemente fuerte porque se alinea con los incentivos del mundo real: los individuos no tienen ningún incentivo para no participar en un conjunto de datos, porque los analistas de ese conjunto de datos sacarán las mismas conclusiones sobre ese individuo, independientemente de que el individuo se incluya o no en el conjunto de datos. Como su información personal confidencial es casi irrelevante en los resultados del sistema, los usuarios pueden estar seguros de que la organización que maneja sus datos no está violando su privacidad.

Los analistas que aprenden «prácticamente nada más sobre un individuo» significa que están restringidos a un cambio insignificante en la creencia sobre cualquier individuo. (Aquí y abajo, «cambio» se refiere al cambio entre el uso de un conjunto de datos y el uso del mismo conjunto de datos menos el registro de una persona.) El alcance de este cambio está controlado por un parámetro conocido como ϵ, que establece el límite del cambio en la probabilidad de cualquier resultado. Un valor bajo de ϵ, como 0.1, significa que muy poco puede cambiar en las creencias sobre cualquier individuo. Un valor alto de ϵ, como 50, significa que las creencias pueden cambiar sustancialmente más. La definición formal es la siguiente.

Un algoritmo A es differ-diferencialmente privado si y solo si:

Pr ≤ e^for * Pr

para todo x y para todos los pares de conjuntos de datos D, D’ donde D’ es D con cualquier registro, es decir, los datos de una persona, faltantes. El símbolo e se refiere a la constante matemática. Tenga en cuenta que esta definición solo tiene sentido para algoritmos aleatorios. Un algoritmo que da salida determinista no es un candidato para la privacidad diferencial.

El atractivo principal de la garantía de privacidad diferencial es su limitación en la cantidad que cualquier analista puede aprender sobre un individuo. Además, tiene las siguientes propiedades útiles:

• Componibilidad: si se responden dos consultas con garantías de privacidad diferenciales de nivel ϵ1 y22, el par de consultas está cubierto por una garantía de nivel (ϵ1 +22). Recuerde que un valor más alto de ϵ significa una garantía más débil.
• Fuerza contra información de fondo arbitraria: la garantía no se basa de ninguna manera en la información de fondo que conoce el atacante. Esta propiedad es una de las principales razones por las que la privacidad diferencial es más fuerte que una garantía de privacidad anterior, k-anonymity.
• Seguridad en posprocesamiento: no hay restricciones sobre lo que se puede hacer con un resultado diferencialmente privado, sin importar con qué se combine o cómo se transforme, sigue siendo diferencialmente privado.

¿Cómo se consigue esta garantía en el software? Los algoritmos diferencialmente privados son algoritmos aleatorios que agregan ruido en puntos clave dentro del algoritmo. Uno de los algoritmos más simples es el mecanismo de Laplace, que puede procesar los resultados de consultas agregadas (por ejemplo, recuentos, sumas y medias) para hacerlos diferencialmente privados. A continuación se muestra un ejemplo de código Java para el mecanismo de Laplace específico para contar consultas:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

Las partes clave de esta función son

1. Instanciar una distribución de probabilidad de Laplace (ver Figura 1) centrada en 0 y escalada por 1/li. Utilizamos la implementación de Apache Commons, «LaplaceDistribution», que se construye con dos argumentos: la media de la distribución y la escala de la distribución. Tenga en cuenta que un menor epsilon (más privacidad) conduce a una mayor escala y, por lo tanto, a una distribución más amplia y más ruido.
2. Dibuja una muestra aleatoria de esta distribución. Esta función sample () toma un número aleatorio entre 0 y 1 y aplica la función de distribución acumulada inversa (CDF) de la distribución de Laplace a este número. Este proceso da como resultado un número aleatorio tal que su probabilidad de ser un valor específico coincide con la distribución. Como una forma alternativa de pensarlo, si esta función de muestra se invocara un millón de veces para obtener un millón de muestras, la forma del histograma de estas muestras coincidiría estrechamente con la forma de la distribución de Laplace.
3. Perturbar el valor real agregando el valor aleatorio del paso 2.

Consideremos por qué este algoritmo es diferencialmente privado tomando el punto de vista de un atacante llamado Eve. Digamos que el conjunto de datos son datos de salud mental, y Eve ha concebido un ataque de rastreador (ver más arriba) que revelará si su objetivo, Bob, recibe asesoramiento para alcoholismo o no. Si el resultado de la consulta es 48, Eve sabe que Bob recibe asesoramiento; si es 47, Eve sabe lo contrario.

Si la respuesta es 47 o 48, el mecanismo de Laplace devolverá un resultado ruidoso en algún lugar alrededor de 47 o 48. Puede devolver 49, 46, o incluso, con menor probabilidad, 44 o 51 (vea la Figura 2 para un histograma). En la práctica, es imposible que Eva esté muy segura de si la verdadera respuesta fue de 47 o 48 años y, por lo tanto, sus creencias sobre si Bob está en terapia para alcoholismo o ahora no cambiarán significativamente.

Figura 1: La distribución de Laplace centrada en 0 con escala de 1. En la imagen se muestra la función de densidad de probabilidad (PDF) de la distribución: el eje y es la probabilidad relativa de que la variable tome el valor en el eje x.

Figura 2: Los resultados probables de la consulta de recuento para los dos escenarios, donde la respuesta real es 47 y cuando es 48. Un pequeño número de productos no bastaría para distinguir de qué distribución procedían. Epsilon está ajustado a 0,67.

Es posible que haya observado en este punto que Eve podría cortar el ruido repitiendo la consulta muchas veces y viendo si las respuestas se agrupan alrededor de 47 o 48. Para evitar esta táctica, los sistemas diferencialmente privados deben tener un «presupuesto de privacidad», un límite en la suma de las ERS utilizadas en cada consulta. Este límite funciona debido a la propiedad de componibilidad de privacidad diferencial descrita anteriormente. Pueden hacer algunas consultas relativamente poco ruidosas, o muchos cientos de consultas de alto ruido, pero de cualquier manera, no podrán establecer con confianza si la respuesta verdadera es 47 o 48.

Por último, tenga en cuenta que el mecanismo de Laplace para los recuentos es simplemente un algoritmo diferencialmente privado simple. El mecanismo de Laplace se puede ampliar para trabajar con sumas y otras consultas agregadas. Además, hay algoritmos fundamentalmente diferentes que han demostrado satisfacer la garantía de privacidad diferencial. Algunos que vale la pena explorar son el algoritmo Privado de Ponderaciones Multiplicativas, el Mecanismo Exponencial de Ponderaciones Multiplicativas y la DualQuery.

Privacidad diferencial en acción

En junio de 2016, Apple anunció que comenzaría a usar algoritmos diferencialmente privados para recopilar estadísticas de comportamiento de iPhones. Este anuncio, además de causar un gran aumento en el interés por la privacidad diferencial, mostró que la privacidad diferencial puede ayudar a las principales organizaciones a obtener un nuevo valor de los datos que anteriormente no tocaban debido a preocupaciones de privacidad.

Aunque Apple hasta ahora ha hecho públicos algunos detalles, el algoritmo utilizado en el iPhone parece similar al proyecto RAPPOR de Google. Google implementó una función en Chrome que recopila estadísticas de comportamiento de los navegadores Chrome a través de un algoritmo de respuesta aleatorio privado diferencial.

En la respuesta aleatoria, el ruido aleatorio se agrega a las estadísticas antes de enviarlas al recopilador. Por ejemplo, si la estadística real es 0, el navegador con cierta probabilidad reemplazará 0 por un 0 o 1 seleccionado aleatoriamente. Cada usuario tiene un alto grado de negación sobre el valor que su software reporta, porque podría ser un valor aleatorio. Pero colectivamente, la señal se destaca sobre el ruido aleatorio y la organización que recopila las estadísticas (es decir, Google o Apple) puede observar con precisión las tendencias.

Curiosamente, ni Google ni Apple, hasta donde sabemos, han revelado el valor de ϵ que va con su garantía de privacidad diferencial. Necesitamos este valor para comprender la protección que ofrece la garantía. Si utilizan un valor suficientemente alto de ϵ, los analistas aún pueden aprender datos confidenciales sobre los usuarios con gran confianza. Se requiere un valor bajo de ϵ para una protección significativa de la privacidad.

También se han implementado algoritmos diferencialmente privados en productos de análisis que preservan la privacidad, como los desarrollados por mi empleador Privitar. Estos productos permiten a las empresas que trabajan con datos valiosos y confidenciales incorporar algoritmos diferencialmente privados en su arquitectura de datos, proporcionando garantías de privacidad a sus usuarios y al mismo tiempo realizando análisis significativos de los datos.

Mirando hacia el futuro

Tanto las comunidades de ingeniería como de investigación tienen caminos hacia adelante con privacidad diferencial. Para los ingenieros, la tarea es educarse en la privacidad diferencial y asegurarse de que se use cuando sea apropiado para la protección de la privacidad del usuario. Para los investigadores, es encontrar más y mejores algoritmos diferencialmente privados, mejorando el conjunto de herramientas con las que podemos habilitar el análisis de datos que preserva la privacidad.

Todos nos beneficiamos del establecimiento de garantías de privacidad y del éxito del análisis de datos. Por ambas razones, esperamos que más organizaciones adopten la privacidad diferencial.

Acerca del Autor

Charlie Cabot es científico de datos sénior en Privitar, una startup de privacidad de datos que crea software de alto rendimiento para la anonimización de datos, incluidos algoritmos de perturbación y generalización y mecanismos diferencialmente privados, para facilitar el uso seguro de conjuntos de datos confidenciales. Charlie se centra en las garantías de privacidad demostrables y el impacto estadístico de la anonimización en la analítica y la ciencia de datos. Anteriormente, trabajando en seguridad cibernética, Charlie diseñó enfoques basados en el aprendizaje automático para la detección de malware y modeló ataques cibernéticos en redes informáticas.