Ataque de reconstrucción

Un ataque de reconstrucción es cualquier método para reconstruir parcialmente un conjunto de datos privados a partir de información pública agregada. Por lo general, el conjunto de datos contiene información sensible sobre individuos cuya privacidad debe protegerse. El atacante no tiene acceso al conjunto de datos o solo tiene acceso parcial a él, pero sí tiene acceso a estadísticas públicas agregadas sobre los conjuntos de datos, que pueden ser exactas o estar distorsionadas, por ejemplo, mediante la adición de ruido. Si las estadísticas públicas no están suficientemente distorsionadas, el atacante puede reconstruir con precisión una gran parte de los datos privados originales. Los ataques de reconstrucción son relevantes para el análisis de datos privados, ya que demuestran que, para preservar incluso una noción muy débil de privacidad individual, cualquier estadística publicada debe estar suficientemente distorsionada. Este fenómeno fue denominado Ley Fundamental de Recuperación de la Información por Dwork y Roth , y formulado como: "las respuestas excesivamente precisas a demasiadas preguntas destruirán la privacidad de forma espectacular". ^{[ 1 ]}

En 2003, Irit Dinur y Kobbi Nissim propusieron un ataque de reconstrucción basado en respuestas ruidosas a múltiples consultas estadísticas. ^{[ 2 ]} Su trabajo fue reconocido con el premio ACM PODS Alberto O. Mendelzon Test-of-Time Award de 2013, en parte por ser la semilla para el desarrollo de la privacidad diferencial . ^{[ 3 ]}

Dinur y Nissim modelan una base de datos privada como una secuencia de bits.${\displaystyle D=(d_{1},\ldots ,d_{n})}$donde cada bit es la información privada de un solo individuo. Una consulta de base de datos se especifica mediante un subconjunto.${\displaystyle S\subseteq \{1,\ldots ,n\}}$y se define como igual${\displaystyle q_{S}(D)=\sum _{i\in S}{d_{i}}}$Demuestran que, dadas las respuestas aproximadas${\displaystyle a_{1},\ldots ,a_{m}}$a consultas especificadas por conjuntos${\displaystyle S_{1},\ldots ,S_{m}}$, de tal manera que${\displaystyle |a_{i}-q_{S_{i}}(D)|\leq {\mathcal {E}}}$ a pesar de${\displaystyle i\in \{1,\ldots ,m\}}$, si${\displaystyle {\mathcal {E}}}$es suficientemente pequeño y${\displaystyle m}$si es suficientemente grande, entonces un atacante puede reconstruir la mayoría de los bits privados en${\displaystyle D}$Aquí el límite de error${\displaystyle {\mathcal {E}}}$puede ser una función de${\displaystyle m}$y${\displaystyle n}$. El ataque de Nissim y Dinur funciona en dos regímenes: en un régimen,${\displaystyle m}$es exponencial en${\displaystyle n}$y el error${\displaystyle {\mathcal {E}}}$puede ser lineal en${\displaystyle n}$; en el otro régimen,${\displaystyle m}$es polinomial en${\displaystyle n}$y el error${\displaystyle {\mathcal {E}}}$es del orden de${\displaystyle {\sqrt {n}}}$.