Matemáticas que aseguran la privacidad: un nuevo enfoque para la seguridad de los datos

En 1997, cuando los investigadores médicos de Massachusetts comenzaron a proporcionar acceso a los registros médicos de los funcionarios, el gobierno eliminó los nombres de los pacientes, sus direcciones y números de seguridad social de las listas. William Weld, entonces gobernador, aseguró al público que sería imposible restaurar la identidad con cita previa.

Unos días después llegó una carta a la oficina de Weld enviada por un estudiante del Instituto de Tecnología de Massachusetts. Los extractos de la tarjeta médica del gobernador estaban encerrados en el sobre.

Aunque se eliminaron los identificadores obvios, los funcionarios decidieron dejar la fecha de nacimiento, el género y el código postal (código postal). Después de comparar estos datos con grabaciones de voz, Latanya Sweeney pudo calcular el historial médico de Weld.

El trabajo de Sweeney y otros avances en la privacidad en los últimos 15 años plantean preocupaciones de seguridad por datos supuestamente anónimos.

"Descubrimos que la intuición de las personas sobre qué datos considerar privados no funciona bien", dice Frank McSherry de Microsoft Research Silicon Valley. "Las computadoras están mejorando constantemente su capacidad de extraer datos individuales de una serie de información que el lego consideraría segura".

Estudiar su historial médico puede ayudarlo a encontrar los genes responsables del riesgo de la enfermedad de Alzheimer, reducir la cantidad de errores en los hospitales o encontrar el mejor medicamento para una enfermedad. La única pregunta es cómo obtener todos estos datos sin dar información personal. Un estudio de diez años sobre este tema ya se está acercando a una solución universal.

Este enfoque se denomina "privacidad diferencial" y le permite publicar datos mientras protege la información personal. El algoritmo de diferenciación de datos permite a los investigadores formular cualquier consulta a una base de datos que contenga información confidencial y recibir una respuesta "borrosa" de tal manera que no revele ningún dato personal, ni siquiera la presencia de datos de una persona en particular en esta base de datos.

"La idea es que puede dejar que sus datos se usen sin riesgo", dice Cynthia Dvork de Microsoft Research Silicon Valley. Dvork introdujo el concepto de privacidad diferencial (RP) en 2005 con la ayuda de McSherry, Cobby Nissim y Adam Smith.

El método conserva el derecho a la "negación plausible", dice Avrim Blum de la Universidad Carnegie Mellon. “Si quiero fingir que mi información personal es diferente de la que realmente tengo, puedo hacerlo. La salida del mecanismo de RP en la práctica no diferirá mucho, sin importar si incluye el verdadero o el falso, por lo que puedo negar todo lo que quiero.

Un nivel tan alto de privacidad parece inalcanzable. Y, de hecho, no existe un algoritmo de RP útil que produzca un resultado completamente idéntico cuando proporciona sus datos reales o ficticios. Pero puede permitir que los algoritmos produzcan datos casi idénticos. El grado de diferencia está calibrado y representa una cuantificación de la privacidad. Las personas o comunidades pueden decidir qué valor de este parámetro corresponde a un grado aceptable de pérdida de privacidad y luego elegir los algoritmos apropiados.

Los expertos en privacidad han desarrollado una amplia gama de algoritmos RP para procesar diferentes datos y responder diferentes preguntas sobre ellos. La mayor parte del trabajo es difícil de percibir para las personas que no son expertas en el campo, por lo tanto, los científicos están desarrollando lenguajes informáticos estandarizados que permitirán que no solo los expertos publiquen datos confidenciales en la RP, simplemente escribiendo un programa simple. "RP es una tecnología prometedora y muy interesante", dice Aaron Roth, un especialista en informática de la Universidad de Pennsylvania.


El Comité del Censo de OnTheMap utiliza privacidad diferencial al publicar datos pero no divulgar información personal

Aguja en un pajar

Parece que para resolver problemas de privacidad solo necesita liberar datos generalizados relacionados con grandes grupos de personas. Pero incluso este enfoque está plagado de una violación de la integridad de los datos personales.

Suponga que necesita averiguar si el autor tiene diabetes y sabe que mis datos están en la base de datos. Uno podría restar los resultados de dos consultas: "Cuántas personas tienen diabetes en la base de datos" y "Cuántas personas en la base de datos, con un nombre que no sea Eric Clarreich, tienen diabetes".

La combinación de dos de estas consultas viola mi privacidad. Pero no siempre está claro qué combinaciones particulares de preguntas pueden violar la privacidad. Encontrar tales combinaciones es una tarea completa de NP, es decir, no existe un algoritmo informático efectivo para rastrear tales "ataques".

En 2008, los investigadores mostraron el peligro de publicar la información agregada obtenida de la investigación genética general, una de las principales herramientas para encontrar la dependencia de la diabetes en los genes. Estos estudios implican decodificar los genes del grupo de prueba de 100 a 1000 pacientes con la misma enfermedad, seguido de calcular la frecuencia promedio con la que ocurre una de las 100,000 mutaciones. Si una de las mutaciones ocurre en el grupo con mucha más frecuencia, se observa que está potencialmente asociada con la enfermedad.

Un equipo de investigadores dirigido por Niels Homer, que era un estudiante graduado en la Universidad de California en ese momento, demostró que en muchos casos, conociendo el genoma del paciente, puede averiguar si él era parte del grupo de pruebas de genoma. Después de eso, la asociación de institutos médicos revocó el decreto de que los datos obtenidos en estudios genéticos deberían publicarse.

Los investigadores llegaron a una conclusión aún más sorprendente en 2011: es posible extraer información personal sobre compras, guiados por un sistema de recomendación con Amazon, que da resultados como "quién compró y también compró B y C". Al observar los cambios en las recomendaciones y compararlas con las revisiones que las personas hacen sobre los artículos comprados, en varios casos, los investigadores pudieron decir que un comprador en particular compró un artículo en particular en un día en particular, incluso antes de publicar una revisión de ese artículo.

En todos los casos, las medidas de privacidad parecen adecuadas, siempre que no sean suficientes. Pero ya en este momento se estaba preparando un nuevo enfoque para proteger la privacidad, obtenido al buscar la respuesta a la pregunta principal: ¿qué significa proteger la privacidad?

La privacidad de dos mundos.

Si los investigadores examinan la base de datos de pacientes y encuentran una conexión entre fumar y alguna forma de cáncer, la privacidad diferencial no protegerá a una persona que fuma en un lugar público de la etiqueta de una persona con un mayor riesgo de enfermarse. Pero si fumar es el secreto de una persona, escondido en la base, RP lo protegerá.

"Diferencia" significa tener en cuenta la diferencia de dos mundos: en uno de ellos le permite incluir sus datos personales en la base de datos, y en el otro no lo permite. Los dos mundos no serán absolutamente idénticos, pero pueden hacerse lo más similares posible, y será casi imposible distinguirlos. Este es el propósito del RP.

RP se centra en algoritmos que emiten datos, reciben consultas a la base de datos y emiten respuestas, no exactas, pero modificadas al azar. Si hace la misma pregunta en dos bases que difieren solo en datos para una persona, obtendrá esencialmente las mismas respuestas.


Representación de RP de la ubicación de los usuarios que buscan la palabra "cricket" en un motor de búsqueda

Más precisamente, para cualquier respuesta posible, la probabilidad de su recepción debería ser la misma para ambas bases de datos; La razón de estas dos probabilidades debe limitarse a un número R cercano a la unidad. Cuanto más cerca esté R de 1, más difícil será para un atacante descubrir si recibe información de la base A o de la base B, y la persona más protegida estará X. Dado que si el atacante no puede saber si la información recibida por él incluye información sobre X, no podrá entienda qué datos se refieren a X. Los

investigadores de RP generalmente hablan sobre el logaritmo de R y lo denotan por Ɛ. El parámetro cuantifica la fuga de datos personales. Cuanto más cerca de Ɛ esté a cero, mejor protegerá el algoritmo la privacidad.

Para comprender cómo se puede construir el algoritmo RP, veamos el ejemplo más simple de dicho algoritmo. Utiliza un escenario en el que el interlocutor solo puede hacer consultas cuantitativas. Por ejemplo: "¿cuántas personas en la base de datos tienen la propiedad C?"

Suponga que la respuesta real a una de las preguntas es 157. El algoritmo RP le agregará "ruido"; antes de emitir una respuesta, sume o reste un número aleatorio. Como resultado, obtenemos 153, 159 o 292. El interlocutor conoce la distribución de probabilidad utilizada por el algoritmo, por lo que sabe qué tan distorsionado es el resultado real (de lo contrario, el retorno sería completamente inútil). Pero no sabe qué tipo de número aleatorio se agregó a la respuesta.

La fórmula de distribución debe elegirse cuidadosamente. Para comprender qué distribución garantiza la privacidad, imaginemos que un solicitante persistente intenta averiguar si estoy en la base de datos. Él pregunta: "¿Cuántas personas llamadas Eric Clarreich están en la base de datos?" Supongamos que recibe una respuesta de 100. Dado que este nombre es raro, se da cuenta de que la respuesta era en realidad 0 o 1. Tiene dos posibilidades:

A) la respuesta es 0, y el algoritmo agregó 100 como ruido;
B) la respuesta es 1, y el algoritmo agregó 99 La

probabilidad de elegir 100 y 99 debería ser la misma. Entonces el interlocutor no puede distinguir entre estos dos casos. Más precisamente, la razón de estas dos probabilidades no debe exceder una R. predeterminada Y tal condición debe preservarse no solo para los pares 100 y 99, sino también para dos números consecutivos.

Esta propiedad tiene la distribución de Laplace. Su pico agudo cae a cero, y luego el gráfico disminuye gradualmente en ambas direcciones. Para ello, se cumple la condición para la existencia del número R (ancho de distribución), de modo que para dos números consecutivos la razón de sus probabilidades es R.

Para cada ancho, hay una posible distribución de Laplace. Por lo tanto, puede jugar con el ancho para obtener una distribución que proporcione exactamente el grado de privacidad que necesitamos. Para mayor privacidad, la distribución será relativamente amplia y plana. Los números lejos de 0 caerán con casi la misma probabilidad que los números cercanos a cero. Los datos serán bastante borrosos.

Naturalmente, hay una confrontación entre privacidad y utilidad. Cuanta más privacidad necesite, más ruido tendrá que agregar y menos útil será la respuesta. Cuando se usa la distribución de Laplace, la cantidad de ruido agregado regresa Ɛ. Si el parámetro de privacidad es 0.01, entonces el algoritmo difuminará los indicadores cuantitativos en aproximadamente 100.

Cuanto mayor sea el conjunto de datos, menos afectará el desenfoque dado a la utilidad. En una base de datos de cientos de registros, un borrón de 100 interferirá más que en una base de datos de millones de registros. Según Dvork, para datos de una escala de Internet, es decir, cientos de millones, el algoritmo ya proporciona suficiente privacidad para un uso práctico.

Y el "ruido" según Laplace es solo la primera etapa de la implementación del RP. Los investigadores ya han creado una gran cantidad de algoritmos mucho más complejos, para muchos de los cuales la relación de utilidad y privacidad excede la de Laplace en ciertas situaciones.

"La gente siempre encuentra formas de mejorar, y todavía hay margen de mejora", dice Dvork. Con respecto a conjuntos de datos más modestos que Internet, dijo, "hay algoritmos para muchas tareas".

Con el algoritmo RP, no es necesario analizar cuidadosamente los problemas de violación de privacidad: esta protección ya está integrada en el algoritmo. Dado que las preguntas que interfieren con sus propios asuntos generalmente se reducen a un pequeño número relacionado con personas específicas, y las preguntas de diferente naturaleza estudian el comportamiento de grupos grandes, la cantidad de ruido adicional que niega las características individuales tendrá poco efecto en las respuestas a preguntas legítimas.

Con RP, los problemas de los investigadores de datos, como las comparaciones cruzadas con fuentes externas, desaparecen. El enfoque matemático no espera que el atacante tenga fuentes limitadas de información externa.

"El enfoque RP implica que el atacante es omnipotente", dice McSherry. - Incluso si el atacante regresa después de 100 años, acumulando ideas y tecnologías informáticas todo el tiempo, aún no podrán saber si usted está en la base de datos. RP está protegido del futuro ".

Primitivo fundamental

Hasta ahora, hemos estado considerando una situación en la que alguien realiza consultas a la base de datos con un número como respuesta. Pero la realidad es más complicada. Los investigadores quieren hacerle muchas preguntas a la base de datos. Y con el tiempo, partes de su información personal llegarán a varias bases de datos, cada una de las cuales proporcionará datos sin preguntar al resto.

RP proporciona una manera precisa y fácil de evaluar la amenaza general a la privacidad cuando los investigadores hacen varias preguntas a todas las bases de datos en las que sus datos están presentes. Suponga que si sus datos están en dos bases de datos, y estos datos se proporcionan de acuerdo con algoritmos que proporcionan los parámetros de privacidad Ɛ1 y Ɛ2, entonces la cantidad total de información personal filtrada no será mayor que Ɛ1 + Ɛ2. La misma fórmula funciona para una sola base de datos con múltiples consultas. Para m consultas, la fuga estará limitada por encima de m * Ɛ.

En teoría, un curador de bases de datos puede permitir a los investigadores hacer tantas preguntas como quieran, agregando la cantidad necesaria de ruido de Laplace a cada respuesta para que la cantidad total de datos personales filtrados no exceda un cierto límite.

Resulta que el límite en las respuestas numéricas no es tan crítico. Se pueden cambiar muchas otras consultas para que se vuelvan cuantitativas. Por ejemplo, si necesita crear una lista de cientos de los nombres más populares para bebés nacidos en 2012, podría, por ejemplo, hacer una secuencia de preguntas como "¿Cuántos niños recibieron nombres que comienzan con A?" Y procesar los resultados.

"Uno de los primeros resultados del aprendizaje automático de aprendizaje afirma que todo lo que se puede aprender en principio se puede aprender mediante consultas numéricas", dice Aaron Roth. "Tales solicitudes no son juguetes en sí mismas, sino una primitiva fundamental", es decir, ladrillos, sobre la base de los cuales se pueden construir algoritmos más complejos.

Pero hay una trampa. Cuantas más preguntas podamos permitir, más ruido se agregará a cada respuesta. Veamos un ejemplo con nombres. Si decidimos limitar el gasto de privacidad máximo Ɛ a 0.01, y los nombres serán 10,000, entonces el límite de privacidad para cada problema será Ɛ / 10,000, o 0.000001. El nivel de ruido será de 10,000 / Ɛ, o 1,000,000, y este nivel simplemente elimina los resultados reales.

En otras palabras, el enfoque "directo" con la adición de ruido de Laplace a cada respuesta está limitado por el número de posibles preguntas. Para remediar la situación, los programadores tuvieron que desarrollar primitivas más adecuadas: "ladrillos" algorítmicos, con la ayuda de los cuales, dada la estructura de una base y tarea específicas, pueden responder más preguntas con mayor precisión.

Por ejemplo, en 2005, Smith descubrió que la tarea con nombres tiene una estructura especial: la eliminación de información sobre una persona de la base de datos cambia la respuesta para solo uno de cada 10,000 nombres. Por lo tanto, no podemos agregar más de 1 / Ɛ de ruido a cada respuesta, en lugar de 10,000 / Ɛ, y la privacidad de la respuesta permanecerá dentro de nuestro límite de . Dicha primitiva se puede aplicar a cualquier consulta de "histograma", es decir, una consulta sobre cuántas personas caen en una de varias categorías mutuamente excluyentes, como los nombres.

Cuando Smith le contó al Dwork sobre esto, "algo dentro de mí se regocijó", dice el Dwork. "Me di cuenta de que podemos usar la estructura de la solicitud o el cálculo y obtener una precisión mucho mayor de la respuesta".

Desde entonces, los científicos informáticos han desarrollado una gran biblioteca de tales primitivas. Y dado que la regla aditiva explica lo que le sucede a la privacidad cuando se combinan algoritmos, los programadores pueden ensamblar estos "ladrillos" en estructuras complejas, mientras monitorean la restricción a la fuga de privacidad.

Para simplificar el acceso al sistema de RP para personas que no son expertas, varios grupos están trabajando en la creación de un lenguaje de programación que nos permita abstraernos de los fundamentos matemáticos de los algoritmos.


PINQ: uno de los ejemplos de PL para RP

Los lenguajes de programación para trabajar con privacidad diferencial, como PINQ, proporcionan una interfaz para datos confidenciales y le permiten hacer preguntas sobre ellos, ajustando respuestas para proteger la privacidad. "Si está a cargo de un conjunto de datos, no tiene que preocuparse por lo que la gente hace con él mientras sus solicitudes se realizan con este PL", dice McSherry, quien creó el lenguaje PINQ. "El programa garantiza la seguridad de las consultas".

Recurso no renovable

Dado que la regla aditiva simple para Ɛ establece el límite superior exacto de la pérdida de privacidad cuando diferentes bases de datos que contienen sus datos brindan respuestas a consultas, esta regla, según McSherry, convierte la privacidad en una moneda.

Por ejemplo, si decide qué restricción a la pérdida de privacidad para usted personalmente es aceptable para toda su vida, puede decidir "gastar" esta privacidad, cambiar por dinero o apoyar un buen proyecto de investigación. Cada vez que permita el uso de sus datos en una nueva publicación de información, sabrá cuál es el saldo de su "presupuesto" de privacidad.

Y el curador del conjunto de datos puede decidir cómo gastar la cantidad de privacidad que decidió liberar; por ejemplo, considere propuestas de proyectos de investigación que describan no solo las solicitudes disponibles, sino también la cantidad de privacidad utilizada en los proyectos. Luego, el curador podrá elegir qué proyectos utilizarán mejor el "presupuesto" existente de este conjunto de información. Después de gastar el presupuesto, se cierra el conjunto de datos.

"La privacidad es un recurso no renovable", dice McSherry. "Tan pronto como lo gastas, desaparece".

Cuando se le pregunta qué valor Ɛ representa una restricción aceptable de la pérdida de privacidad, la sociedad debe responder, no los programadores. Y todos pueden tener su propia respuesta. Y aunque la posibilidad de asignar un precio a una cosa intangible como la privacidad puede parecer desalentadora, ya existen análogos de esto.

"Hay otro recurso con las mismas propiedades: el reloj de tu vida", dice McSherry. "Su número es limitado, y después de gastarlos, desaparecen". Pero dado que tenemos una moneda y un mercado laboral, nuestra sociedad ha ideado cómo asignar un precio al tiempo humano. Uno puede imaginar cómo sucederá lo mismo con la privacidad ".

Source: https://habr.com/ru/post/es398011/