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

А реконструкция атаки - это любой метод частичного восстановления частного набора данных из общедоступной совокупной информации. Как правило, набор данных содержит конфиденциальную информацию о лицах, конфиденциальность которых необходимо защитить. Злоумышленник не имеет доступа к набору данных или имеет только частичный доступ, но имеет доступ к общедоступной совокупной статистике о наборах данных, которая может быть точной или искаженной, например, из-за добавления шума. Если общедоступная статистика недостаточно искажена, злоумышленник может точно восстановить большую часть исходных личных данных. Реконструктивные атаки имеют отношение к анализу частных данных, поскольку они показывают, что для сохранения даже очень слабого представления о личной конфиденциальности любая опубликованная статистика должна быть в достаточной степени искажена. Это явление было названо Фундаментальным законом восстановления информации. Dwork и Рот и сформулирован как «чрезмерно точные ответы на слишком много вопросов впечатляющим образом разрушат конфиденциальность».^[1]

Атака Динура-Ниссима

В 2003 г. Ирит Динур и Кобби Ниссим предложил реконструктивную атаку, основанную на зашумленных ответах на несколько статистических запросов.^[2] Их работа была отмечена премией ACM PODS Alberto O. Mendelzon Test-of-Time в 2013 году отчасти за то, что она стала основой для разработки дифференциальная конфиденциальность.^[3]

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

Рекомендации

1. Алгоритмические основы дифференциальной конфиденциальности Синтии Дворк и Аарон Рот. Основы и тенденции теоретической информатики. Vol. 9, вып. 3-4, стр. 211-407, август 2014 г. DOI: 10.1561 / 0400000042
2. Ирит Динур и Кобби Ниссим. 2003. Раскрытие информации при сохранении конфиденциальности. В материалах двадцать второго симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PODS '03). ACM, Нью-Йорк, Нью-Йорк, США, 202–210. DOI: 10.1145 / 773153.773173
3. "Приз ACM PODS Альберто О. Мендельзон" Испытание временем ".