Privacidad diferencial

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de febrero de 2022; las comprobaciones requieren 2 ediciones .

La privacidad diferencial es un conjunto de métodos que proporcionan las consultas más precisas a una base de datos estadística y minimizan la posibilidad de identificar registros individuales en ella.

Introducción

La privacidad diferencial es la definición matemática de la pérdida de datos confidenciales de las personas cuando su información personal se utiliza para crear un producto. El término fue acuñado por Cynthia Dwork en 2006 [1] pero también se usa en una publicación anterior de Dwork, Frank McSherry , Kobe Nissim y Adam D. Smith [2] . El trabajo se basa en particular en la investigación de Nissim e Irit Dinur [3] [4], quienes demostraron que es imposible publicar información de una base de datos estática privada sin exponer parte de la información privada, y que toda la base de datos puede divulgarse. publicando los resultados de un número relativamente pequeño de solicitudes [4] .

Después del estudio, quedó claro que era imposible garantizar la confidencialidad en las bases de datos estadísticas utilizando los métodos existentes y, como resultado, había una necesidad de otros nuevos que limitaran los riesgos asociados con la pérdida de información privada contenida en la estadística. base de datos. Como resultado, se han creado nuevos métodos que permiten, en la mayoría de los casos, proporcionar estadísticas precisas de la base de datos, al tiempo que brindan un alto nivel de confidencialidad [5] [6] .

Principio e ilustración

La privacidad diferencial se basa en introducir aleatoriedad en los datos.

Un ejemplo sencillo desarrollado en las ciencias sociales [7] es pedirle a una persona que responda a la pregunta "¿Tienes el atributo A?" de acuerdo con el siguiente procedimiento:

lanza una moneda
Si surgen cabezas, responda la pregunta con honestidad.
De lo contrario, lanza de nuevo, si sale cara, responde "Sí", si sale cruz, "No".

La confidencialidad surge porque es imposible saber con certeza a partir de la respuesta si una persona tiene un atributo determinado. No obstante, estos datos son significativos, ya que las respuestas positivas provienen de una cuarta parte de las personas que no tienen este atributo, y de las tres cuartas partes de las que sí lo tienen. Por lo tanto, si p es la verdadera proporción de personas con A, entonces esperamos obtener (1/4) (1- p) + (3/4) p = (1/4) + p / 2 respuestas positivas. Por lo tanto, se puede estimar R.

Definición formal y ejemplo de uso

Sea ε un número real positivo y A un algoritmo probabilístico que toma un conjunto de datos como entrada (representa las acciones de una parte confiable que tiene los datos). Denote la imagen de A por im A . El algoritmo A es ε - diferencialmente privado si para todos los conjuntos de datos y que difieren en un elemento (es decir, datos de una persona), así como todos los subconjuntos S del conjunto im A : $D_{1}$ $D_{2}$

$P[{\mathcal {A}}(D_{1})\en S]\leq e^{\epsilon }\times P[{\mathcal {A}}(D_{2})\en S ],$

donde P es la probabilidad.

De acuerdo con esta definición, la privacidad diferencial es una condición del mecanismo de publicación de datos (es decir, determinada por la parte confiable que publica información sobre el conjunto de datos), no el conjunto de datos en sí. Intuitivamente, esto significa que para dos conjuntos de datos similares, el algoritmo privado diferencial se comportará aproximadamente igual en ambos conjuntos de datos. La definición también proporciona una fuerte garantía de que la presencia o ausencia de un individuo no afectará el resultado final del algoritmo.

Por ejemplo, supongamos que tenemos una base de datos de registros médicos donde cada registro es un par de ( Nombre , X ) donde es cero o uno que indica si la persona tiene gastritis o no: $D_{1}$ $X$

Nombre	Presencia de gastritis (X)
Iván	una
Pedro	0
vasilisa	una
Miguel	una
María	0

Ahora supongamos que un usuario malicioso (a menudo denominado atacante) quiere saber si Mikhail tiene gastritis o no. Supongamos también que sabe qué fila contiene información sobre Mikhail en la base de datos. Ahora suponga que a un atacante solo se le permite usar una forma específica de consulta que devuelve una suma parcial de las primeras filas de una columna en la base de datos. Para saber si Mikhail tiene gastritis, el atacante ejecuta consultas: y luego calcula su diferencia. En este ejemplo, , y , por lo que su diferencia es . Esto significa que el campo "Presencia de gastritis" en la línea de Mikhail debe ser igual a . Este ejemplo muestra cómo la información individual puede verse comprometida incluso sin una solicitud explícita de los datos de una persona específica. $Q_{yo}$ $i$ $X$ $Q_{4}(D_{1})$ ${\ estilo de visualización Q_ {3} (D_ {1})}$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $una$ $una$

Continuando con este ejemplo, si construimos el conjunto de datos reemplazando (Mikhail, 1) con (Mikhail, 0), entonces el atacante podrá distinguirlo calculando para cada conjunto de datos. Si un atacante obtuviera valores a través de un algoritmo privado diferencial ε, para un ε suficientemente pequeño, entonces no podría distinguir entre los dos conjuntos de datos. $D_{2}$ $D_{2}$ $D_{1}$ ${\ Displaystyle Q_{4}-Q_{3))$ $Q_{yo}$

El ejemplo de moneda descrito anteriormente es -diferencialmente privado [8] . ${\ estilo de visualización (\ ln 3)}$

Casos límite

El caso cuando ε = 0 es ideal para mantener la confidencialidad, ya que la presencia o ausencia de cualquier información sobre cualquier persona en la base de datos no afecta el resultado del algoritmo, sin embargo, dicho algoritmo no tiene sentido en términos de información útil, ya que incluso con cero número de personas dará el mismo o similar resultado.

Si ε tiende a infinito, entonces cualquier algoritmo probabilístico se ajustará a la definición, ya que la desigualdad siempre se cumple. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Sensibilidad

Sea un entero positivo, sea un conjunto de datos y sea una función. La sensibilidad [9] de la función, denotada por , está determinada por la fórmula $d$ $\mathcal{D}$ $f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$ $\Delta f$

\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},

sobre todos los pares de conjuntos de datos y en , que difieren en no más de un elemento y donde denota la norma . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\ estilo de visualización \ lVert \ cdot \ rVert _ {1}}$ $\ell _{1}$

En el ejemplo anterior de una base de datos médica, si consideramos la sensibilidad de la función , entonces es igual a , ya que cambiar cualquiera de los registros en la base de datos conduce a algo que cambia o no cambia. $d$ $Q_{yo}$ $una$ $Q_{yo}$ $una$

Mecanismo de Laplace

Debido a que la privacidad diferencial es un concepto probabilístico, cualquiera de sus métodos tiene necesariamente un componente aleatorio. Algunos de ellos, como el método de Laplace, utilizan la adición de ruido controlado a la función a calcular.

El método de Laplace añade el ruido de Laplace, es decir, el ruido de la distribución de Laplace , que se puede expresar como una función de densidad de probabilidad y que tiene media y desviación estándar cero . Definamos la función de salida como una función de valor real en la forma donde , y es la consulta que planeamos ejecutar en la base de datos. Por lo tanto, se puede considerar una variable aleatoria continua , donde ${\text{ruido}}(y)\propto \exp(-|y|/\lambda )\,\!$ ${\sqrt {2}}\lambda\,\!$ ${\mathcal {A}}\,\!$ ${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$ $Y\sim {\text{Vuelta}}(\lambda )\,\!\,\!$ $F\,\!$ ${\mathcal {T}}_{\mathcal {A}}(x)\,\!$

{\frac {\mathrm {pdf} ({\mathcal {T}}_({\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({ \mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{ruido}}(tf(D_{1})) }{{\text{ruido}}(tf(D_{2})))}}\,\!

que no es más que (pdf - función de densidad de probabilidad o función de densidad de probabilidad). En este caso, podemos denotar el factor de privacidad ε. Por tanto, según la definición, es ε-diferencialmente privado. Si tratamos de usar este concepto en el ejemplo anterior sobre la presencia de gastritis, entonces para que sea una función privada ε-diferencial, debe cumplirse , ya que ). $e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda } }\,\!$ ${\frac {\Delta (f)}{\lambda }}\,\!$ ${\mathcal {T}}\,\!$ ${\mathcal {A}}\,\!$ ${\ estilo de visualización \ lambda = 1/\ épsilon}$ ${\ estilo de visualización \ Delta (f) = 1}$

Además del ruido de Laplace, también se pueden utilizar otros tipos de ruido (por ejemplo, gaussiano), pero pueden requerir una ligera relajación de la definición de privacidad diferencial [10] .

Composición

Aplicación consistente

Si ejecutamos una consulta ε-diferencialmente segura veces, y el ruido aleatorio introducido es independiente para cada consulta, entonces la privacidad total será (εt)-diferencial. Más generalmente, si existen mecanismos independientes: , cuyas garantías de privacidad son iguales respectivamente, entonces cualquier función será -diferencialmente privada [11] . $T$ $norte$ ${\mathcal {M}}_{1},\dots,{\mathcal {M}}_{n}$ ${\ estilo de visualización \ epsilon _ {1}, \ puntos, \ epsilon _ {n}}$ $g({\mathcal {M}}_{1},\dots,{\mathcal {M}}_{n})$ $(\sum \limits _{i=1}^{n}\epsilon _{i})$

Composición paralela

Además, si las consultas se ejecutan en subconjuntos de la base de datos que no se superponen, la función sería diferencialmente privada [11] . $gramo$ ${\ estilo de visualización (\ max _ {i} {\ épsilon} _ {i})}$

Privacidad de grupo

La privacidad diferencial en general está diseñada para proteger la privacidad entre bases de datos que difieren en una sola línea. Esto significa que ningún adversario con información auxiliar arbitraria puede saber si algún participante individual ha proporcionado su información. Sin embargo, este concepto se puede extender a un grupo si queremos proteger las bases de datos que difieren por filas para que un atacante con información de respaldo arbitraria no pueda saber si los miembros individuales han proporcionado su información. Esto se puede lograr si la fórmula de la definición se reemplaza por [12] , luego para D 1 y D 2 que difieren por filas $C$ $C$ ${\ estilo de visualización \ exp (\ épsilon)}$ ${\ estilo de visualización \ exp (\ épsilon c)}$ $C$

\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon c)\times \Pr[{\mathcal {A}}(D_{2}) \En s]\,\!

Por lo tanto, usar el parámetro (ε/c) en lugar de ε le permite lograr el resultado deseado y proteger las cadenas. En otras palabras, en lugar de que cada elemento sea ε-diferencialmente privado, ahora cada grupo de elementos es ε-diferencialmente privado, y cada elemento es (ε/c)-diferencialmente privado. $C$ $C$

Aplicación de privacidad diferencial a aplicaciones del mundo real

Hasta la fecha, existen varios usos para la privacidad diferencial:

Oficina del Censo de EE . UU. al mostrar estadísticas [13]
Google RAPPOR para recopilar estadísticas sobre software no deseado que infringe las preferencias del usuario [14] ( implementación de código abierto de RAPPOR )
Google , para compartir estadísticas del historial de tráfico [15] .
El 13 de junio de 2016, Apple anunció su intención de utilizar la privacidad diferencial en iOS 10 para mejorar sus ofertas de tecnología y soporte inteligente [16]

Notas

↑ Dwork Cynthia, 2006 , pág. ocho.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim y Adam Smith=. Calibración del ruido a la sensibilidad en el análisis de datos privados // Actas de la Tercera conferencia sobre teoría de la criptografía (TCC'06), Shai Halevi y Tal Rabin (Eds.). - Springer-Verlag, Berlín, Heidelberg, 2006. - P. 266 . -doi : 10.1007/ 11681878_14 .
↑ Dwork Cynthia, 2006 , pág. 12
↑ 12 Nissim et al, 2003 , págs. 202-206.
↑ HILTON, MICHAEL. Privacidad diferencial: un estudio histórico (indefinido) . , pág.1
↑ Dwork, 2008 , págs. 3-13.
↑ Roth y otros, 2014 , pág. quince.
↑ Roth y otros, 2014 , pág. treinta.
↑ Dwork y otros, 2006 , págs. 271-272.
↑ Dwork, 2008 , pág. dieciséis.
↑ 12 McSherry , 2009 , pág. 6.
↑ Dwork Cynthia, 2006 , pág. 9.
↑ Machanavajjhala y otros, 2008 , pág. una.
↑ Erlingsson y otros, 2014 , pág. una.
↑ Abordar la movilidad urbana con tecnología por Andrew Eland . Blog sobre políticas de Google en Europa . Fecha de acceso: 19 de diciembre de 2017. Archivado desde el original el 10 de diciembre de 2017. (indefinido)
↑ Apple - Información de prensa - Apple Previews iOS 10, el mayor lanzamiento de iOS hasta la fecha . manzana _ Fecha de acceso: 16 de junio de 2016. Archivado desde el original el 29 de abril de 2017. (indefinido)

Literatura

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Privacidad: la teoría se encuentra con la práctica en el mapa // En las actas de la 24.ª Conferencia internacional sobre ingeniería de datos (ICDE). — 2008.
Ulfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Respuesta ordinal de preservación de la privacidad agregable aleatoriamente // Actas de la 21.ª Conferencia ACM sobre seguridad informática y de las comunicaciones (CCS). — 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Calibración del ruido a la sensibilidad en el análisis de datos privados // Conferencia de teoría de la criptografía (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Consultas integradas de privacidad: una plataforma extensible para el análisis de datos que preserva la privacidad // Actas de la 35.ª Conferencia internacional SIGMOD sobre gestión de datos (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. Los fundamentos algorítmicos de la privacidad diferencial // Fundamentos y tendencias en informática teórica. - 2014. - Agosto (vol. 9). -doi : 10.1561 / 0400000042 .
Dwork, Cynthia. Privacidad diferencial: una encuesta de resultados // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Teoría de Angsheng y Aplicaciones de Modelos de Computación. Apuntes de clase en informática. - Springer Berlín Heidelberg, 2008. - 25 de abril. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Privacidad diferencial . - Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Revelar información mientras se protege la privacidad // Actas del vigésimo segundo simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos (PODS '03). - ACM, Nueva York, NY, EE. UU., 2003. - doi : 10.1145/773153.773173 .