Tenemos un dataset D que contiene datos de usuarios, siendo cada fila los datos de un usuario. El curador, una entidad de confianza para los usuarios, publica algunos datos usando un mecanismo M que da como resultado $R = M(D)$. El adversario trata de realizar inferencias sobre los datos D contenidos en R.

• Usuario: Fila en la BBDD
• Curador: Procesa los datos para responder a un analista
  • Publica mediante un mecanismo ($M(D)$), un algoritmo que oculta los datos a porteger.
• Analista: Intenta hacer inferencias de la BBDD con lo que se publica

La privacidad diferencial protege contra el riesgo de conocimiento de información de un sujeto mediante el uso de inferencia con información externa sobre dicho sujeto. De esta forma, observando la respuesta $R$ no se puede cambiar lo que el adversario puede saber.

No protege contra inferencias que se puedan hacer fuera de la Base de Datos Suponemos que existen 2 Bases de Datos con la única diferencia de que una tiene a Alice y la otra no.

• Se modifica una fila de una Base de datos a Otra
• Existen unas salidas con Alice y otras sin ella.
• La privacidad diferencial busca que estas 2 salidas NO se puedan distinguir
• El mecanismo $M(D)$ no puede dar un resultado diferente cuando Alice está y cuando no.
• El curador va a tomar las respuestas y les va a añadir ruido para que no se puedan distiguir.
• Las distribuciones deben ser lo más parecidas posibles
  • Las 2 distribuciones se tienen que parecer para que la diferencia entre una y otra no sea mayor de un valor P que establecemos.
• So dos bases de datos difieren en una sola fila son bases de datos vecinas.

En resumidas cuentas, la clave para dificultar que un adversario pueda identificar datos sobre un sujeto es crear dos salidas $R = M(D)$ y $R' = M(D')$, siendo D y D' Bases de datos vecinas, de forma que ambas respuestas no puedan ser distinguidas. Para hacer esto se diseña un mecanismo $M$ el cual no puede ser determinístico, tiene que ser probabilístico.

Un mecanismo $M$ es privado si para todas las posibles salidas de $R$ y todos los pares de Bases de datos Vecinas $(D, 'D)$:

El valor de $P$ debe ser uno que no facilite que se pueda identificar cuando Alice no está en la Base de datos. Con esta primera definición nos encontramos con el problema de existen ciertas salidas de R que solo pueden ocurrir cuando la entrada es $D'$, permitiendo diferenciar los dos datasets. Para corregir esto, se realiza la siguiente definición:

Un mecanismo $M$ es privado si para todas las posibles salidas de $R$ y para todos los pares de las bases de datos vecinas $(D, D')$:

Cuanto más alto sea el valor de $P$ menor es la privacidad, por lo tanto, si $P=∞$ no hay privacidad.

Es similar a las dos definiciones antes realizadas, con la diferencia de que se sustituye $p$ con $e^ε$:

Un mecanismo $M: D$ → R es ε-privadamente diferencial ($ε-DP$) si para todas las posibles salidas $R ∈ $ R y todos los pares de las Bases de Datos Vecinas $D,D'∈ D$:

• Usamos $e^ε$ en vez de $ε$ ya que hace más fácil formular algunos teoremas útiles
• $ε ∈ [0,∞)$ asegura que $e^ε ∈ [1,∞)$
• Cuanto más pequeño es el valor de $ε$, mayor es la privacidad
• La privacidad perfecta se da cuando $ε = 0$, pero en cambio, la salida que se obtiene es completamente inútil.
• No existe consenso sobre como de pequeño debe ser el valor de $ε$, pero debe tener un valor que evite que la salida del mecanismo sea inútil.

Si tomamos logaritmos naturales, aparece la siguiente definición alternativa:

A un mecanismo $M : D$ → R es ε-privadamente diferencial (ε-PD) si para todas las posibles salidas $R ∈$ R y todos los pares de las bases de datos vecinas $D,D' ∈$ D:

Uno de los problemas de la privacidad diferencial es que es difícil de interpretar, por ejemplo, considerando el siguiente caso:

• Teniendo en cuenta este caso, sabemos que $Pr(D) = Pr(D') = 0.5$
• El adversario tiene que decidir D si $Pr(D|R) > Pr(D'|R')$, en caso contrario decide D'
• Al hacer eso, existe una probabilidad $P_{err}$ de que el adversario se equivoque.
• Las probabilidades pueden ser calculadas usando el teorema de Bayes:

• Lo que es equivalente a:

• Pero si el mecanismo es $ε-DP$, entonces:

La privacidad diferencial asegura la protección incluso contra adversarios poderosos que saben que la entrada es D o D'. En la práctica un algoritmo que provee $ε = 10$ puede proveer alta protección empírica contra ataques existentes. En este punto el problema es que el peor caso teórico no importa ya que uno puede usar algo que no de privacidad diferencial pero se obtiene un mejor rendimiento empírico.

Considerando el mecanismo laplaciano siendo $X_i$ valores del dataset:

Donde y es una muestra de una distribución laplaciana con media 0 y escalka b:

Este mecanismo provee 1/b-privacidad diferencial. La salida de este mecanismo debe tener la siguiente distribución:

Estas dos distribuciones difieren en la media. Tomando $b=1$ obtenemos una $ε-DP$ con $ε=1$. Supongamos que trucamos el laplaciano en $y > 1000$. El mecanismo es prácticamente el mismo ya que:

De todas formas, truncando vamos de $ε = 1$ a $ε = ∞$, por lo que pasamos de tener una privacidad muy buena a no tener nada de privacidad.

Un mecanismo $M : D$ → R es (ε,δ)-privadamente diferencial ($(ε,δ)-DP$) si para todas las posibles salidas $R ⊂$ R y los pares de bases de datos vecinas $D,D' ∈ D$:

Esta definición es una relajación de la de Privacidad diferencial que permite cierta tolerancia. Si $δ = 0$, entonces tenemos el mismo caso que $ε-DP$

Dependiendo de donde se ejecuta el mecanismo $M(D)$ hay 2 modelos generales para la privacidad diferencial:

• Privacidad diferencial central: Hay un agregador de confianza centralizado.
  • Un mecanismo $M : D$ → R es ε-privadamente diferencial si para todas las salidas $R ⊂$ R y todos los pares de bases de datos vecinas $D,D' ∈ D$:

• Privacidad diferencial local: Cada usuario ejecuta el mecanismo y reporta el resultado al analista
  • Un mecanismo $M : D$ → R es ε-privadamente diferencial si para todas las salidas $R ⊂$ R y todos los pares de inputs $X,X'$:

La definición de la privacidad diferencial se asegura de que correr el mecanismo $M(D)$ en una base de datos vecina producen resultados similares. Normalmente hay 2 definiciones principales para como se definen las bases de datos vecinas en el modelo central:

• Privacidad Diferencial Acotada: $D$ y $D'$ tienen el mismo número de entradas, pero difieren en el valor de una de ellas (Se modifica el valor de una fila)
• Privacidad Diferencial No Acotada: $D'$ es obtenida tras eliminar una entrada de $D$ (Se elimina una fila)

Existen varios mecanismos que proveen privacidad diferenciual que pueden ser aplicados en varios sistemas.

Dada una función $g: D$ → $R^k$ y dos bases de datos vecinas $D,D' ∈ D$. la $l_1-sensibilidad$ de $g$ es el máximo cambio de salida resultante tras reemplazar $D$ con $D'$:

Dada cualquier función g y Δ, podemos convertirla en un Mecanismo de privadidad diferencial si añadimos ruido laplaciano a su salida. El Mecanimso laplaciano se define como:

Donde cada $Y_i$ tiene una distribución independiente siguiendo $Y_i ~Lap(Δ/ε)$

En el caso de la privacidad diferencial local, si la función $g : X$ → $R^k$, entontes dos entradas dadas $X,X' ∈ X$ la $l_1-sensibilidad$ de $g$ es el mayor cambio de la salida que puede resultar de cambiar $X$ por $X'$:

En este caso tenemos un mecanismo $M : {0,1} -> {0,1}$ para privacidad diferencial local:

Se puede realizar una generalización asumiendo una cierta probabilidad de $γ$ de decir la verdad:

Un mecanismo $M : X$ → $Y$ es ε-privadamente diferencial (ε-DP) si las posibles salidas $y ∈ Y$ y todos los pares de bases de entradas vecias $x, x' ∈ X$:

Por lo tanto hay 2 posibles salidas:

• Cuando Y = 0:

• Cuando Y = 1:

• Si $γ≤1/2$, el más grande de los dos es $(1-γ)/γ$, en caso contrario, γ/(1-γ)
• Por lo tanto el nivel de privacidad es el siguiente:

A veces, añadir ruido laplaciano puede destruir la utilidad del mecanismo. En ocasiones no queremos que las respuestas numéricas sean privadas, pero queremos ser capaces de reportar objetos, clases y categorías. La idea del mecanismo exponencial es que podamos reportar una salida privadamente pero con una probabilidad proporcional a su utilidad.

Dada una base de datos $D ∈ D$, un set de salidas $H$ y una función de puntuación $S : D x H$ → R el mecanismo exponecial elige una salida $h ∈ H$ con la siguiente probabilidad:

La sensibilidad está dada por:

Para calcular la probabilidad $Pr(M(D) = h)$ necesitamos computar los valores de puntuación para cada $h ∈ H$, lo que puede ser muy costoso. El mecanismo proporcional elige elementos de forma proporcional a la función de puntuación. Las salidas con utilidad van a ser elegidas con mucha mayor probabilidad.

Los mecanismos anteriores proveían una privacidad diferencial exacta, el emcanismo gaussiano la da aproximada. Se usa la $l_2-sensibilidad$ de $g$:

El mecanismo gaussiano simplemente añade ruido gaussiano a la salida de la función. El mecanismo Gaussiano es definido como $M(D) = g(D) + [Y_1, Y_2 ... Y_k]$ donde cada $Y_i$ tiene una distribución independiente siguiendo $Y_i ~ N(0,σ^2)$ con:

El mecanismo gaussiano provee (ε-∂)-DP

Sea $M : D$ → $γ$ un mecanismo (ε-∂)-DP y $F : Y$ → $Z$ una aplicación posiblemente aleatoria, entonces $F o M$ es (ε-∂)-DP. Esto significa que el procesado nunca decrementa la privacidad, pero puede incrementarla. Esto tiene sentido si consideramos que en caso contrario, el adversario podría diseñar una aplicación $F$ que parcialmente revierta $M$. Es muy importante que $F$ no de depnda de $D$ más allá de $γ$.

Sea $M : D$ → $R$ un mecanismo que provee ε-DP para $D,D'$ que difieren en una entrada. Entonces provee kε-DP para los datasets D,D' que difieren en k entradas. Esto es fácil de provar construiyendo una secuencia de k datasets que difieran en más de una entrada.

Composición ingénua: Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mecanismos donde $M_i$ es $(ε_i,∂_i)-DP$. Entonces $M$ es $(Σ^k_{i=1}ε_i, Σ^k_{i=1}∂_i)$

• Esto significa que ejecutar k mecanismos en el mismo dataset sen sible y publicando todos los k resultados, la privacidad se decremente según se van publicando más resultados.

Composición Avanzada: Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mecanismos donde $M_i$ es $(ε_i,∂_i)-DP$. Entonces $M$ es $(ε\sqrt{8k*log(1/∂')}, k∂+∂)-DP$

Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mencanismos donde $M_i$ es $ε_i-DP$. Sean $D_1, D_2 .... D_k$ una partición determinística de $D$. Publicar las salidas $M_1(D_1), M_2(D_2), ... , M_k(D_k)$ satisface $(max ε_i)-DP$