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