Реконструкционная атака

Атака реконструкции — это любой метод частичной реконструкции частного набора данных на основе общедоступной совокупной информации. Обычно набор данных содержит конфиденциальную информацию о людях, чью конфиденциальность необходимо защищать. Злоумышленник не имеет доступа к набору данных или имеет только частичный доступ, но имеет доступ к общедоступной совокупной статистике о наборах данных, которая может быть точной или искаженной, например, за счет добавления шума. Если публичная статистика не искажена в достаточной степени, злоумышленник сможет точно восстановить большую часть исходных частных данных. Реконструктивные атаки актуальны для анализа частных данных, поскольку они показывают, что для сохранения даже очень слабого понятия индивидуальной конфиденциальности любая опубликованная статистика должна быть достаточно искажена. «Фундаментальным законом восстановления информации Это явление было названо Дворком и Ротом » и сформулировано так: «чрезмерно точные ответы на слишком большое количество вопросов эффектным образом разрушат конфиденциальность».

Нападение Динур-Ниссим

В 2003 году Ирит Динур и Кобби Ниссим предложили атаку реконструкции, основанную на зашумленных ответах на несколько статистических запросов. Их работа была отмечена премией Альберто О. Мендельзона «Испытание временем» ACM PODS 2013 года отчасти за то, что она стала основой для развития дифференциальной конфиденциальности .

Динур и Ниссим моделируют частную базу данных как последовательность битов. $D=(d_{1},\ldots ,d_{n})$, где каждый бит представляет собой личную информацию одного человека. Запрос к базе данных определяется подмножеством $S\subseteq \{1,\ldots ,n\}$, и определяется равным $q_{S}(D)=\sum _{i\in S}{d_{i}}$. Они показывают, что при приблизительных ответах $a_{1},\ldots ,a_{m}$ к запросам, заданным наборами $S_{1},\ldots ,S_{m}$, такой, что $|a_{i}-q_{S_{i}}(D)|\leq {\mathcal {E}}$для всех $i\in \{1,\ldots ,m\}$, если ${\mathcal {E}}$ достаточно мал и $m$ достаточно велик, то злоумышленник может восстановить большую часть частных битов в $D$. Здесь ошибка связана ${\mathcal {E}}$ может быть функцией $m$ и $n$. Атака Ниссима и Динура работает в двух режимах: в одном режиме $m$ является экспоненциальным по $n$, и ошибка ${\mathcal {E}}$ может быть линейным по $n$; в другом режиме, $m$ полиномиален по $n$, и ошибка ${\mathcal {E}}$ находится в порядке ${\sqrt {n}}$.