Privacidad diferencial

Sea ε un número real positivo y${\displaystyle {\mathcal {A}}}$Sea un algoritmo aleatorio que toma un conjunto de datos como entrada (que representa las acciones de la parte de confianza que posee los datos).${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$denota la imagen de${\displaystyle {\mathcal {A}}}$.

El algoritmo${\displaystyle {\mathcal {A}}}$Se dice que proporciona privacidad diferencial (ε, δ) si, para todos los conjuntos de datos${\displaystyle D_{1}}$y${\displaystyle D_{2}}$que difieren en un solo elemento (es decir, los datos de una persona) y todos los subconjuntos${\displaystyle S}$de${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$:

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\Pr[{\mathcal {A}}(D_{2})\in S]+\delta .}$$

donde la probabilidad se toma sobre la aleatoriedad utilizada por el algoritmo. ^{[ 6 ]} Esta definición a veces se denomina "privacidad diferencial aproximada", siendo la "privacidad diferencial pura" un caso especial cuando${\displaystyle \delta =0}$En este último caso, se suele decir que el algoritmo satisface la privacidad diferencial ε (es decir, omite${\displaystyle \delta =0}$).

La privacidad diferencial ofrece garantías sólidas y robustas que facilitan el diseño modular y el análisis de mecanismos de privacidad diferencial debido a su capacidad de composición , su robustez ante el posprocesamiento y su degradación gradual en presencia de datos correlacionados .

Según esta definición, la privacidad diferencial es una condición del mecanismo de divulgación (es decir, la entidad de confianza que divulga la información sobre el conjunto de datos) y no del conjunto de datos en sí. Intuitivamente, esto significa que, para dos conjuntos de datos similares, un algoritmo con privacidad diferencial se comportará de forma prácticamente idéntica en ambos. Esta definición ofrece una sólida garantía de que la presencia o ausencia de un individuo no afectará significativamente el resultado final del algoritmo.

Por ejemplo, supongamos que tenemos una base de datos de registros médicos.${\displaystyle D_{1}}$donde cada registro es un par ( Nombre , X ), donde${\displaystyle X}$es un valor booleano que indica si una persona tiene diabetes o no. Por ejemplo:

Ahora supongamos que un usuario malicioso (a menudo denominado adversario ) quiere averiguar si Chandler tiene diabetes o no. Supongamos también que sabe en qué fila de la base de datos reside Chandler. Ahora supongamos que al adversario solo se le permite usar una forma particular de consulta.${\displaystyle Q_{i}}$que devuelve la suma parcial de la primera${\displaystyle i}$filas de columna${\displaystyle X}$en la base de datos. Para averiguar el estado de diabetes de Chandler, el adversario ejecuta${\displaystyle Q_{5}(D_{1})}$y${\displaystyle Q_{4}(D_{1})}$, luego calcula su diferencia. En este ejemplo,${\displaystyle Q_{5}(D_{1})=3}$y${\displaystyle Q_{4}(D_{1})=2}$Por lo tanto, su diferencia es 1. Esto indica que el campo "Tiene diabetes" en la fila de Chandler debe ser 1. Este ejemplo resalta cómo la información individual puede verse comprometida incluso sin consultar explícitamente la información de una persona específica.

Continuando con este ejemplo, si construimos${\displaystyle D_{2}}$Al reemplazar (Chandler, 1) con (Chandler, 0), este adversario malicioso podrá distinguir${\displaystyle D_{2}}$de${\displaystyle D_{1}}$mediante computación${\displaystyle Q_{5}-Q_{4}}$para cada conjunto de datos. Si el adversario estuviera obligado a recibir los valores${\displaystyle Q_{i}}$a través de un${\displaystyle \varepsilon }$-algoritmo de privacidad diferencial, para un suficientemente pequeño${\displaystyle \varepsilon }$, entonces no podría distinguir entre los dos conjuntos de datos.

La componibilidad se refiere al hecho de que la distribución conjunta de las salidas de mecanismos diferencialmente privados (posiblemente elegidos de forma adaptativa) satisface la privacidad diferencial. ^{[ 3 ]}

• Composición secuencial. Si consultamos un mecanismo de privacidad diferencial ε${\displaystyle t}$veces, y la aleatorización del mecanismo es independiente para cada consulta, entonces el resultado sería${\displaystyle \varepsilon t}$-privacidad diferencial. En el caso más general, si hay${\displaystyle n}$mecanismos independientes:${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$, cuyas garantías de privacidad son${\displaystyle \varepsilon _ {1},\dots,\varepsilon _ {n}}$privacidad diferencial, respectivamente, entonces cualquier función${\displaystyle g}$de ellos:${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$es${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$-privacidad diferencial. ^{[ 7 ]}

• Composición paralela. Si los mecanismos anteriores se calculan en subconjuntos disjuntos de la base de datos privada, entonces la función${\displaystyle g}$sería${\displaystyle (\max _ {i}\varepsilon _ {i})}$-privacidad diferencial en su lugar. ^{[ 7 ]}

La otra propiedad importante para el uso modular de la privacidad diferencial es la robustez al posprocesamiento. Esto se define como que para cualquier función determinista o aleatoria${\displaystyle F}$definido sobre la imagen del mecanismo${\displaystyle {\mathcal {A}}}$, si${\displaystyle {\mathcal {A}}}$satisface la privacidad diferencial ε, al igual que${\displaystyle F({\mathcal {A}})}$. ^{[ 3 ]}

La propiedad de composición permite la construcción modular y el análisis de mecanismos con privacidad diferencial ^{[ 3 ]} y motiva el concepto de presupuesto de pérdida de privacidad . Si todos los elementos que acceden a datos sensibles de un mecanismo complejo son individualmente con privacidad diferencial, también lo será su combinación, seguida de un posprocesamiento arbitrario. ^{[ 3 ]}

En general, la privacidad diferencial ε está diseñada para proteger la privacidad entre bases de datos vecinas que difieren solo en una fila. Esto significa que ningún adversario con información auxiliar arbitraria puede saber si un participante en particular envió su información. Sin embargo, esto también es extensible. ^{[ 3 ]} Es posible que queramos proteger bases de datos que difieren en${\displaystyle c}$filas, lo que equivale a que un adversario con información auxiliar arbitraria sepa si${\displaystyle c}$Particulares participantes enviaron su información. Esto se puede lograr porque si${\displaystyle c}$Los elementos cambian, la dilatación de probabilidad está limitada por${\displaystyle \exp(\varepsilon c)}$en lugar de${\displaystyle \exp(\varepsilon )}$, ^{[ 8 ]} es decir, para D ₁ y D ₂ que difieren en${\displaystyle c}$elementos:$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$$Por lo tanto, estableciendo ε en su lugar a${\displaystyle \varepsilon /c}$logra el resultado deseado (protección de${\displaystyle c}$elementos). ^{[ 3 ]} En otras palabras, en lugar de tener cada elemento ε-diferencialmente privado protegido, ahora cada grupo de${\displaystyle c}$Los elementos están protegidos de forma ε-diferencialmente privada (y cada elemento es${\displaystyle (\varepsilon /c)}$-privacidad diferencial protegida). ^{[ 3 ]}

Se puede pensar en la privacidad diferencial como la limitación de las tasas de error en una prueba de hipótesis. Consideremos dos hipótesis:

• ${\displaystyle H_{0}}$Los datos de este individuo no se encuentran en el conjunto de datos.

• ${\displaystyle H_{1}}$: Los datos del individuo están en el conjunto de datos.

Entonces, hay dos tasas de error:

• Tasa de falsos positivos (FPR): ${\displaystyle P_{\text{FP}}=\Pr[{\text{El adversario adivina }}H_{1}\mid H_{0}{\text{ es verdadero}}].}$

• Tasa de falsos negativos (FNR): ${\displaystyle P_{\text{FN}}=\Pr[{\text{El adversario supone que }}H_{0}\mid H_{1}{\text{ es verdadero}}].}$

La protección ideal implicaría que ambas tasas de error son iguales, pero para una configuración fija (ε, δ), un atacante puede lograr las siguientes tasas: ^{[ 9 ]}

• ${\displaystyle \{(P_{\text{FP}},P_{\text{FN}})\mid P_{\text{FP}}+e^{\varepsilon }P_{\text{FN}}\geq 1-\delta ,\ e^{\varepsilon }P_{\text{FP}}+P_{\text{FN}}\geq 1-\delta \}}$

El mecanismo de Laplace añade ruido de Laplace (es decir, ruido de la distribución de Laplace , que puede expresarse mediante una función de densidad de probabilidad).${\displaystyle {\text{ruido}}(y)\propto \exp(-|y|/\lambda )\,\!}$, que tiene media cero y desviación estándar${\displaystyle {\sqrt {2}}\lambda \,\!}$). Ahora, en nuestro caso, definimos la función de salida de${\displaystyle {\mathcal {A}}\,\!}$como una función de valor real (llamada como la salida de la transcripción por${\displaystyle {\mathcal {A}}\,\!}$) como${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!}$dónde${\displaystyle Y\sim {\text{Lap}}(\lambda )\,\!\,\!}$y${\displaystyle f\,\!}$es la consulta/función original de valor real que planeábamos ejecutar en la base de datos. Ahora claramente${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)\,\!}$puede considerarse una variable aleatoria continua, donde

$${\displaystyle {\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!}$$

que es como máximo${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$Podemos considerar${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$ser el factor de privacidad${\displaystyle \varepsilon \,\!}$. De este modo${\displaystyle {\mathcal {T}}\,\!}$sigue un mecanismo de privacidad diferencial (como se puede ver en la definición anterior). Si intentamos usar este concepto en nuestro ejemplo de diabetes, entonces se deduce del hecho derivado anteriormente que para tener${\displaystyle {\mathcal {A}}\,\!}$como el${\displaystyle \varepsilon \,\!}$-algoritmo de privacidad diferencial que necesitamos tener${\displaystyle \lambda =1/\varepsilon \,\!}$Aunque aquí hemos utilizado el ruido de Laplace, se pueden emplear otras formas de ruido, como el ruido gaussiano, pero estas podrían requerir una ligera relajación de la definición de privacidad diferencial. ^{[ 8 ]}

Un ejemplo sencillo, especialmente desarrollado en las ciencias sociales , ^{[ 12 ]} consiste en pedirle a una persona que responda a la pregunta "¿Posee usted el atributo A ?", según el siguiente procedimiento:

1. Lanza una moneda .
2. Si sale cara, vuelve a lanzar la moneda (ignorando el resultado) y responde a la pregunta con sinceridad.
3. Si sale cruz, vuelve a lanzar la moneda y responde "Sí" si sale cara, "No" si sale cruz.

(El lanzamiento adicional, aparentemente redundante, del primer caso es necesario en situaciones donde el simple acto de lanzar una moneda puede ser observado por otros, aunque el resultado real permanezca oculto). La confidencialidad surge entonces de la posibilidad de refutar las respuestas individuales.

Pero, en general, estos datos con muchas respuestas son significativos, ya que las respuestas positivas son dadas a una cuarta parte de las personas que no tienen el atributo A y a tres cuartas partes de las personas que realmente lo poseen. Por lo tanto, si p es la proporción real de personas con A , entonces esperamos obtener (1/4)(1- p ) + (3/4) p = (1/4) + p /2 respuestas positivas. Por lo tanto, es posible estimar p .

En particular, si el atributo A es sinónimo de comportamiento ilegal, entonces responder "Sí" no es incriminatorio, siempre que la persona tenga una probabilidad de dar una respuesta "Sí", sea cual sea.

Aunque este ejemplo, inspirado en la respuesta aleatoria , podría aplicarse a los microdatos (es decir, publicar conjuntos de datos con cada respuesta individual), por definición la privacidad diferencial excluye las publicaciones de microdatos y solo es aplicable a las consultas (es decir, agregar respuestas individuales en un solo resultado), ya que esto violaría los requisitos, más específicamente la negación plausible de que un sujeto participó o no. ^{[ 13 ] [ 14 ]}

Una transformación${\displaystyle T}$es${\displaystyle c}$-estable si la distancia de Hamming entre${\displaystyle T(A)}$y${\displaystyle T(B)}$es como máximo${\displaystyle c}$-veces la distancia de Hamming entre${\displaystyle A}$y${\displaystyle B}$para cualesquiera dos bases de datos${\displaystyle A,B}$Si existe un mecanismo${\displaystyle M}$eso es${\displaystyle \varepsilon }$-privacidad diferencial, entonces el mecanismo compuesto${\displaystyle M\circ T}$es${\displaystyle (\varepsilon \times c)}$-privacidad diferencial. ^{[ 7 ]}

Esto podría generalizarse a la privacidad de grupo, ya que el tamaño del grupo podría considerarse como la distancia de Hamming.${\displaystyle h}$entre ${\displaystyle A}$y${\displaystyle B}$(dónde${\displaystyle A}$contiene el grupo y${\displaystyle B}$no). En este caso${\displaystyle M\circ T}$es${\displaystyle (\varepsilon \times c\times h)}$-privacidad diferencial.

En 1977, Tore Dalenius formalizó las matemáticas de la supresión celular . ^{[ 15 ]} Tore Dalenius fue un estadístico sueco que contribuyó a la privacidad estadística a través de su artículo de 1977 que reveló un punto clave sobre las bases de datos estadísticas: que estas no deberían revelar información sobre un individuo que no sea accesible de otra manera. ^{[ 16 ]} También definió una tipología para las divulgaciones estadísticas. ^{[ 4 ]}

En 1979, Dorothy Denning , Peter J. Denning y Mayer D. Schwartz formalizaron el concepto de Rastreador, un adversario que podía aprender el contenido confidencial de una base de datos estadística mediante la creación de una serie de consultas dirigidas y el registro de los resultados. ^{[ 17 ]} Esta y futuras investigaciones demostraron que las propiedades de privacidad en una base de datos solo podían preservarse considerando cada nueva consulta a la luz de (posiblemente todas) las consultas anteriores. Esta línea de trabajo se denomina a veces privacidad de consultas, y el resultado final es que rastrear el impacto de una consulta en la privacidad de los individuos en la base de datos era NP-difícil .

En 2003, Kobbi Nissim e Irit Dinur demostraron que es imposible publicar consultas arbitrarias en una base de datos estadística privada sin revelar cierta cantidad de información privada, y que todo el contenido informativo de la base de datos puede revelarse publicando los resultados de un número sorprendentemente pequeño de consultas aleatorias, mucho menor de lo que sugerían trabajos anteriores. ^{[ 18 ]} Este fenómeno general se conoce como la Ley Fundamental de Recuperación de la Información , y su idea clave, a saber, que en el caso más general, la privacidad no puede protegerse sin inyectar cierta cantidad de ruido, condujo al desarrollo de la privacidad diferencial.

En 2006, Cynthia Dwork , Frank McSherry , Kobbi Nissim y Adam D. Smith publicaron un artículo ^{[ 3 ]} que formalizaba la cantidad de ruido que debía añadirse y proponía un mecanismo generalizado para ello. Este artículo también creó la primera definición formal de privacidad diferencial. ^{[ 4 ]} Su trabajo fue co-receptor del premio TCC Test-of-Time de 2016 ^{[ 19 ]} y del premio Gödel de 2017. ^{[ 20 ]}

Desde entonces, investigaciones posteriores han demostrado que existen muchas maneras de producir estadísticas muy precisas a partir de la base de datos, al tiempo que se garantizan altos niveles de privacidad . ^{[ 1 ]}

• Calibración del ruido a la sensibilidad en el análisis de datos privados , Cynthia Dwork , Frank McSherry , Kobbi Nissim y Adam Smith. 2006. En Actas de la Tercera Conferencia sobre Teoría de la Criptografía (TCC'06). Springer-Verlag, Berlín, Heidelberg, 265-284. Calibración del ruido a la sensibilidad en el análisis de datos privados (Esta es la publicación original de Privacidad diferencial, y no el artículo homónimo de Dwork publicado el mismo año).
• Privacidad diferencial: Un estudio de los resultados, por Cynthia Dwork, Microsoft Research, abril de 2008 (Presenta los hallazgos de los dos primeros años de investigación sobre privacidad diferencial).
• Privacidad diferencial: una introducción para un público no técnico , Alexandra Wood, Micah Altman , Aaron Bembenek, Mark Bun, Marco Gaboardi, et al., Vanderbilt Journal of Entertainment & Technology Law, Volumen 21, Número 1, Otoño de 2018. (Un buen documento introductorio, pero definitivamente *no* para un público no técnico).
• Ficha informativa sobre tecnología: Privacidad diferencial por Raina Gandhi y Amritha Jayanti, Centro Belfer para la Ciencia y Asuntos Internacionales, otoño de 2020
• Privacidad diferencial y el censo estadounidense de 2020 , Estudios de caso del MIT sobre responsabilidades sociales y éticas de la informática, n.º Invierno 2022 (enero). Privacidad diferencial y el censo estadounidense de 2020 .
• Garfinkel, Simson (2025). Privacidad diferencial . Conocimiento esencial de MIT Press. Prensa del MIT. doi : 10.7551/mitpress/15354.001.0001 . ISBN 9780262551656.
• Bowen, Claire McKay y Simson Garfinkel, La filosofía de la privacidad diferencial , AMS Notices, noviembre de 2021.

• Guía práctica para principiantes sobre privacidad diferencial, por Christine Task, Universidad de Purdue, abril de 2012.