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

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

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

В 2003 году Ирит Динур и Кобби Ниссим предложили атаку реконструкции, основанную на зашумленных ответах на множественные статистические запросы. ^[2] Их работа была отмечена премией ACM PODS Alberto O. Mendelzon Test-of-Time Award 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. Алгоритмические основы дифференциальной конфиденциальности Синтии Дворк и Аарона Рота . Основы и тенденции в теоретической информатике. Том 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 Альберто О. Мендельсона за испытание временем".