В 1997 году, когда в штате Массачусетс исследователям в медицинской области начали предоставлять доступ к медицинским картам чиновников, правительство удаляло из списков имена пациентов, их адреса и номера карт соцстрахования. Уильям Уэлд, бывший тогда губернатором, уверил общественность, что восстановить личность по записи будет невозможно.

Уже через несколько дней в офис Уэлда пришло письмо, отправленное студентом из Массачусетского технологического института. В конверт были вложены выписки из медицинской карты губернатора.

Хотя очевидные идентификаторы были удалены, чиновники решили оставить дату рождения, пол и почтовый индекс (ZIP-код). Проведя перекрёстное сравнение этих данных с записями регистрации голосов, Латанья Суини [Latanya Sweeney] смог вычислить медкарту Уэлда.

Работа Суини и другие прорывы в приватности, случившиеся за последние 15 лет, поднимают вопросы безопасности якобы анонимных данных.

«Мы обнаружили, что интуиция людей по поводу того, какие данные считать приватными, работает плохо,- говорит Фрэнк Макшерри из Microsoft Research Silicon Valley. – Компьютеры постоянно совершенствуют свои возможности по выуживанию индивидуальных данных из массива сведений, которые обыватель счёл бы безопасными».

Изучение историй болезней может помочь в поисках генов, ответственных за риск появления болезней типа Альцгеймера, уменьшить количество ошибок в госпиталях, или подобрать наилучшее лекарство для какой-либо болезни. Вопрос только в том, как заполучить все эти данные, не выдавая личной информации? Десятилетнее исследование на эту тему уже подходит к выработке универсального решения.

Этот подход называется «разностной приватностью», и позволяет публиковать данные, охраняя при этом персональную информацию. Алгоритм дифференциации данных позволяет исследователям формировать любой запрос к базе данных, содержащей чувствительную информацию, и получать ответ, «размытый» таким образом, что он не открывает никаких личных данных – даже наличия данных какой-то конкретной персоны в этой базе.

«Идея в том, что вы можете позволить использовать ваши данные, не подвергаясь риску»,- говорит Синтия Дворк из Microsoft Research Silicon Valley. Дворк представила концепцию разностной приватности (РП) в 2005 году при помощи Макшерри, Кобби Ниссима и Адама Смита.

Метод сохраняет право на «правдоподобное отрицание», как говорит Аврим Блюм из Университета Карнеги-Меллон. «Если мне захочется притвориться, что моя личная информация отличается от той, что есть на самом деле – я могу это сделать. Выходные данные механизма РП на практике будут мало отличаться, неважно, включает он настоящего или поддельного меня – поэтому я могу отрицать всё, что хочу».

Такой высокий уровень приватности кажется недостижимым. И в самом деле, не существует полезного алгоритма РП, выдававшего бы полностью идентичный результат в случаях, когда вы предоставляете свои настоящие или вымышленные данные. Но можно разрешить алгоритмам выдавать почти идентичные данные. Степень отличия калибруется и представляет собой квантификацию приватности. Люди или сообщества могут решить, какое значение этого параметра соответствует приемлемой степени потери приватности, а затем выбрать подходящие алгоритмы.

Эксперты по приватности разработали большой ассортимент РП-алгоритмов для обработки разных данных и ответов на разные вопросы по ним. Большая часть работы сложна для восприятия людьми, не являющимися экспертами в области, поэтому учёные разрабатывают стандартизированные компьютерные языки, которые позволят не только экспертам публиковать чувствительные данные РП-способом, просто составив несложную программу. «РП – многообещающая и очень интересная технология»,- говорит Аарон Рот, специалист по информатике в Пенсильванском университете.


Комитет по переписи на сайте OnTheMap использует разностную приватность, публикуя данные, но не разглашая личную информацию

Иголка в стоге сена

Кажется, что для решения проблем с приватностью нужно просто выпускать обобщённые данные, относящиеся к большим группам людей. Но и такой подход чреват нарушением неприкосновенности личных данных.

Допустим, вам необходимо выяснить, есть ли у автора диабет, и вы знаете, что мои данные есть в базе данных. Можно было бы вычесть результаты двух запросов: «У скольких людей в базе диабет» и «Сколько людей в базе, с именем, отличным от Эрика Кларрейх, страдают диабетом».

Комбинация двух таких запросов нарушает мою приватность. Но не всегда понятно, какие именно комбинации вопросов могут нарушить приватность. Нахождение таких комбинаций – это NP-полная задача, то есть, эффективного компьютерного алгоритма для отслеживания подобных «атак» не существует.

В 2008 году исследователи показали опасность публикации совокупной информации, полученной при всеобщих генетических исследованиях – одном из основных инструментов поиска зависимости диабета от генов. Эти исследования подразумевают расшифровку генов тестовой группы от 100 до 1000 пациентов с одним и тем же заболеванием, с последующим подсчётом средней частоты, с которой встречается одна из 100 000 мутаций. Если одна из мутаций встречается в группе гораздо чаще, она отмечается, как потенциально связанная с болезнью.

Команда исследователей под руководством Нильса Гомера, который в то время был аспирантом в Калифорнийском университете, показала, что во многих случаях, зная геном пациента, можно узнать, входил ли он в группу по тестированию геномов. После этого ассоциация медицинских институтов отозвала указ о том, что полученные в генетических исследованиях данные должны быть опубликованы.

Ещё более удивительный вывод сделали исследователи в 2011 году – возможно извлечь персональную информацию о покупках, руководствуясь рекомендательной системой с Amazon, которая выдаёт результаты вроде «купившие А также купили Б и В». Наблюдая за изменениями рекомендаций и сравнивая их с обзорами, которые люди делают о купленных предметах, в нескольких случаях исследователи смогли сказать, что конкретный покупатель купил конкретную вещь в конкретный день – ещё даже до того, как он размещал обзор этой вещи.

Во всех случаях меры защиты частной жизни кажутся адекватными, до тех пор, пока их оказывается недостаточно. Но уже в это время готовился новый подход к защите приватности, полученный путём поисков ответа на основной вопрос: что это значит, защищать приватность?

Приватность двух миров

Если исследователи изучат базу данных больных и найдут связь между курением и некоей формой рака, разностная приватность не защитит человека, курящего в общественном месте, от метки человека с повышенным риском заболеть. Но если курение – это секрет человека, спрятанный в базе, РП его защитит.

«Разностная» – значит, учитывающая разницу двух миров: в одном из них вы позволяете включать ваши личные данные в базу данных, а в другом – не позволяете. Два мира не окажутся абсолютно идентичными, но их можно сделать как можно более похожими, и их практически невозможно будет отличить. В этом и состоит цель РП.

РП концентрируется на алгоритмах, выдающих данные, принимающих запросы к базе данных и выдающих ответы – не точные, а случайным образом изменённые. Если вы зададите один и тот же вопрос по двум базам, отличающимся только данными по одному человеку, вы получите по сути одинаковые ответы.


РП-представление о местоположении пользователей, искавших слово «cricket» в поисковике

Точнее, для любого возможного ответа, вероятность его получения должна быть одинаковой для обеих баз данных; соотношение двух этих вероятностей должно быть ограничено числом R, близким к единице. Чем ближе R к 1, тем сложнее атакующему выяснить, получает он информацию из базы А или из базы Б, и тем более защищённым будет человек Х. Поскольку, если атакующий не может знать, включают ли полученные им данные информацию по Х, он не сможет понять, какие данные относятся к Х.

Исследователи РП обычно говорят о логарифме R, и обозначают его ?. Параметр количественно обозначает утечку личных данных. Чем ближе ? к нулю, тем лучше алгоритм защищает приватность.

Чтобы понять, как можно сконструировать РП-алгоритм, посмотрим на простейший пример такого алгоритма. Он использует сценарий, в котором спрашивающий может делать лишь количественные запросы. Например: «у какого числе людей в базе есть свойство С?»

Допустим, настоящим ответом на один из вопросов будет 157. РП-алгоритм добавит в него «шум» – перед тем, как выдать ответ, добавит или вычтет случайное число. В результате мы получим 153, 159 или 292. Спрашивающему известно распределение вероятности, используемое алгоритмом, поэтому ему примерно понятно, насколько был искажён реальный результат (иначе выдача была бы полностью бесполезна). Но какое именно случайное число было добавлено к ответу, ему неизвестно.

Формулу распределения нужно выбирать аккуратно. Чтобы понять, какое распределение гарантирует приватность, представим, что настойчивый спрашивающий пытается узнать, есть ли я в базе. Он спрашивает: «Сколько человек по имени Эрика Кларрейх есть в базе?». Допустим, он получает ответ 100. Поскольку имя это редкое, он догадывается, что на самом деле ответ было 0 или 1. У него вырисовываются две возможности:

А) ответ – 0, и алгоритм добавил 100 в качестве шума
Б) ответ – 1, и алгоритм добавил 99

Вероятность выбора 100 и 99 должна быть одинаковой. Тогда спрашивающий не сможет отличить эти два случая. Точнее, отношение этих двух вероятностей не должно превышать заранее заданного R. И такое условие должно сохраняться не только для пар 100 и 99, но и для любых двух последовательных чисел.

Таким свойством обладает распределение Лапласа. Его острый пик приходится на ноль, а затем график плавно убывает в обе стороны. Для него выполняется условие существования числа R (ширина распределения), такое, что для двух любых последовательных номеров соотношение их вероятностей равно R.

Для каждой ширины существует одно возможное распределение Лапласа. Поэтому можно поиграть с шириной, чтобы получить распределение, обеспечивающее именно такую степень приватности, которая нам необходима. Для сильной приватности распределение будет относительно широким и плоским. Далёкие от 0 числа будут выпадать почти с такой же вероятностью, что и числа, близкие к нулю. Данные будут размыты достаточно сильно.

Естественно, что между приватностью и полезностью существует противостояние. Чем больше приватности вам нужно, тем больше шума вам придётся добавить, и тем менее полезным окажется ответ. При использовании распределения Лапласа количество добавляемого шума обратно ?. Если параметр приватности равен 0,01, то алгоритм размоет количественные показатели примерно на 100.

Чем больше набор данных, тем меньше заданное размытие повлияет на полезность. В базе из сотен записей размытие величиной в 100 будет мешать больше, чем в базе из миллионов записей. По словам Дворк, для данных интернетовского масштаба, т.е., сотен миллионов, алгоритм уже обеспечивает достаточную для практического использования приватность.

И «шум» по Лапласу – только первый этап реализации РП. Исследователи придумали уже огромное количество гораздо более сложных алгоритмов, у многих из которых отношение полезности и приватности превышает лапласовское в определённых ситуациях.

«Люди всё время находят способы улучшения, и есть ещё куда улучшать»,- говорит Дворк. Касательно более скромных наборов данных, чем интернет, по её словам, «появляются алгоритмы для многих задач».

С алгоритмом РП нет нужды аккуратно анализировать вопросы на предмет нарушения приватности – эта защита уже встроена в алгоритм. Поскольку вопросы, вмешивающиеся не в свои дела, обычно сводятся к небольшим числам, связанным с конкретными людьми, а вопросы иного характера изучают поведение крупных групп, то количество дополнительного шума, которое сводит на нет индивидуальные особенности, мало повлияет на ответы на законные вопросы.

При помощи РП проблемы исследователей данных, вроде перекрёстного сравнения с внешними источниками, исчезают. Математический подход не рассчитывает на то, что у атакующего будут ограниченные источники внешней информации.

«Подход РП подразумевает, что атакующий всемогущ,- говорит Макшерри. – Даже если атакующий вернётся через 100 лет, всё это время накапливая идеи и компьютерные технологии, они всё равно не смогут выяснить, есть ли вы в базе данных. РП защищена от будущего».

Фундаментальный примитив

Пока что мы рассматривали ситуацию, в которой некто делает запросы к базе с числом в качестве ответа. Но в реальности всё сложнее. Исследователям хочется задавать базе много вопросов. И с течением времени кусочки вашей персональной информации проберутся в различные базы, каждая из которых будет отдавать данные, не спрашивая у остальных.

РП обеспечивает точный и простой способ оценки общей угрозы приватности в случае, когда исследователи задают всем базам, в которых присутствуют ваши данные, несколько вопросов. Допустим, если ваши данные есть в двух базах, и эти данные отдаются по алгоритмам, обеспечивающим параметры приватности ?1 и ?2, тогда общее количество утёкшей личной информации составит не более ?1+ ?2. Та же формула работает и для одной базы с несколькими запросами. Для m запросов утечка будет ограничена сверху m*?.

В теории, куратор базы данных может позволить исследователям задавать сколько угодно вопросов, добавляя необходимое количество лапласовского шума к каждому ответу так, чтобы общее количество утёкших личных данных не превышало некоего предела.

Оказывается, что ограничение на числовые ответы не так уж критично. Многие другие запросы можно поменять так, чтобы они превратились в количественные. К примеру, если вам нужно создать список сотни самых популярных имён для младенцев, родившихся в 2012 году, вы могли бы, например, задавать последовательность вопросов типа «Скольким детям дали имена, начинающиеся с А?», и обрабатывать результаты.

«Один из ранних результатов изучения машинного обучения утверждает, что всё, что в принципе возможно изучить, можно изучить при помощи числовых запросов,- говорит Аарон Рот. – Такие запросы – это не игрушки в себе, а фундаментальный примитив»,- то есть, кирпичики, на основе которого можно строить более сложные алгоритмы.

Но есть и подвох. Чем больше вопросов мы можем позволить задать, тем больше шума будет добавлено к каждому ответу. Обратимся к примеру с именами. Если мы решим ограничить максимальный расход приватности ? в 0.01, а имён будет 10 000, тогда ограничение приватности каждого вопроса будет ?/10 000, или 0,000001. Уровень шума составит 10 000/?, или 1 000 000 — и такой уровень просто нивелирует реальные результаты.

Иначе говоря, подход «в лоб» с добавлением лапласовского шума к каждому ответу ограничен количеством возможных вопросов. Для исправления ситуации программистам пришлось разработать более пригодные примитивы – алгоритмические «кирпичики», с помощью которых, учитывая структуры конкретной базы и задачи, могут ответить на большее количество вопросов с большей точностью.

К примеру, в 2005 году Смит обнаружил, что у задачи с именами есть особая структура: удаление информации об одном человеке из базы меняет ответ только для одного из 10 000 имён. Поэтому мы можем добавлять не более, чем 1/? шума в каждый ответ, вместо 10 000/?, и приватность ответа останется в рамках нашего ограничения в ?. Такой примитив можно применять к любому «гистограммному» запросу – то есть, запросу о том, сколько людей попадает в одну из нескольких взаимоисключающих категорий, таких, как имена.

Когда Смит рассказал об этом Дворку, «что-то внутри меня возликовало,- говорит Дворк. – Я понял, что мы можем использовать структуру запроса или расчёта и получать гораздо большую точность ответа».

С тех пор специалисты по информатике разработали большую библиотеку подобных примитивов. И поскольку аддитивное правило объясняет, что происходит с приватностью при комбинировании алгоритмов, программисты могут собирать эти «кирпичики» в сложные структуры, отслеживая при этом ограничение на утечку приватности.

Для упрощения доступа к системе РП для людей, не являющихся экспертами, несколько групп работают над созданием языка программирования, который позволит абстрагироваться от математических основ алгоритмов.


PINQ – один из примеров ЯП для РП

Такие языки программирования для работы с разностной приватностью, как PINQ, обеспечивают интерфейс для чувствительных данных и позволяют задавать вопросы по ним, подправляя ответы для защиты приватности. «Если вы курируете набор данных, вам можно не волноваться о том, что с ним делают люди, пока их запросы сделаны при помощи этого ЯП»,- говорит Макшерри, создавший язык PINQ. «Программа гарантирует безопасность запросов».

Невозобновляемый ресурс

Поскольку простое аддитивное правило для ? задаёт точное верхнее ограничение потери приватности, когда разные базы данных, содержащие ваши данные, выдают ответы на запросы, это правило, по словам Макшерри, превращает приватность в валюту.

К примеру, если вы решите, какое ограничение на потерю приватности лично для вас является приемлемым за всю вашу жизнь, вы можете затем решить «потратить» эту приватность – поменять на деньги, или поддержать хороший исследовательский проект. Каждый раз, когда вы позволяете использовать ваши данные в новом выпуске информации, вы будете знать, каков остаток вашего «бюджета» приватности.

И куратор набора данных может решить, как потратить то количество приватности, которое он решил выпустить – например, рассмотреть предложения от исследовательских проектов, описывающие не только доступные запросы, но и количество используемой в проектах приватности. Затем куратор сможет выбрать, какие проекты наилучшим образом будут использовать имеющейся «бюджет» данного набора информации. После того, как бюджет израсходован, набор данных закрывается.

«Приватность – это невозобновляемый ресурс,- говорит Макшерри. – Как только вы его потратили, он исчезает».

На вопрос о том, какое значение ? представляет допустимое ограничение на потерю приватности, должно отвечать общество, а не программисты. И у каждого может быть свой ответ. И хотя перспектива присваивания ценника такой неосязаемой вещи, как приватность, может выглядеть пугающей, аналоги этого уже существуют.

«Есть другой ресурс с такими же свойствами – часы вашей жизни,- говорит Макшерри. – Их количество ограничено, и после того, как вы их потратили, они исчезают. Но поскольку у нас есть валюта и рынок труда, наше общество придумало, как присвоить ценник человеческому времени. Можно представить, как то же самое случится и с приватностью».