Обучающий комплекс по дифференциальной конфиденциальности для специалистов по информационной безопасности

Виктория Липатникова

Обучающий комплекс по дифференциальной конфиденциальности для специалистов по информационной безопасности

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

Информатика

Дипломы

Вуз: Санкт-Петербургский государственный политехнический университет (ФГБОУ ВПО «СПбГПУ»)

ID: 60dc20cae4dde5000191eec5

UUID: e13f3340-bba4-0139-3799-0242ac180005

Язык: Русский

Опубликовано: почти 3 года назад

Просмотры: 14

10.28

Виктория Липатникова

Комментировать 0

Рецензировать 0

Скачать - 1,1 МБ

Поделиться работой

Министерство науки и высшего образования Российской Федерации Санкт-Петербургский политехнический университет Петра Великого Институт кибербезопасности и защиты информации Работа допущена к защите Директор Института кибербезопасности и защиты информации, д.т.н., проф. ______________ Д.П. Зегжда «___»______________2021 г. ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА РАБОТА БАКАЛАВРА ОБУЧАЮЩИЙ КОМПЛЕКС ПО ДИФФЕРЕНЦИАЛЬНОЙ КОНФИДЕНЦИАЛЬНОСТИ ДЛЯ СПЕЦИАЛИСТОВ ПО ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ по направлению подготовки (специальности) 10.03.01 Информационная безопасность Направленность (профиль) 10.03.01_03 Безопасность компьютерных систем Выполнил студент гр. 4831001/70301 В.С. Липатникова Руководитель доцент ИКиЗИ, к.т.н., доцент М.А. Полтавцева Санкт-Петербург 2021

РЕФЕРАТ На 63 с., 24 рисунка, 5 таблиц. КЛЮЧЕВЫЕ СЛОВА: КОНФИДЕНЦИАЛЬНОСТЬ, МЕТОД ДИФФЕРЕНЦИАЛЬНАЯ ОБЕСПЕЧЕНИЯ ПРИВАТНОСТИ ДАННЫХ, МЕХАНИЗМ ЛАПЛАСА, РАНДОМИЗИРОВАННЫЙ АЛГОРИТМ, МЕХАНИЗМ ГАУССА Выпускная квалификационная работа на тему «Обучающий комплекс по дифференциальной конфиденциальности для специалистов по информационной безопасности» направленна на теоретическое и практическое понимание дифференциальной конфиденциальности. Целью работы является повышение качества подготовки специалистов по информационной безопасности путем разработки обучающего комплекса по обеспечению дифференциальной конфиденциальности. Задачами, которые решались в процессе работы, являются: − проведение обзора существующих методов обеспечения конфиденциальности данных; − анализ механизмов обеспечения дифференциальной конфиденциальности; − проектирование обучающего комплекса по дифференциальной конфиденциальности для студентов по информационной безопасности. В качестве объекта исследования выступают основные свойства и базовые механизмы обеспечения дифференциальной конфиденциальности. Предметом исследования являются механизмы Лапласа, Гаусса, а также рандомизированный и экспоненциальный алгоритмы. Составленные в результате лабораторные работы содержат задания по программной реализации описанных в теоретической части алгоритмов, вычисления ошибок при применении этих алгоритмов с выявлением причин их возникновения, упражнения для лучшего понимания математического аппарата и основ дифференциальной конфиденциальности, а также контрольные вопросы для проверки знаний, полученных в ходе выполнения лабораторных работ.

Результаты выпускной работы могут быть полезны для студентов, обучающихся информационной безопасности, а также для людей, заинтересованных в теме обеспечения конфиденциальности данных. THE ABSTRACT 63 pages, 24 figures, 5 tables. KEY WORDS: DIFFERENTIAL PRIVACY, DATA PRIVACY METHOD, LAPLACE MECHANISM, RANDOMIZED ALGORITHM, GAUSSIAN MECHANISM The final qualification work on the topic "Training complex on differential privacy for information security specialists" is aimed at theoretical and practical understanding of differential privacy. The aim of the work is to improve the quality of training of information security specialists by developing a training complex for ensuring differential confidentiality. The tasks that were solved in the course of work are: − review of existing data privacy practices; − analysis of differential privacy mechanisms; − designing a training complex on differential privacy for students on information security. The object of the study is the main properties and basic mechanisms for ensuring differential confidentiality. The subject of the study is the Laplace and Gaussian mechanisms, as well as randomized and exponential algorithms. The resulting laboratory work contains tasks for the software implementation of the algorithms described in the theoretical part, calculations of errors in the application of these algorithms with the identification of the causes of their occurrence, exercises for a better understanding of the mathematical apparatus and the basics of differential confidentiality, as well as control questions to test the knowledge gained during the laboratory work. The results of the final work can be useful for students studying information security, as well as for people interested in the topic of data privacy.

4 СОДЕРЖАНИЕ Введение ............................................................................................................. 6 Анализ методов обеспечения анонимности персональных данных ... 9 1.1 Анонимизация .......................................................................................... 9 1.2 Метод добавления шума на основе возмущений .................................. 10 1.3 Добавления мультипликативного шума на основе возмущений ........ 10 1.4 Метод k -анонимизации ........................................................................... 11 1.5 Методы на основе криптографии ........................................................... 11 1.6 Дифференциальные механизмы конфиденциальности ........................ 11 1. 2. Обеспечение анонимности данных путем дифференциальной конфиденциальности ............................................................................... 16 2.1 Типы анализа ............................................................................................ 18 2.2 Формальное определение ........................................................................ 18 2.3 Свойства дифференциальной конфиденциальности ............................ 19 2.3.1 Последовательная композиция ............................................................... 20 2.3.2 Параллельная композиция....................................................................... 22 2.3.3 Постобработка .......................................................................................... 22 2.3.4 Расширенная композиция ........................................................................ 23 2.4 Количественная оценка знаний злоумышленника ............................... 24 2.5 Модели дифференциальной конфиденциальности .............................. 26 2.5.1 Глобальная модель ................................................................................... 26 2.5.2 Локальная модель ..................................................................................... 27 2.6 Чувствительность ..................................................................................... 28 2.6.1 Глобальная чувствительность ................................................................. 29 2.6.2 Локальная чувствительность .................................................................. 29 2.7 Механизмы добавления шума................................................................. 30 2.7.1 Механизм Лапласа ................................................................................... 31 2.7.2 Механизм Гаусса ...................................................................................... 34 2.7.3 Экспоненциальный механизм ................................................................. 36 3. Разработка лабораторных работ для специалистов по информационной

5 безопасности ............................................................................................. 39 3.1 Разработка структуры и тем лабораторных работ ................................ 39 3.2 Инструменты реализации ........................................................................ 40 3.3 Состав лабораторных работ .................................................................... 42 3.3.1 Работа 1 – Механизм рандомизированного ответа............................... 43 3.3.2 Работа 2 – Механизм Лапласа ................................................................. 47 3.3.3 Работа 3 – Механизм Гаусса и свойства дифференциальной конфиденциальности ............................................................................... 51 3.3.4 Работа 4 – Экспоненциальный механизм .............................................. 54 Заключение ........................................................................................................ 59 Список используемых источников .................................................................. 61

6 ВВЕДЕНИЕ В современности любая информация, которая становится известна о человеке, неважно был ли это сбор статистики, анкетирование населения, выборы или просто выполнение запросов под своей учетной записью, для аналитиков может стать кладом, который может раскрыть конфиденциальную информацию человека. С одной стороны подобный сбор информации о людях полезен с точки зрения улучшения качества жизни, однако, с другой стороны, эти данные могут содержать частную информацию, которой пользователь не хочет делиться с общественностью. Так, например, ученые компании Microsoft продемонстрировали, что, анализируя большие выборки запросов поисковых систем, в некоторых случаях они могут идентифицировать интернетпользователей, страдающих раком поджелудочной железы, даже до того, как им будет поставлен диагноз этого заболевания [1]. Следовательно, с развитием технологий, которые обеспечивают все более детальный и эффективный сбор информации, возрастает потребность в надежном и математически строгом определении конфиденциальности, а также в обширном вычислительном классе алгоритмов, удовлетворяющих этому требованию. Для определения режима конфиденциальности общедоступной информации в России в 2006 году был утвержден федеральный закон №152 «О персональных данных», где в статье 3 «Основные понятия, используемые в настоящем Федеральном законе», пункт 8 появляется понятие «обезличивание персональных данных» [2]. Приказ Роскомнадзора №996 Российской Федерации [3] устанавливает методологии обезличивания персональных данных, где описываются такие методы как: метод введения идентификаторов, метод изменения состава или семантики, метод декомпозиции, метод перемешивания. Однако последние уже не являются столь актуальными. В связи с этим многие компании обращаются

7 к иным, более новым методам, среди которых можно выделить дифференциальную конфиденциальность. Актуальностью исследования является распространения понимания дифференциальной конфиденциальности среди специалистов по информационной безопасности с целью дальнейшего развития и применения этого метода обеспечения приватности данных, при которой сохраняется баланс между сохранением полезной нагрузки информации и ее конфиденциальности. В качестве объекта исследования фундаментальные свойства и дифференциальной приватности, основные а данной работы механизмы предметом являются обеспечения исследования являются экспоненциальный механизм и механизмы Лапласа и Гаусса, которые обеспечивают приватность набора данных. Целью этой выпускной квалификационной работы является повышение качества подготовки специалистов информационной безопасности путем разработки обучающего комплекса по обеспечению дифференциальной конфиденциальности. Для достижения вышеописанной цели были поставлены следующие задачи: − провести обзор существующих методов, подходов и алгоритмов обеспечения конфиденциальности данных, а также извлечь их преимущества и недостатки; − проанализировать механизмы обеспечения дифференциальной конфиденциальности; − спроектировать обучающий комплекс по дифференциальной конфиденциальности для студентов информационной безопасности. В качестве теоретической основы использовались исследования Дворк С. и Рота А., а также Фатхима Ш., Дефонтейна Д. и др. Практическая часть была выполнена на основании документации по языку программирования Python, блокнота Jupyter Notebook, и СУБД Oracle.

8 Информационной базой исследования послужили знания и данные, полученные в результате прохождения курсов «Системы управления базами данных», «Теория вероятностей и математическая статистика», а также зарубежные статьи [18-22] и публикации [13-16,23] на тему дифференциальной конфиденциальности. Научная новизна и практическая значимость настоящей работы заключается в анализе методов анонимизации данных, выделении базовых подходов и реализации нового обучающего комплекса для специалистов информационной безопасности конфиденциальности. по обеспечению дифференциальной

9 1. АНАЛИЗ МЕТОДОВ ОБЕСПЕЧЕНИЯ АНОНИМНОСТИ ПЕРСОНАЛЬНЫХ ДАННЫХ В последние десятилетия сбор информации различными компаниями и организациями стал обычным явлением. Полученные данные связаны с определенной потребностью и относятся к какой-либо конкретной области. Как пример, правительственные организации могут собирать информацию в области медицины или экономики для оценки качества жизни населения. Большинство собранных данных при этом персонализированы, а значит, содержат частную информацию. Для обеспечения конфиденциальности было предложено множество различных методов, подходов и алгоритмов сохранения конфиденциальности, среди которых можно выделить: − анонимизация; − метод добавления шума на основе возмущений; − метод добавления мультипликативного шума на основе возмущений; − метод K-анонимизации; − методы на основе криптографии; − дифференциальные механизмы конфиденциальности. 1.1 Анонимизация Данные не могут быть полностью анонимными и оставаться полезными. Чем большей полнотой и структурированностью обладают данные, тем они интереснее и полезнее. Для решения данной проблемы ввели такие понятия, как «анонимность» и «удаление идентификационной информации лиц», которые обеспечивают безвозвратную потерю связности между данными и конкретным субъектом. Однако, если у злоумышленника есть вспомогательная информация из других источников, то анонимизации оказывается недостаточно, так как путем сопоставления этих данных с теми, что были анонимизированы, есть возможность идентификации пользователя.

10 Это доказывают исследования Латаня Суини [4, 5], в которых было показано, что даже при удалении всех явных идентификаторов отдельные лица все равно могут быть повторно идентифицированы посредством связей с другим общедоступным набором данных с помощью комбинации почтового индекса, даты рождения и пола. Методы подобные анонимизации также не обладают композициональностью. Это значит, что при многократном обращении к данным с целью их анализа может появиться проблема потери конфиденциальности и приватности. 1.2 Метод добавления шума на основе возмущений Метод добавления мультипликативного шума на основе возмущений, обеспечивает конфиденциальность и целостность информации. Данный метод достаточно эффективен с математической точки зрения [6-8]. Преимуществом такого подхода является возможность обеспечения конфиденциальности данных во время их сбора. Это обосновывается тем, что дальнейший процесс анализа данных никак не зависит от количества добавляемых возмущений. Но в то же самое время данный плюс обращается в минус, так как снижается общая защищенность информации при искажении. Еще одним недостатком этого метода является то, что последний подвержен атаке ввода-вывода, когда нарушителю известно какое-то количество информации и измененная шумом версия этих же данных. Используя реверс-инжиниринг, атакующих может узнать природу преобразований, которые произошли с данными. 1.3 Добавления мультипликативного шума на основе возмущений Различные методы добавления шума [9, 10], являются с одной стороны эффективными, так как добавление возмущений увеличивает защищенность данных, но с другой стороны из-за применения шума можно потерять информацию вовсе. Из-за этого возникает необходимость поиска компромисса между попытками защиты информации и сохранения ее полезности.

11 1.4 Метод k -анонимизации Метод k-анонимизации [4], является самой популярной моделью конфиденциальности и считается многообещающим, так как использует методы подавления и обобщения информации, которые позволяют добиться отсутствия конфиденциальной информации. Весь набор данных разбивается на несколько групп – классов эквивалентности, в которых каждая запись имеет одинаковые значения атрибутов как минимум с k-1 другими записями. Однако при этом появляется проблема выбора данных для обезличивания, так как, при обезличивании всех значащих полей может возникнуть снижение информативности, а при обезличивании только части – возникает ситуация переизбытка данных в полях. Также этот метод подвержен атакам, в которых при помощи ассоциаций между атрибутами злоумышленник может получить защищаемые дынные. 1.5 Методы на основе криптографии Применяя криптографические протоколы, можно создать анонимные каналы сообщений. Ишай, Кушелевиц и Островский [11] показывают, что анонимные каналы могут повысить эффективность для некоторых вычислительных задач. Существенным недостатком методов, основанных на криптографии, является подверженность внутренним атакам на каналы. Хоть системы и в состоянии отследить злоумышленника, они не могут предотвратить его деятельность, направленную на нарушение конфиденциальности, во время общения участников канала. В результате чего многие схемы имеют низкую эффективность и высокую стоимость. 1.6 Дифференциальные механизмы конфиденциальности Все вышеизложенные методы не обладают твердой теоретической основой для оценки уровня конфиденциальности набора данных. Дифференциальная конфиденциальность конфиденциальности определению. в и отличие набор них предлагает технологий, строгое определение удовлетворяющий этому

12 Особенностью этого метода является то, что он обеспечивает анонимность пользователей, позволяя при этом проводить значимый анализ набора данных. При попытке злоумышленника или аналитика обратиться к базам данных, которые отличаются только одной записью, вероятность изменения конечного результата не будет зависеть от наличия, отсутствия или модификации этой записи, то есть при использовании дифференциальной конфиденциальности невозможно различить базы данных на основе результатов запроса. Таким образом, метод защищает личную информацию человека независимо от того, какая другая информация может быть доступна потенциальному злоумышленнику. Еще одним существенным преимуществом дифференциальной конфиденциальности над ранее рассмотренными методами является то, что она обладает устойчивостью к композициональным атакам. Это значит, что обеспечивается защита от проблем потери приватности, возникающих при многократном обращении к данным с целью их анализа. Описываемый метод привлекателен для множества приложений, поскольку гарантирует «потребности» конфиденциальности, то есть при этом подходе исключаются любые потенциальные методы, которые могут понадобиться аналитику данных, чтобы отличить конкретного человека от других участников идентифицированным или связать человеком. конкретное поведение Следовательно, с ранее дифференциальная конфиденциальность следит за тем, чтобы риск конфиденциальности, связанный с наличием информации о пользователе в базе, существенно не увеличивался [12]. *** Таким образом, в данном разделе выпускной квалификационной работы был произведен анализ существующих методов обеспечения анонимности, в результате которого были рассмотрены уязвимости, связанные с нарушением конфиденциальности субъекта. Также были исследованы достоинства и

13 недостатки вышеизложенных методов. Результаты анализа представлены в таблице 1.

14 Таблица 1 – Сравнительная таблица существующих методов обеспечения анонимности Метод Метод добавления шума на основе возмущений Оценочные параметры алгоритмов, сохраняющих конфиденциальность Уровень Качество данных конфиденциальности после применения метода Энтропия Первоначальные данные могут быть раскрыты с высокой точностью Метод добавления мультипликативного шума на основе возмущений Разница дисперсий между фактическим и возмущенным значением Метод Kанонимизации Зависит от степени случайности (как минимум, 1/K) Недостатки Подвержен атаке на основе известного образца, что позволяет предсказывать значения данных Точные значения Подвержен атаке исходного массива ввода-вывода. данных найти невозможно, но приближенные исходные данные можно Первоначальные Подвержен к атакам данные могут быть с однородностями, раскрыты. если нарушитель обладает первоначальной информацией о конфиденциальном множестве данных Преимущества Позволяет избежать разглашения данных и нарушения их целостности. Конфиденциальность данных может быть обеспечена во время процесса их сбора. С помощью обобщения и усечения детализация представления данных понижается. И в конечном множестве данных отсутствует конфиденциальная информация.

15 Таблица 1 – Сравнительная таблица существующих методов обеспечения анонимности (продолжение) Метод Методы на основе криптографии Оценочные параметры алгоритмов, Недостатки сохраняющих конфиденциальность Уровень Качество данных после конфиденциальности применения метода Зависит от Высокий уровень Плохая криптографических конфиденциальности. эффективность. методов. Дифференциальные Зависит от формы Высокий уровень механизмы шумов (может быть конфиденциальности конфиденциальности Гауссовский шум или шум Лапласа) Ответы на запросы ограничены, из-за чего работа с БД останавливается для предотвращения утечки информации. Преимущества Хорошо могут обеспечить конфиденциальность данных. Защита здесь гарантируется, даже когда атакующий направляет серию адаптивных запросов к БД, изменяя количество шума, добавляемого к каждому результату запроса.

16 2. ОБЕСПЕЧЕНИЕ АНОНИМНОСТИ ДАННЫХ ПУТЕМ ДИФФЕРЕНЦИАЛЬНОЙ КОНФИДЕНЦИАЛЬНОСТИ Основная цель дифференциальной конфиденциальности – гарантировать, что различные виды статистического анализа не нарушат конфиденциальность данных. То есть необходимо убедиться в том, что в результате применения статистического анализа к набору данных, содержащему в себе какую-либо информацию о человеке, не будет поставлена под угрозу конфиденциальность любого конкретного лица, содержащегося в этом наборе данных. Конфиденциальность сохраняется, если после анализа анализатор ничего не знает о людях в наборе данных. Еще говорят, что они остаются «незамеченными». Определим понятие «конфиденциальности». В 1977 году было предложено следующее определение: «Всю информацию, которую можно узнать об участнике в статистической базы данных, можно узнать и без доступа к этой базе данных» [13]. Это говорит о том, что все данные, которые мы хотим получить о человеке, должны быть только публичными. Однако по этому определению, вопервых, совершенно нельзя будет выборочно использовать информацию из каких-либо «частных» баз данных или источников, а это говорит о том, что эти данные перестают нести в себе смысл их использования в целом. А, во-вторых, появляется необходимость следить за тем, являются данные публичными или нет. Все это привело к новому определению, которое сформулировала Синтия Дворк: дифференциальная конфиденциальность описывает обещание, которое дает владелец информации субъекту данных, которое звучит следующим образом: «Вы никак не пострадаете, если позволите использовать ваши данные в каком-либо исследовании или анализе, независимо от того, какие еще наборы данных или источники информации доступны» [14]. Последняя часть содержит одну из ключевых идей, лежащих в основе дифференцированной конфиденциальности и дающих преимущество: она направлена на защиту личной информации человека независимо от того, какая другая информация

17 может быть доступна потенциальному злоумышленнику (например, в других наборах данных). Рассмотрим рисунок 1, где представлен некоторый процесс, на вход принимающий базу данных, а на выходе возвращающий некоторые значения. Рисунок 1 – Демонстрация получения процессом данных Дифференциальная приватность — это свойство, которое обеспечивает конфиденциальность процесса, путем внесения случайности в набор данных. Значит для того, чтобы сделать процесс дифференциально частным, необходимо применить рандомизированный алгоритм, который будет вносить в изначальные данные некую меру случайности или, как еще называют, шум. Дифференциальная конфиденциальность достигается, когда злоумышленник не может отличить ответы, полученные рандомизированным алгоритмом на запрос от изначальной базы данных и базы данных без одного человека, как показано на рисунке 2. Рисунок 2 – Неразличимость баз данных злоумышленником То есть изучаемый метод позволяет человеку находиться в базе данных и дает гарантию, что злоумышленник не сможет об этом узнать. Если распределения вероятностей будут близки друг к другу, то влияние одного человека на любой результат из возможных будет незначительным. Это

18 позволяет людям участвовать в опросах или исследованиях и предоставлять личную информацию, так как есть уверенность в том, что их данные буду защищены. 2.1 Типы анализа Обработка данных подразумевает под собой различные виды анализа информации. Рассмотрим методы, для которых обеспечивается дифференциальная конфиденциальность. 1. Численные запросы – запросы, направленные на оценку количества отдельных записей в базе данных, которые удовлетворяют определенному свойству. Например, это может быть запрос числа людей в университете с голубыми глазами. 2. Гистограммы содержат информацию, классифицированную по непересекающимся категориям. 3. Кумулятивные функции распределения отражают вероятность того, что результат запроса будет меньше заданного значения или равен ему. 4. Линейная регрессия, которая показывает зависимость одной переменной от другой. Например, исследователь может попытаться понять, как здоровье человека зависит от его образования и дохода. 5. Кластеризация – метод анализа, включающий группировку точек данных в кластеры по общим признакам. 6. Классификация определяет категорию, к которой относятся данные. 7. Синтетические данные – это данные, полученные в результате ручного создания данных или путем применения какого-либо генератора [15]. 2.2 Формальное определение Введем формальное определение дифференциальной конфиденциальности, которая гарантирует, что рандомизированный алгоритм будет выдавать близкие выходные значения при схожих входных данных. Пусть Ɛ – положительное действительное число, A – вероятностный алгоритм, который принимает на вход набор данных, а 𝑃 − вероятность.

19 Определение 1: Базы данных будем называть соседними, если они отличаются только наличием или отсутствием одного человека. Определение 2: Рандомизированный алгоритм 𝐴 обеспечивает (Ɛ, 𝛿) – дифференциальную конфиденциальность, если для соседних баз данных D1 и D2 и для всех 𝑆 ⊆ 𝑅𝑎𝑛𝑔𝑒(𝐴) выполняется следующее выражение: 𝑃[𝐴(𝐷1) ∈ 𝑆] ≤ 𝑒𝑥𝑝Ɛ ∗ 𝑃[𝐴(𝐷2) ∈ 𝑆] + δ, где Ɛ называют бюджетом приватности, а параметр δ характеризует вероятность случайной утечки информации. Если значение параметра Ɛ близко к 0, то экспоненциальная функция 𝑒𝑥𝑝Ɛ близка к 1, а значит вероятности приблизительно одинаковы. Тогда достигается полная конфиденциальность данных, однако получается, что точность алгоритма низкая. Это вызвано тем, что к данным прибавляется большое количество шума. Следовательно, чем больше значение Ɛ, тем сильнее вероятности отличаются друг от друга, то есть информация менее конфиденциальна. Определение 3: Если δ = 0, то алгоритм A называют Ɛ – дифференциально конфиденциальным и говорят, что для всех соседних баз данных D1 и D2 и всех выходных значений алгоритма A нельзя различить, какая база данных является истинной, на основе наблюдения за выходными данными. Важно отметить, что дифференциальная конфиденциальность – это свойство не данных, а алгоритма A, который обеспечивает распределение вероятностей в диапазоне 𝑅𝑎𝑛𝑔𝑒(𝐴). 2.3 Свойства дифференциальной конфиденциальности Дифференциальная конфиденциальность свойствами: 1. Последовательной композицией. 2. Параллельной композицией. обладает тремя основными

20 3. Устойчивостью к постобработке. Рассмотрим каждое более подробно. 2.3.1 Последовательная композиция Последовательная композиция ограничивает конфиденциальность при публикации нескольких результатов дифференциально частных механизмов, полученных на одном и том же наборе данных. По теореме о последовательной композиции [16]: конфиденциальностью, если 𝐴1 (𝐷) обладает Ɛ1 – дифференциальной а 𝐴2 (𝐷) обладает Ɛ2 – дифференциальной конфиденциальностью, то механизм 𝐴(𝐷) = (𝐴1 (𝐷), 𝐴2 (𝐷)), который выводит оба результата, удовлетворяет Ɛ1 + Ɛ2 – дифференциальной конфиденциальности. Пусть 𝐴1 (𝐷) обладает бюджетом конфиденциальности Ɛ1 = 1, а 𝐴2 (𝐷) имеет Ɛ2 = 2. Продемонстрируем приватность, используя механизм Лапласа. Рисунок 3 – Плотность распределений Лапласа для дифференциально частных алгоритмов 𝐴1 (𝐷) и 𝐴2 (𝐷) Как видно из рисунка 3 𝐴2 (𝐷) обеспечивает большую вероятность получения результатов, близких к действительному значению и, следовательно, меньшую приватность. Рассмотрим графики плотностей последовательной композиции 𝐴1 (𝐷) и 𝐴2 (𝐷).

21 Рисунок 4 – Сравнение графиков плотности вероятности 𝐴1 (𝐷) и последовательной композиции 𝐴1 (𝐷) и 𝐴2 (𝐷) Рисунок 4 показывает, что последовательная композиция дает более точные выходные значения, что неудивительно, так как бюджет конфиденциальности Ɛ1 + Ɛ2 больше Ɛ1 . Однако рисунок 5 изображает, что рассматриваемая композиция обеспечивает больший разброс величин. Это связано с тем, что конфиденциальность здесь описывается последовательным составом и, так как Ɛ1 в Ɛ1 + Ɛ2 меньше Ɛ2 в 𝐴2 (𝐷), то уровень приватности выше. Рисунок 5 – Сравнение графиков плотности вероятности 𝐴2 (𝐷) и последовательной композиции 𝐴1 (𝐷) и 𝐴2 (𝐷) Таким образом, последовательная композиция позволяет контролировать уровень конфиденциальности, устанавливая границы бюджета приватности, что добавляет еще одно конфиденциальности. преимущество в копилку дифференциальной

22 2.3.2 Параллельная композиция Параллельная композиция базируется на идее разделения набора данных 𝐷 на непересекающиеся множества 𝐷 = 𝑑1 ⋃ 𝑑2 ⋃ … ⋃ 𝑑𝑘 с дальнейшим применением механизма дифференциальной конфиденциальности 𝐴(𝐷) к каждому из этих множеств. После этого говорят, что результаты 𝐴(𝑑1 ), … , 𝐴(𝑑𝑘 ) удовлетворяют Ɛ - дифференциальной конфиденциальности. Важно сказать, что параллельная композиция обеспечивает лучшую приватность, так как рандомизированный механизм выполняется для каждого подмножества только один раз, что дает Ɛ - дифференциальную конфиденциальность. Последовательная же композиция же складывается из бюджетов конфиденциальности каждого механизма Ɛ1 + ⋯ + Ɛ𝑘 , а это удовлетворяет 𝑘 ∗ Ɛ – дифференциальной приватности. Примером применения параллельной композиции являются гистограммы, разбивающие набор данных на основе значения одного из атрибутов, как показано на рисунке 6. 2.3.3 Постобработка Свойство постобработки говорит о том, что если некоторый рандомизированный алгоритм 𝐴(𝐷), применяемый к набору данных 𝐷, удовлетворяет Ɛ – дифференциальной конфиденциальности, то для любой (детерминированной или рандомизированной) функции 𝑔 выполняется 𝑔(𝐴(𝐷)), которое обеспечивает Ɛ – дифференциальную приватность. Иными словами, постобработка позволяет выполнять произвольные вычисления с данными, полученными в результате применения к ним дифференциально частного механизма, не опасаясь при этом за потерю конфиденциальности. Рассматриваемое свойство применяют для повышения точности или уменьшения шума дифференциально частных алгоритмов, а также используется для гарантии ограничения Ɛ – дифференциальной конфиденциальности при

23 наличии у злоумышленника или стороннего лица вспомогательной информации, которая может содержаться в функции 𝑔. Рисунок 6 - Пример применения параллельной композиции 2.3.4 Расширенная композиция В определении 2 дифференциальной конфиденциальности указывался параметр , обозначающий вероятность возникновения ошибки при работе рандомизированного алгоритма. Для (Ɛ, ) – дифференциальной конфиденциальности существует дополнительное свойство, касающееся композиции – расширенная композиция. Оно основана на идее наличия последовательности механизмов 𝑚1 , … , 𝑚𝑘 , где каждый 𝑚𝑖 может быть получен из результатов всех предыдущих механизмов 𝑚1 , … , 𝑚𝑖−1 . Основная теорема расширенной композиции гласит, что если механизм 𝑚𝑖 является Ɛ – дифференциально конфиденциальным, то общий бюджет конфиденциальности при  ≥ 0 может быть получен как: 1 Ɛобщий = 2 ∗ Ɛ√2 ∗ 𝑘 ∗ log ( ) 

24 Композиция позволяет оценить верхние границы значения Ɛ, то есть сколько приватной информации можно потерять при нескольких запросах с разными значениями Ɛ. 2.4 Количественная оценка знаний злоумышленника Предположим, что к базе данных D применен алгоритм A, который вносит случайность. Цель злоумышленника – выяснить, находится ли определенный человек в базе данных. Рассмотрим худший случай, когда злоумышленнику известна вся база данных, однако он не знает в какой из двух баз данных D1 или D2 находится интересующий его человек. Атакующий может сделать предположение 𝑃[𝐷 = 𝐷1], которое будет означать, что его цель находится в базе данных D1 с некоторой вероятностью 𝑃 ∈ [0,1]. Точно таким же образом может быть выдвинуто подозрение, что в D2 цель злоумышленника отсутствует 𝑃[𝐷 = 𝐷2] = 1 − 𝑃[𝐷 = 𝐷1]. Предположим, что после применения A к базе данных возвращается выходное значение Out, исходя из которого атакующий может сделать новое предположение, которое определяется как 𝑃[𝐷 = 𝐷2 | 𝐴(𝐷) = 𝑂𝑢𝑡]. Применяя теорему Байеса, получаем: 𝑃[𝐷 = 𝐷2 | 𝐴(𝐷) = 𝑂𝑢𝑡] = где 𝑃[𝐷 = 𝐷2 ] ∗ 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡|𝐷 = 𝐷2 ] , 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡] 𝑃[𝐷 = 𝐷2 ] - изначальное предположение злоумышленника, 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡|𝐷 = 𝐷2 ]– вероятность получения значения Out из базы данных D2, 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡] − вероятность того, что в результате применения алгоритма A к D2 выходным значением будет Out. Если первоначальным предположением злоумышленника окажется, что нужные ему данные содержатся в D1, тогда аналогичным образом получится: 𝑃[𝐷 = 𝐷1 | 𝐴(𝐷) = 𝑂𝑢𝑡] = 𝑃[𝐷 = 𝐷1 ] ∗ 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡|𝐷 = 𝐷1 ] 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡]

25 Так как значение 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡] неизвестно, нужно произведи преобразование, чтобы эта величина сократилась, а для этого рассмотрим соотношение: 𝑃[𝐷 = 𝐷2 | 𝐴(𝐷) = 𝑂𝑢𝑡] 𝑃[𝐷 = 𝐷2] 𝑃[ 𝐴(𝐷2) = 𝑂𝑢𝑡] = ∗ 𝑃[𝐷 = 𝐷1 | 𝐴(𝐷) = 𝑂𝑢𝑡] 𝑃[𝐷 = 𝐷1] 𝑃[ 𝐴(𝐷1) = 𝑂𝑢𝑡] Применяя к 𝑃[ 𝐴(𝐷2) = 𝑂𝑢𝑡] и 𝑃[ 𝐴(𝐷1) = 𝑂𝑢𝑡] (1) определение дифференциальной конфиденциальности, получим: 𝑃[ 𝐴(𝐷2) = 𝑂𝑢𝑡] ≤ 𝑒𝑥𝑝Ɛ 𝑃[ 𝐴(𝐷1) = 𝑂𝑢𝑡] Так как при перестановке баз данных они все равно будут отличаться одной записью, выражение выше можно модифицировать: 𝑒𝑥𝑝−Ɛ ≤ 𝑃[ 𝐴(𝐷2) = 𝑂𝑢𝑡] ≤ 𝑒𝑥𝑝Ɛ 𝑃[ 𝐴(𝐷1) = 𝑂𝑢𝑡] (2) Из (1) и (2) выводим: 𝑒𝑥𝑝−Ɛ ∗ 𝑃[𝐷 = 𝐷2] 𝑃[𝐷 = 𝐷2 | 𝐴(𝐷) = 𝑂𝑢𝑡] 𝑃[𝐷 = 𝐷2] ≤ ≤ 𝑒𝑥𝑝Ɛ ∗ 𝑃[𝐷 = 𝐷1] 𝑃[𝐷 = 𝐷1 | 𝐴(𝐷) = 𝑂𝑢𝑡] 𝑃[𝐷 = 𝐷1] Заменяя 𝑃[𝐷 = 𝐷1] на 1 − 𝑃[𝐷 = 𝐷2], а также проделывая это для 𝑃[𝐷 = 𝐷1 | 𝐴(𝐷) = 𝑂𝑢𝑡], получаем неравенство вида: 𝑒𝑥𝑝Ɛ 𝑃[𝐷 = 𝐷2] ≤ 𝑃[𝐷 = 𝐷2 | 𝐴(𝐷) = 𝑂𝑢𝑡] + (1 − 𝑒𝑥𝑝Ɛ ) ∗ 𝑃[𝐷 = 𝐷2] ≤ 𝑒𝑥𝑝Ɛ ∗ 𝑃[𝐷 = 𝐷2] 1 + (𝑒𝑥𝑝Ɛ − 1) ∗ 𝑃[𝐷 = 𝐷2] Ɛ - дифференциальная конфиденциальность гарантирует, что для каждого применения алгоритма A результат приблизительно с равной вероятностью будет одновременно наблюдаться на одной из соседних баз данных [17]. Это значит, что статистические данные запросов и функций, выполняемых в базе, не должны сильно зависеть от конкретного человека. Выведенное неравенство, на основе которого был построен график на рисунке 7, показывает количественную оценку этого явления. Черная линия на графике означает, что атакующий практически не получает никакой информации, следовательно его предположения практически

26 не обновляются в силу недостатка данных. Цветные линии одинаковых цветов – это верхние и нижние границы знаний злоумышленника. Если Ɛ=0, тогда будет достигаться полная конфиденциальность людей, чья информация содержится в базе данных. При увеличении же значения знания злоумышленника о содержимом базы данных увеличивается, соответственно приватность будет уменьшаться и может снизиться до полного отсутствия. Рисунок 7 – График, отображающий количественную оценку Ɛ дифференциальной конфиденциальности 2.5 Модели дифференциальной конфиденциальности Как выяснили ранее, дифференциальная конфиденциальность добавляет шум к данным. В зависимости от того, где именно он добавляется выделяют два типа дифференциальной конфиденциальности – локальная и глобальная. 2.5.1 Глобальная модель В глобальной модели, схема работы которой представлена на рисунке 8, каждый участник доверяет службе, которая собирает информацию, поэтому данные от пользователей отправляются без добавления шума. Рандомизированный алгоритм применяется один раз, когда служба публикует результаты или отвечает на запрос, полученный от третьих лиц.

27 Рисунок 8 – Глобальная модель Преимуществом модели является точность, так как в одном месте собираются данные о разных пользователях. В связи с этим каждый отдельный пользователь «теряется в толпе», что означает, что его частные данные извлечь становится сложнее, поэтому количество шума, которое необходимо добавлять мало. Однако можно выделить и недостатки, связанные с тем, что участники должны достаточно доверять службе, потому что последняя должна корректно добавлять шум и защищать конфиденциальность пользователя. Кроме того, в глобальной модели вся информация собирается в одном месте, что увеличивает риск отказа. 2.5.2 Локальная модель В локальной модели, изображенной на рисунке 9, каждый пользователь перед предоставлением информации какой-либо службе применяет к своим данным рандомизированный алгоритм. В отличие от предыдущего типа дифференциальной конфиденциальности, служба может сразу же публиковать полученную информацию без

28 дополнительных преобразований. То есть плюсом локальной модели является то, что служба не требует доверия, так как каждый участник сам защищает свои данные. Из минусов можно выделить то, что общий шум, наложенный на информацию, становится больше, а это значит, что точность уменьшается и для получения полезных результатов потребуется гораздо больше пользователей. Рисунок 9 – Локальная модель 2.6 Чувствительность Чувствительность запроса помогает понять, насколько данные человека влияют на расчеты и, следовательно какое количество шума необходимо добавлять. Высокая чувствительность 𝑓 при фиксированном значении Ɛ служит предупреждением о том, что необходимо добавить больше шума, чтобы замаскировать данные [18]. Для дальнейшего рассмотрения чувствительностей введем определения норм L1 и L2. Определение 4: Норма L1 вектора V длины k определяется как сумма элементов вектора:

29 𝑘 ||𝑉||1 = ∑ |Vi | 𝑖=1 Определение 5: Норма L2 вектора V длины k определяется как квадратный корень из суммы квадратов: 𝑘 ||𝑉||2 = √∑ Vi2 𝑖=1 Существует глобальная чувствительность и локальная. 2.6.1 Глобальная чувствительность Определение 6: Глобальная чувствительность характеризуется максимальной разницей выходных данных, к которой может привести функция запроса 𝑓 при внесении одного изменения в любой из всех возможных наборов данных, отличающихся не более чем одним элементом. 𝑓𝐺𝑆 = max ||𝑓(𝐷1) − 𝑓(𝐷2)||1 , 𝐷1,𝐷2:𝑑(𝐷1,𝐷2)=1 где ||. ||1 – расстояние 𝐿1 – нормы между наборами данных, отличающихся не более, чем на один элемент [19]. Важно отметить, что глобальная чувствительность — это максимальная разница в выходных данных с учетом всех возможных наборов данных, и поэтому она зависит только от запроса, а не от набора данных. Эта мера чувствительности называется «глобальной», потому что она не зависит от фактического запрашиваемого набора данных, она верна для любого выбора соседних D1 и D2 [20]. 2.6.2 Локальная чувствительность Локальная чувствительность характеризуется максимальной разницей выходных данных, к которой может привести функция запроса 𝑓 при внесении одного изменения в локальный набор данных D1:

30 𝑓𝐿𝑆 = max||𝑓(𝐷1) − 𝑓(𝐷2)||1 𝐷2 Локальная чувствительность является функцией как запроса 𝑓, так и фактического набора данных 𝐷1 . В отличие от случая глобальной чувствительности, нельзя говорить о локальной чувствительности функции, не учитывая также набор данных, в котором возникает эта локальная чувствительность, а значит, что известен и размер набора. Следовательно, есть возможность устанавливать конечные границы чувствительности некоторых функций. Идея, лежащая в основе локальной чувствительности, заключается в том, чтобы зафиксировать один из двух наборов данных как фактический запрашиваемый набор данных и учесть всех его соседей. Глобальная чувствительность учитывает любые два соседних набора данных. Таким образом, локальная чувствительность — это минимальная чувствительность, необходимая для того, чтобы запрос охватил один конкретный набор данных, а глобальная — это минимальная чувствительность, необходимая для того, чтобы запрос охватил все возможные наборы данных. 2.7 Механизмы добавления шума Как было сказано ранее, дифференциальная конфиденциальность обеспечивает приватность данных путем внесения случайности или шума. Количество добавляемого шума зависит от четырех параметров: − типа шума (Лапласа, Гаусса или экспоненциальный); − чувствительности запроса или функции; − желаемого Ɛ; − желаемого δ. Рассмотрим каждый из дифференциально частных механизмов добавления шума.

31 2.7.1 Механизм Лапласа Механизм Лапласа используют для выполнения числовых запросов к базе данных. Эти запросы отображают базы данных на множество действительных чисел: 𝑓: 𝐷 → 𝑅 или 𝑓: 𝐷 → 𝑅𝑘 , где 𝑅𝑘 – вектор действительных чисел длины k. Для определения механизма Лапласа требуется ввести следующее определение. Определение 7: Распределением Лапласа (с центром в точке 0) называется непрерывное распределение случайной величины с функцией плотности вероятности [21]: 𝐿𝑎𝑝(𝑓(𝐷)|𝑏) = |𝑓(𝐷)| 1 ∗ exp (− ), 2∗𝑏 𝑏 где b – параметр масштаба, который определяет статистическую дисперсию распределения вероятностей или, иначе говоря, величина показывает, на сколько распределение «плоское». Определение 8: Механизм Лапласа заключается в добавлении шума – значений распределения Лапласа к истинному ответу на запрос 𝑓(𝐷): 𝐴(𝐷) = 𝑓(𝐷) + 𝐿𝑎𝑝(𝑏), причем параметр 𝑏 = 𝑓 Ɛ , где 𝑓 – чувствительность запроса, которая показывает сколько нужно добавлять шума к данным, чтобы они были конфиденциальные. Чем больше чувствительность, тем больше шума необходимо добавлять, чтобы обеспечить конфиденциальность информации. Механизм Лапласа конфиденциальность, так обеспечивает как из определений конфиденциальности и механизма Лапласа следует, что: ε-дифференциальную дифференциальной

32 |𝑓(𝐷)−𝑂𝑢𝑡| (− ) 1 𝑏 |𝑓(𝐷)−𝑂𝑢𝑡| |𝑓(𝐷`)−𝑂𝑢𝑡| ∗ 𝑒𝑥𝑝 𝑃[ 𝐴(𝐷) = 𝑂𝑢𝑡] ( + ) 𝑏 𝑏 = 2∗𝑏 = 𝑒𝑥𝑝 |𝑓(𝐷`)−𝑂𝑢𝑡| 𝑃[ 𝐴(𝐷`) = 𝑂𝑢𝑡] (− ) 1 𝑏 ∗ 𝑒𝑥𝑝 2∗𝑏 = 𝑒𝑥𝑝 ≤ Ɛ∗(|𝑓(𝐷`)−𝑂𝑢𝑡|−|𝑓(𝐷)−𝑂𝑢𝑡|) ( ) 𝑓 Ɛ∗|𝑓(𝐷`)−𝑓(𝐷)| ( ) 𝑓 𝑒𝑥𝑝 = 𝑒𝑥𝑝 ( Ɛ∗||𝑓(𝐷`)−𝑓(𝐷)||1 ) 𝑓 ≤ 𝑒𝑥𝑝Ɛ Относительная ошибка вычисляется как разница между истинным результатом запроса и тем, что получился в результате зашумления: 𝑒𝑟𝑟𝑜𝑟 = 𝑣𝑎𝑙𝑢𝑒𝑟𝑒𝑎𝑙 − 𝑣𝑎𝑙𝑢𝑒𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑡𝑖𝑎𝑙 𝑝𝑟𝑖𝑣𝑎𝑐𝑦 Эта величина зависит от значения параметра Ɛ в механизме Лапласа и отражает точность результата. Для Ɛ = 0,1 относительная ошибка примерно в 10 раз больше, чем для Ɛ = 1,1, что говорит о том, что ошибка обратно пропорциональна Ɛ. Чем выше бюджет конфиденциальности, тем меньше ошибка, и наоборот. Это отражают гистограммы на рисунках 10 и 11, которые были построены по запросу, который вычисляет число людей в наборе данных, кто никогда не был в браке, зашумленному механизмом Лапласа для Ɛ = 0,1 и Ɛ = 1,1 соответственно. При малых значениях Ɛ чувствительности, равной 1, параметр 𝑏 = 𝑓 Ɛ = 1 Ɛ будет большим, а шум, который будет наложен на результат запроса – нулевым. График плотности вероятности механизма Лапласа для запроса, ответ которого равен 500, изображенный на рисунке 12, показывает, что, чем меньше значение Ɛ, тем более конфиденциальны данные. Красная гистограмма отображает значения ответа при Ɛ = 10, серая – при Ɛ = 1, зеленая – при Ɛ = 0,3.

33 Рисунок 10– Гистограмма относительной ошибки для Ɛ = 0,1 Рисунок 11 – Гистограмма относительной ошибки для Ɛ = 1,1 Рисунок 12 – Плотность вероятности для механизма Лапласа

34 2.7.2 Механизм Гаусса В определении 2 был указан параметр , который обозначает вероятность нарушения корректной работы дифференциально частного механизма. То есть с вероятностью  дифференциальная конфиденциальность будет нарушена, и с вероятностью 1 −  последняя будет установлена, а именно будет соблюдаться: 𝑃[ 𝐴(𝐷2) = 𝑂𝑢𝑡] ≤ 𝑒𝑥𝑝Ɛ 𝑃[ 𝐴(𝐷1) = 𝑂𝑢𝑡] Механизмом, в котором наблюдается (Ɛ, ) – дифференциальная конфиденциальность, является механизм Гаусса. Определение 8: Механизм Гаусса заключается в добавлении шума – значений нормального распределения к истинному ответу на запрос 𝑓(𝐷) [22]: 𝐴(𝐷) = 𝑓(𝐷) + 𝒩(𝜎 2 ), где 𝜎 2 = 2 ∗ 𝑓 2 ∗ log 1.25  Ɛ2 Механизм схож с механизмом Лапласа, однако по сравнению с последним, при использовании механизма Гаусса вероятность получения результата, который не является истинным, выше, так как распределение более пологое, что показано на рисунке 13. Это говорит о том, что вероятность получения точных данных при использовании механизма Гаусса меньше. Рисунок 13 – Сравнение функций плотности вероятности механизмов Гаусса и Лапласа для Ɛ = 0.1,  = 10−5

35 Несмотря на такие недостатки как меньшая точность и вероятность  нарушения дифференциальной конфиденциальности, механизм Гаусса по сравнению с механизмом Лапласа позволяет добавлять к данным гораздо меньше шума, так как может использовать чувствительность с нормой L2, которая меньше чувствительности с нормой L1 [1]. Предположим, что есть набор данных, в котором содержится информация о пациентах и специализация врача, которого данный пациент посещал. Каждая запись соответствует одному человеку. К набору данных 𝐷 выполняется запрос 𝑓(𝐷), подсчитывающий число пациентов по каждой из специальностей врачей. Наглядно это можно изобразить на рисунке 14. Пусть число специалистов будет равняться 20. Важно сказать, что пациент может обратиться к нескольким врачам, однако если он посетит «терапевта» 5 раз, то количество пациентов «терапевта» увеличится на 1. Чтобы обеспечить дифференциальную приватность информации необходимо добавить шум в соответствии с чувствительностью. Рисунок 14 – Наглядное изображения выполнения запросов по каждому врачу Чувствительность измеряет, насколько ее вывод может измениться при добавлении одной записи в базу данных. Как было сказано ранее, пациент изменяет статистику лишь на 1, значит по определению чувствительности из раздела 2.5 данной выпускной квалификационной работы, для механизма Лапласа получаем следующее значение чувствительности:

36 20 1 𝑓 = max 𝐷1,𝐷2:𝑑(𝐷1,𝐷2)=1 ∑|𝑓(𝐷1) − 𝑓(𝐷2)| = 20 𝑖=1 Для механизма Гаусса это значение будет равняться: 20 2 𝑓 = 20 √∑|𝑓(𝐷1) − 𝑓(𝐷2)|2 = √∑ 12 = √20 ≈ 4.47 max 𝐷1,𝐷2:𝑑(𝐷1,𝐷2)=1 𝑖=1 𝑖=1 Полученные результаты говорят о том, что в соответствии с меньшим значением чувствительности, механизм Гаусса добавляет к данным меньше шума, что хорошо, так как нам нужно обеспечить конфиденциальность информации, при этом сохраняя как можно большую точность. Механизм Гаусса отлично подходит для обеспечения дифференциальной конфиденциальности при выполнении запросов к набору данных, где один человек оказывает влияние на множество величин. В противном случае, когда пользователь меняет только одно значение, лучше использовать метод Лапласа. 2.7.3 Экспоненциальный механизм Экспоненциальный механизм используется для обеспечения дифференциальной конфиденциальности, когда выходные данные не являются числовыми. Механизм был разработан для обстоятельств, в которых было желательно выбрать наилучший ответ [23]. Пусть 𝐷, как и раньше, обозначает входной набор данных, а 𝑟 ∈ 𝑅 обозначает один из потенциальных ответов на запрос, учитывая функцию оценки 𝑢: 𝐷 × 𝑅 → ℝ, случайный алгоритм 𝐴 удовлетворяет ε-дифференциальной конфиденциальности, если выбирает ответ на основе вероятности: 𝐴(𝐷, 𝑢) = {𝑟|𝑃[𝑟 ∈ 𝑅] = 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷,𝑟) 2𝑢 }, где 𝑢 означает чувствительность функции оценки и определяется как: 𝑢 = max max 𝑟∈ℝ 𝐷1,𝐷2:||𝐷1−𝐷2|| ≤1 1 |𝑢(𝐷1, 𝑟) − 𝑢(𝐷2, 𝑟)| Цель механизма состоит в том, чтобы случайным образом сопоставить набор данных 𝐷 с некоторым выходом в диапазоне 𝑅, в результате чего любой

37 паре (𝑑, 𝑟) присваивается оценка [24]. Максимальное значение этой оценки и будет результатом опроса. К примеру, некая компания хочет установить цену на выпускаемое программное обеспечение. Чтобы сделать это, они проводят опрос потенциальных покупателей, спрашивая цену, которую те готовы заплатить. При этом людям обещают, что названные каждым из них, не будут разглашены, опубликуется лишь дифференциально конфиденциальное значение оптимальной стоимости. Однако, если руководствоваться механизмами Лапласа или Гаусса, к цене необходимо будет добавить шум для обеспечения дифференциальной приватности, что изменит значение цены и может оказаться таковым, что люди не захотят столько платить, а это приведет к нулевым продажам. Экспоненциальный механизм решает эту проблему. Учитывая параметр конфиденциальности Ɛ, набор результатов 𝑅 и функцию оценки 𝑢, которая сопоставляет пары - (база данных, потенциальный результат) с оценкой, механизм выбирает один элемент из 𝑅 на основе распределения вероятностей, указанного выше. Вышеизложенный пример представлен на рисунке 15. Рисунок 15 – Принцип работы экспоненциального механизма При этом экспоненциальный дифференциальную конфиденциальность: механизм обеспечивает Ɛ -

38 Ɛ∗𝑢(𝐷1,𝑟) 2𝑢 ( Ɛ∗𝑢(𝐷1,𝑟`) ) ∑𝑟`∈𝑅 𝑒𝑥𝑝 2𝑢 𝑒𝑥𝑝 𝑃[ 𝐴(𝐷1, 𝑢) = 𝑟] = 𝑃[ 𝐴(𝐷2, 𝑢) = 𝑟] =( Ɛ∗𝑢(𝐷2,𝑟) 2𝑢 ( Ɛ∗𝑢(𝐷2,𝑟`) ) ∑𝑟`∈𝑅 𝑒𝑥𝑝 2𝑢 𝑒𝑥𝑝 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷1,𝑟) 2𝑢 Ɛ∗𝑢(𝐷2,𝑟) 𝑒𝑥𝑝 2𝑢 )∗( ∑𝑟`∈𝑅 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷1,𝑟`) ∑𝑟`∈𝑅 𝑒𝑥𝑝 2𝑢 = Ɛ∗(𝑢(𝐷1,𝑟)−𝑢(𝐷2,𝑟)) 2𝑢 𝑒𝑥𝑝 ≤ Ɛ 2 𝑒𝑥𝑝 ∗ Ɛ 2 𝑒𝑥𝑝 ∗( Ɛ∗𝑢(𝐷2,𝑟`) 2𝑢 ∗( ∑𝑟`∈𝑅 𝑒𝑥𝑝 ) Ɛ∗𝑢(𝐷2,𝑟`) 2𝑢 Ɛ∗𝑢(𝐷1,𝑟`) ∑𝑟`∈𝑅 𝑒𝑥𝑝 2𝑢 ∑𝑟`∈𝑅 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷1,𝑟`) 2𝑢 Ɛ∗𝑢(𝐷1,𝑟`) ∑𝑟`∈𝑅 𝑒𝑥𝑝 2𝑢 ) ) = 𝑒𝑥𝑝Ɛ *** Таким образом, в этой части работы были даны основные определения, играющие важную роль для обеспечения дифференциальной приватности алгоритмов. Также было рассмотрено формальное определение понятия дифференциальная конфиденциальность, его основные свойства, механизмы и особенности их применения. Кроме прочего был произведен анализ подсчета бюджета конфиденциальности Ɛ, который количественную оценку знаний злоумышленника. позволяет произвести

39 3. РАЗРАБОТКА ЛАБОРАТОРНЫХ РАБОТ ДЛЯ СПЕЦИАЛИСТОВ ПО ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ В этой части будет описана практическая часть выпускной квалификационной работы, которая посвящена созданию лабораторных работ по обеспечению дифференциальной конфиденциальности для студентов, обучающихся на направлении информационной безопасности. 3.1 Разработка структуры и тем лабораторных работ В качестве тем для лабораторных работ были выбраны основные механизмы обеспечения дифференциальной конфиденциальности, которые в настоящее время используются известными компаниями для сохранения приватности информации пользователей. Среди таких механизмов можно выделить: − механизм рандомизированного ответа, который применяется технологией RAPPOR компании Google для сбора статистических данных о населении, путем исследования запросов пользователей в поисковой строке [25]; − механизм Лапласа, используемый в системе PrivTree от Microsoft для маскировки местоположения людей в базах данных геолокации [26]; − механизм Гаусса, зачастую применяемый в сферах здравоохранения для конфиденциальности данных пациентов [27]; − экспоненциальный механизм, из которого вышеупомянутые методы могут быть получены [21]. Изучаемые алгоритмы обеспечения дифференциальной конфиденциальности позволят студентам освоить актуальную на сегодняшний день базу, которую в дальнейшем можно будет расширять, углубляясь в тему обеспечения приватности данных. Структура каждой лабораторной работы представляет собой 2 части теоретическую и практическую. Теоретическая часть составляет приблизительно 40% и включает в себя контрольные вопросы, ответы на которые можно дать, основываясь на содержащемся в лабораторной работе теоретическом материале,

40 а также упражнения, решение которых требует от студента не только понимание предоставленной информации, но и более глубокую оценку механизмов и свойств дифференциальной конфиденциальности. Упражнения включают в себя задачи на доказательство приватности, анализ и интерпретацию полученных результатов, а также в некоторых работах учащийся может представить себя в роли специалиста по дифференциальной приватности для обеспечения конфиденциальности набора данных и оценки степени его защищенности. Практическая часть составляет 60% лабораторной работы. Она представляет собой реализацию механизмов и свойств дифференциальной приватности для выданного набора данных. От студента требуется также произвести анализ разработанных методов, а также продумать и реализовать способы их улучшения. Помимо прочего в этой части необходимо строить графики, гистограммы и сравнительные таблицы, основываясь на результатах, полученных после реализации запросов к набору данных, защищенному с помощью механизмов дифференциальной конфиденциальности. Вышеописанная структура позволяет познакомить специалиста по информационной безопасности не только с основами рассматриваемого в выпускной работе метода обеспечения анонимности данных, но и закрепить полученные знания на практике посредствам проведения различного анализа и решения некоторого множества задач. 3.2 Инструменты реализации Лабораторные работы, реализованные в рамках данной выпускной квалификационной работы, разработаны в интерактивном веб-приложении Jupyter Notebook [28], которое обеспечивает удобство и наглядность разработки. Его преимущества перед составлением лабораторных работ лишь в Microsoft Word отражены в таблице 2. Использование скриптов также не является удобным, так как они не наглядны и могут лишь запутать студента.

41 Таблица 2 – Преимущества составления лабораторных работ с поддержкой Jupyter Notebook помимо Microsoft Word Критерии Jupyter Notebook Microsoft Word сравнения Содержимое Содержат меньше Возможны опечатки в предоставляемых опечаток, а также намного примерах, плюс ко всему для шаблонов кода легче в запуске кода. запуска кода необходимо его скопировать и, возможно, изменить внешний вид для корректности отступов и прочего. Наглядность Подсвечивание частей кода Весь код одного цвета, что программной различными цветами делает его осмысление более составляющей обеспечивает более сложным. наглядную картину для понимания логики программы. Проверочные Меньшая вероятность Могут также содержать тесты опечаток, уже имеет опечатки или иметь корректный синтаксис. некорректный синтаксис, что запутает учащегося. Отправная точка Студентам будет сразу Среда выполнения кода не понятно, где и что делать, так очевидна, поэтому без траты дополнительного отнимет у учащегося время времени на поиск среды на ее поиски. реализации. Входные наборы Веб-приложение реализует данных удобную обработку наборов данных и имеет множество документации на эту тему. Составление Обеспечивает удобство в графиков создании графиков, гистограмм, таблиц, схем. Таким образом, Jupyter Notebook позволяет совместить все необходимые составляющие – код, текст, изображения и графики в одном месте, благодаря чему обеспечить комфортную среду выполнения лабораторных работ. Языком программирования, используемым для выполнения заданий, является Python. Этот выбор объясняется тем, что последний позволяет

42 подключать огромное количество библиотек, содержит большое число документации, а также является довольно простым и понятным языком. 3.3 Состав лабораторных работ Каждая лабораторная работа посвящена отдельной теме, касающейся дифференциальной конфиденциальности, и содержит 7 вариантов для выполнения. Состав лабораторных работ, который предоставляется студентам, выглядит следующим образом: 1. Блокнот Jupyter Notebook, который содержит: − название лабораторной работы; − цель лабораторной работы; − теоретические сведения, которые содержат информацию, необходимую для выполнения практических задач; − задания на работу по вариантам, где описывается последовательность задач, а также макет кода, графики, проверочные тесты по вариантам и пояснения, нужные для облегчения и большего понимания требований от студента; − шаблоны, содержащие комментарий «#ВАШ КОД», для выполнения студентом программной части задания. 2. Документ формата .docx с дублированием названия, цели, теоретической информации и заданий, однако, помимо этого, включающий в себя: − включают упражнения для более глубокого понимания материала. Они в себя задачи, касающиеся математического аппарата дифференциальной конфиденциальности; вопросы, поясняющие полученные в ходе работы результаты; головоломки на проверку студента в роли аналитика по дифференциальной конфиденциальности; − контрольные вопросы, касающиеся базовых основ, ответы на которые можно найти в теоретической части;

43 − содержание отчета с требованиями для учащихся. 3. Раздаточный материал формата .csv с указанием вариантов, который содержит наборы данных, анализируемые в ходе выполнения лабораторных работ. Для преподавателя дополнительно предоставляются: 1. Блокнот Jupyter Notebook, который содержит требуемые реализации задач. 2. Документ формата .docx, в состав которого плюсом прилагаются решения упражнений и ответы на контрольные вопросы. 3.3.1 Работа 1 – Механизм рандомизированного ответа Целью работы является изучение механизма рандомизированного ответа и анализ результатов в зависимости от набора данных. Рандомизированный ответ — это механизм локальной дифференциальной конфиденциальности, который изначально предназначался для улучшения предвзятости ответов на «тонкие» вопросы. Например, рассмотрим ситуацию, когда необходимо узнать зарплату сотрудников некоторой компании. Если напрямую спросить людей, то велика вероятность, что большинство не захотят сообщать запрошенную информацию, так как она относится к частной жизни. Выход из данной ситуации заключается в том, что каждый сотрудник прибавляет к своей заработной плате S случайное число R, находящееся в промежутке от 10000 до 10000, и сообщает в ответ на запрос лишь полученную в результате сумму 𝑆𝑢𝑚𝑚 = 𝑆 + 𝑅. Так как 𝑆𝑢𝑚𝑚 не выдает истинную зарплату человека, то можно сказать, что персональные данные были защищены. То есть для того, чтобы обеспечить конфиденциальность данных, полученных от некоторых лиц, дифференциальная конфиденциальность добавляет к исходной информации статистический шум, как показано на рисунке 16. Однако, в таком случае, необходимо найти баланс между сохранением конфиденциальности данных и информативностью, так как после внесения случайности снизилась информативность данных. Для этого используется закон

44 простых чисел, благодаря которому по мере роста размера выборки ее среднее значение приближается к среднему, то есть шум устраняется и полученное среднее значение становится близко к истинному среднему числу. И чем больше выборка, тем больше будет приближение. Рисунок 16 – Механизм работы дифференциальной конфиденциальности Идея алгоритма состоит в том, что человек отвечает на вопрос в соответствии с результатом подбрасывания двух монет, как представлено на рисунке 17. Это вносит некую неопределенность, которая и обеспечивает конфиденциальность информации. Алгоритм позволяет ввести степень правдоподобного отрицания, так как аналитик данных уже не может быть уверен в истинности ответа определенного человека. Однако, в то же время, достаточно информативен, чтобы позволить сделать какие-то выводы. Рисунок 17 – Алгоритм рандомизированного ответа

45 В соответствии с номером варианта учащемуся предоставляется набор данных, как представлено в таблице 3, который содержит список людей с их личной информацией (идентификатор человека, имя, дата рождения, возраст, образование, профессия, семейное положение, пол, страна проживания, зарплата и др.). Пример набора данных представлен на рисунке 18. Таблица 3 – Наборы данных в соответствии с вариантом студента Вариант Имя набора данных Размер набора данных (КБ) 1 data_for_lab1_var1.csv 4808 data_for_lab1_var1_100.csv 15 data_for_lab1_var1_1000.csv 150 data_for_lab1_var1_10000.csv 1492 2 data_for_lab1_var2.csv 4813 data_for_lab1_var2_100.csv 15 data_for_lab1_var2_1000.csv 150 data_for_lab1_var2_10000.csv 1492 3 data_for_lab1_var3.csv 4823 data_for_lab1_var3_100.csv 15 data_for_lab1_var3_1000.csv 150 data_for_lab1_var3_10000.csv 1492 4 data_for_lab1_var4.csv 4834 data_for_lab1_var4_100.csv 15 data_for_lab1_var4_1000.csv 150 data_for_lab1_var4_10000.csv 1492 5 data_for_lab1_var5.csv 4838 data_for_lab1_var5_100.csv 15 data_for_lab1_var5_1000.csv 150 data_for_lab1_var5_10000.csv 1492 6 data_for_lab1_var6.csv 4853 data_for_lab1_var6_100.csv 15 data_for_lab1_var6_1000.csv 150 data_for_lab1_var6_10000.csv 1492 7 data_for_lab1_var7.csv 4856 data_for_lab1_var7_100.csv 15 data_for_lab1_var7_1000.csv 150 data_for_lab1_var7_10000.csv 1492 Основными задачами лабораторной работы являются: 1. Осуществление запроса к набору данных data_for_lab1_varX.csv без использования рандомизированного алгоритма, значение которого будет считаться истинным ответом.

46 2. Применение алгоритма рандомизированного ответа к предоставленному набору данных. 3. Выполнение рандомизированного запроса к алгоритма, набору значение данных которого с использования будет считаться дифференциально частным ответом. 4. Вычисление относительной ошибки при применении механизма рандомизированного ответа. 5. наборов Сравнение результатов ошибок при использовании предоставляемых данных различных размеров – data_lab1_varX_100.csv, data_lab1_varX_1000.csv, data_lab1_varX_10000.csv. 6. Выполнение упражнений: 1) докажите, что механизм рандомизированного ответа является дифференциально частным; 2) механизм рандомизированного ответа является локальной моделью дифференциальной конфиденциальности. Объясните, в каких случаях следует использовать локальную модель, а в каких глобальную. Рисунок 18 – Набор данных для варианта 1

47 При выполнении работы результаты относительных ошибок для различных вариантов будут выглядеть приблизительно так, как представлено в таблице 4. Эти значения показывают, что механизм рандомизированного ответа хорошо выполняет свою задачу для большой базы данных, так как в этом случае по закону больших чисел выходные значения принимают приблизительно истинное значение, что обеспечивает приватность, и в то же самое время гарантирует точность результата. В случае маленького содержания строк в наборе, ответы на запросы перестают быть точными, из-за чего информативность содержимого теряется. Таблица 4 – Приблизительные выходные значения при реализации лабораторной работы 1 Вариант 1 2 3 4 5 6 7 Относительная ошибка (в %) в наборах данных, содержащих: 32219 строк 100 строк 1000 строк 10000 строк 1,888 99,665 98,447 65,997 5,242 99,880 98,609 65,873 4,849 99,666 97,435 69,276 0,479 99,773 98,241 66,418 0,399 99,987 98,029 70,439 1,369 100 98,139 70,395 3,662 99,668 98,461 71,921 3.3.2 Работа 2 – Механизм Лапласа В этой работе производится конфиденциальность которого анализ исходного набора данных, обеспечивается с помощью применения механизма Лапласа. В отличие от механизма рандомизированного ответа механизм Лапласа позволяет оценивать количество генерируемого шума для обеспечения дифференциальной конфиденциальности. Также среди плюсов этого алгоритма можно отметить то, что он является более точным. В качестве исходных данных используется информация из Национального отделения неотложной помощи, содержащая сведения об употреблении пациентами зловредных препаратов [29]. На рисунке 19 представлены первоначальные материалы.

48 Далее с помощью функции, представленной ниже производится генерация датасета, изображенный на рисунке 20, с которым проводится дальнейшая работа. Он содержит информацию о 100 людях и препаратах, которые они принимали. """Вход: data - фрейм данных, содержащий препарат и вероятность того, что пациент его использовал. N - количество людей, которых нужно сгенерировать. r - случайное значение. Выход: DATA - фрейм данных, содержащий N строк, где каждая строка соответствует человеку, 1 в столбце означает, что человек использовал лекарство.""" def DatasetModeling(data, N, r = None): df = {} for index_num, row in data.iterrows(): name = row['Substance'] probability = row['Probability'] df_row = bernoulli.rvs(probability, size=N, random_state = np.random.RandomState(seed=r)) f[name] = df_row DATA = pd.DataFrame(df) return DATA Рисунок 19 – Содержимое набора данных для выполнения лабораторной работы 2

49 Рисунок 20 – Сгенерированный набор данных В лабораторной работе необходимо проанализировать среднее значение θ = 𝐸[𝑋] по полученному материалу дифференцированно частным образом. Основываясь на том, как были сгенерированы данные, истинное среднее значение распределения, из которого были взяты выборки, — это исходные вероятности из набора данных Национального отделения неотложной помощи, которое вычисляется как: TRUE_MEAN = data['Probability'].to_numpy() Затем требуется реализовать и сравнить результаты трех алгоритмов. Алгоритм 1 – Не конфиденциальный Алгоритм не является дифференциально конфиденциальным. Оценивать среднее значение необходимо путем определения среднего значения выборок 𝐷𝑖 : 𝑁 1 𝜃̅ = 𝐴(𝐷) = 𝑓(𝐷) = ∑ 𝐷𝑖 𝑁 𝑖=1 Алгоритм 2 – Механизм Лапласа Механизм Лапласа, который добавляет шум 𝜀𝑒 к истинному ответу на запрос 𝑓(𝐷) как: 𝑁 1 𝜃̅ = 𝐴(𝐷) = 𝑓(𝐷) + 𝜀𝑒 = ( ∑ 𝐷𝑖 ) + 𝜀𝑒 𝑁 𝑖=1 𝜀𝑒 ∈ 𝑅𝑑 представляет собой независимые координаты, каждая из которых распределена в соответствии с параметром масштаба определяется как: ∆𝑓 𝑒 . Чувствительность ∆𝑓

50 𝑁 𝑁 𝑖=1 𝑖=1 1 1 𝑓 = max max ||𝑓(𝐷1 ) − 𝑓(𝐷2 ) ||1 = || ∑ 𝐷1 𝑖 − ∑ 𝐷2 𝑖 || 𝐷1 ,𝐷2 :𝑑(𝐷1 ,𝐷2 )=1 𝐷1 ,𝐷2 :𝑑(𝐷1 ,𝐷2 )=1 𝑁 𝑁 = 1 𝑑 𝑁 где ||. ||1 – расстояние 𝐿1 – нормы. Алгоритм 3 – Локально дифференциально конфиденциальный механизм Лапласа В отличие от алгоритма 2 в данном алгоритме шум 𝜀𝑒 добавляется не к агрегированному значению 𝑓(𝐷), а к каждому 𝐷𝑖 по отдельности: 𝑁 1 𝜃̅ = 𝐴(𝐷) = 𝑓(𝐷 + 𝜀𝑒 ) = ∑(𝐷𝑖 + 𝜀𝑒𝑖 ) 𝑁 𝑖=1 Здесь 𝜀𝑒 ∈ 𝑅𝑑×𝑁 делает каждую строку в данных дифференциально конфиденциальной еще до того, как будет получен ответ на запрос 𝑓(𝐷). Для каждой строки 𝐷𝑖 , 𝜀𝑒𝑖 ∈ 𝑅𝑑 имеет независимые координаты, каждая из которых распределена в соответствии с распределением Лапласа с параметром масштаба ∆𝐷𝑖 𝑒 . Чувствительность ∆𝐷𝑖 изменения одной строки 𝐷𝑖 базы данных определяется как: ∆𝐷𝑖 = max ||𝐷1 − 𝐷2 ||1 𝐷1 ≠𝐷2 =𝑑 где ||. ||1 – расстояние 𝐿1 – нормы. Сравнение алгоритмов происходит путем оценки относительной ошибки каждого из них. Столбцы Alg1_error, Alg2_error, Alg3_error на рисунке 21 отражают разницу между значениями, полученными при выполнении алгоритмов, и настоящей величиной. Среди трех алгоритмов только алгоритмы 2 и 3 обеспечивают дифференциальную конфиденциальность. Наихудшая оценка наблюдается у алгоритма 3, так как ошибка в значениях больше двух предыдущих алгоритмов, что говорит о меньшей точности. Это связано с тем, что шум накладывается на каждую строку. Количество шума в

51 алгоритме 2 меньше за счет того, что значения «теряются в толпе», благодаря чему количество накладываемого шума уменьшается, и полезность данных остается на высоком уровне. Алгоритм 3 может быть использован в случаях, когда человек не доверяет какой-либо службе, ответственной за обеспечение конфиденциальности, и накладывает на свои данные шум самостоятельно. Причинами недоверия могут быть как сомнения в качестве добавляемого шума или в человеке, отвечающем за наложение шума, так и опасение за то, что служба может быть взломана или атакована злоумышленником, из-за чего данные, собираемые последней, будут узнаны третьими лицами. Рисунок 21 – Пример результатов выполненной лабораторной работы 2 3.3.3 Работа 3 – Механизм Гаусса и свойства дифференциальной конфиденциальности Основная цель – изучение метода Гаусса и анализ основных свойств Ɛ и (Ɛ, ) – дифференциальной конфиденциальности.

52 В данной лабораторной работе сначала требуется посчитать общее значение последовательной и расширенной композиции и сравнить полученные результаты. График, построенный в ходе выполнения этих задач, будет принимать вид, представленный на рисунке 22. Рисунок 22 – Сравнение последовательной и расширенной композиций Из вышеприведенного графика следует вывод о том, что при большом количестве испытаний (запросов) расширенная композиция обеспечивает более высокий уровень конфиденциальности, однако в случае малого числа запросов (в данном случае примерное менее 95) стоит отдать предпочтение последовательной композиции. Оба графика выдают верные значения. Однако их результаты разные. Это происходит в силу того, что теорема о композиции задает верхнюю границу потери приватности, а не четкий уровень, т. е. на самом деле, бюджет конфиденциальности может быть и ниже этого максимума, но никак не выше. Теоремы о композиции используются в случаях множественных запросов. Для обеспечения конфиденциальности необходимо наложить шум на результаты запросов. Поэтому следующим шагом лабораторной работы требуется реализовать векторный механизм Гаусса на основе примера реализации векторного механизма Лапласа, код которого выглядит следующим образом: #Векторный механизм Лапласа def LaplaceMechVec(vector, sensitivity, epsilon):

53 return [vec + np.random.laplace(loc=0, epsilon) for vec in vector] scale=sensitivity # Выполнение проверки vector = [1,2,3,4,5,6,7,8,9,10] RES = [LaplaceMechVec(vector, 8, 1.0) for _ in range(200)] for i, vec in enumerate(vector): s = [np.random.laplace(loc=vec, scale=8/1.0) for range(200)] _ / in К предоставленным в раздаточных материалах запросам Query1, Query2, Query3 для гарантии приватности полученных ответов, необходимо применить реализованный векторный механизм Гаусса для, а также механизм Лапласа, код которого указан выше, и написать функцию подсчета ошибок. Для удобства и наглядности последнюю требовалось изобразить в виде гистограммы, пример которой изображен на рисунке 23. Рисунок 23 – График подсчета ошибок для результатов дифференциально защищенных механизмов Лапласа и Гаусса Значения ошибок при использовании механизма Гаусса для обеспечения дифференциальной конфиденциальности нескольких запросов имеют меньшие значения, нежели в результате применения механизма Лапласа. Однако стоит учитывать, что механизм Гаусса работает лучше далеко не всегда. Он отлично подходит для обеспечения дифференциальной конфиденциальности при выполнении запросов к набору данных, где один человек оказывает влияние на множество величин. В противном случае, когда пользователь меняет только одно

54 значение, лучше использовать метод Лапласа. Также всегда стоит учитывать значение параметра , так как при больших значениях приватность данных может быть нарушена вовсе. 3.3.4 Работа 4 – Экспоненциальный механизм Механизмы Лапласа и Гаусса, которые были рассмотрены в предыдущих лабораторных работах, сосредоточены на численных ответах и добавляют шум непосредственно к самому ответу. Если нужно получить точный ответ, который не содержит дополнительного шума, но при этом сохраняет дифференциальную конфиденциальность, используют экспоненциальный механизм. Последний позволяет выбрать "лучший" элемент из набора. Аналитик определяет, какой элемент является "лучшим", указывая функцию оценки, которая выводит оценку для каждого элемента в наборе данных. Например, предположим, что некая компания хочет установить цену на выпускаемое программное обеспечение. Чтобы сделать это, они проводят опрос потенциальных покупателей, спрашивая цену, которую те готовы заплатить. При этом людям обещают, что названные каждым из них, не будут разглашены, опубликуется лишь дифференциально конфиденциальное значение оптимальной стоимости. Однако, если руководствоваться механизмами Лапласа или Гаусса, к цене необходимо будет добавить шум для обеспечения дифференциальной приватности, что изменит значение цены и может оказаться таковым, что люди не захотят столько платить, а это приведет к нулевым продажам. Экспоненциальный механизм решает эту проблему. Учитывая параметр конфиденциальности Ɛ, набор результатов 𝑅 и функцию оценки 𝑢: 𝐷 × 𝑅 → ℝ с чувствительностью 𝑢, которая сопоставляет пары - (база данных, потенциальный результат) с оценкой, механизм выбирает один элемент 𝑟 ∈ 𝑅 с вероятностью: 𝑃[𝑟 ∈ 𝑅] = 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷,𝑟) 2𝑢 Самое большое практическое различие между экспоненциальным механизмом и механизмами Лапласа и Гаусса заключается в том, что выход экспоненциального механизма всегда является членом множества 𝑅.

55 Алгоритм 1 – Экспоненциальный механизм для конечного множества 1. Вход: a. набор данных 𝐷; b. множество выходных значений 𝑅; c. чувствительность 𝑢; d. значение бюджета конфиденциальности Ɛ. 2. Определить функцию оценки 𝑢(𝑑, 𝑟), которая будет вычислять «пользу» одного из выходных значений 𝑟 ∈ 𝑅 относительно остальных, т. е. оценивать на сколько текущее значение лучше или больше остальных. Например, эта функция может иметь вид представленный ниже: def u (d = adult['Marital Status'], r = 'Never-married'): return d.value_counts()[r]/np.max(d.value_counts()) 3. Вычислить оценку: 𝑢(𝑑, 𝑟) → 𝑟𝑎𝑡𝑖𝑛𝑔 для каждого элемента 𝑟 из 𝑅. 4. Для каждого элемента 𝑟 ∈ 𝑅 рассчитать вероятность на основе его оценки из пункта 2: 𝑃[𝑟 ∈ 𝑅] = 𝑒𝑥𝑝 Ɛ∗𝑢(𝐷,𝑟) 2𝑢 В качестве чувствительности можно принять значение 𝑢 = 1. 5. Нормализовать вероятности, чтобы их сумма была равна 1. 6. Выбрать значение из 𝑅 на основе вероятностей. 7. Выход: 𝑟 ∈ 𝑅. Экспоненциальный механизм интересен по нескольким причинам: 1. Механизм обеспечивает Ɛ - дифференциальную конфиденциальность 2. Работает как для конечных, так и для бесконечных множеств 𝑅, однако, когда множество 𝑅 бесконечно, может быть очень сложно построить практическую реализацию. 3. Механизм представляет собой "фундаментальный механизм" Ɛ - дифференциальной конфиденциальности: все другие дифференциально частные механизмы могут быть определены в терминах экспоненциального с соответствующим определением функции оценки 𝑢.

56 Набор данных для анализа берется тот же, что был дан в лабораторной работе 1. Помимо ранее указанных вариантов задания в этой работе, а именно запросы к данным, разделяются еще и по четности номера варианта: − для четных вариантов необходимо определить семейный статус большинства в предоставляемом наборе данных запрос; − для нечетных – образование большинства. Затем по предоставленному алгоритму 1 необходимо реализовать экспоненциальный механизм для конечного множества, который будет вычислять вышеописанные запросы, и может иметь следующий вид: def ExponentialMech(d, R, u, sensitivity = 1, epsilon = 1): # 1. Вычислить оценку для каждого элемента R rating = [u(d, r) for r in R] # 2. Рассчитать вероятность для каждого элемента на основе его оценки probabilities = [np.exp(epsilon * i / (2 * sensitivity)) for i in rating] # 3. Нормализовать вероятности, чтобы они в сумме равнялись 1 probabilities = probabilities / np.linalg.norm(probabilities, ord=1) #4. Выбрать элемент из R на основе вероятностей return np.random.choice(R, 1, p=probabilities)[0] Для вычисления точности, требуется выполнить 300 итераций экспоненциального механизма. Результат для нечетных вариантов может иметь вид, представленный на рисунке 24. Он показывает, что из 300-от итераций 230 выдали точный ответ - большинство людей в наборе закончили старшую школу, а еще 70 сделали ошибочные выводы, которые возникают из-за неудачного определения функции оценки: def u (d = data['Education'], r): return d.value_counts()[r]/np.max(d.value_counts())

57 Рисунок 24 – Результат 300-от итераций экспоненциального механизма При переопределении последней: # Функция оценки def EvaluationFunction(d,r): return d.value_counts()[r]/100 результат уже может иметь вид, представленный на рисунке 25, который дает нулевой процент ошибок. Рисунок 25 – Результат 300-от итераций экспоненциального механизма после переопределения функции оценки На основании полученных знаний о различных механизмах обеспечения дифференциальной конфиденциальности, в данной лабораторной работе студенту предлагается проанализировать все ранее рассмотренные алгоритмы и заполнить сравнительную таблицу, которая в готовом виде представлена как таблица 5. Таблица 5 - Сравнительная таблица механизмов обеспечения дифференциальной конфиденциальности Параметры сравнения Лапласа Механизмы Гаусса Экспоненциальн ый Уровень Ɛ - (Ɛ, ) − Ɛ дифференциально дифференциальна дифференциальна дифференциальна й я я я конфиденциально конфиденциально конфиденциально конфиденциально сти сть сть сть

58 Таблица 5 - Сравнительная таблица механизмов обеспечения дифференциальной конфиденциальности (продолжение) Параметры сравнения Лапласа Как достигается Добавляет шум к конфиденциальност результату ь? запроса в соответствии с распределением Лапласа. Количество шума определяется чувствительност ью запроса. Для каких запросов В основном применим? численные запросы, где один человек влияет на один параметр в наборе данных. Чувствительность Механизмы Гаусса L1 Экспоненциальн ый Результат определяется путем вычисления «пользы» параметра. В базе хранятся не сами значения, а оценка их «пользы». Запросы, где важна точность результата, или при выборе «лучшего» значения. Добавляет шум к результату запроса в соответствии с распределением Гаусса. Количество шума определяется чувствительност ью запроса. В основном численные запросы, где один человек влияет на несколько параметров в наборе данных. L1 или L2. L1 Чувствительност ь L2 ниже L1, что позволяет добиться меньшего шума. *** Таким образом, данная глава описывает практическую часть, которая посвящена разработке лабораторных работ по обеспечению дифференциальной конфиденциальности. Здесь представлены причины выбора разработанных работ, а также используемые при этом инструменты. тем для

59 ЗАКЛЮЧЕНИЕ С развитием технологий, обеспечивающих все более детальный и эффективный сбор информации, растет потребность в защите личной информации людей, предоставляющих свои персональные данные. Средства обработки данных должны гарантировать человеку приватность. Чтобы добиться этого необходимо надежное и математически строгое определение конфиденциальности, а также широкий класс алгоритмов, которые будут удовлетворять этому требованию. В процессе исследования был произведен анализ существующих в настоящее время методов обеспечения конфиденциальности, в результате которого удалось выявить основные достоинства и недостатки каждого из них. На основании полученных результатов, был выбран метод, который на мой взгляд, является наиболее актуальным в современное время и будет актуален в ближайшем будущем. Этим методом является дифференциальная конфиденциальность. Конечно же, нельзя сказать, что последний не имеет минусов, однако метод широко применим известными компаниями, такими как Google, Uber, Microsoft и позволяет добиться конфиденциальности информации, обеспечивая при этом достаточную точность. На основании этого выбора было решено разработать обучающий комплекс по обеспечению дифференциальной конфиденциальности, для чего сначала были проанализированы основные методы обеспечения дифференциальной приватности – механизм рандомизированного ответа, механизмы Лапласа и Гаусса и экспоненциальный механизм, а также сформулированы основные определения и свойства. Результатом исследования стал разработанный обучающий комплекс, состоящий из четырех работ, который может позволить специалистам информационной безопасности оценивать меру конфиденциальности набора данных, понимать и применять основные методы обеспечения дифференциальной конфиденциальности, а также строить алгоритмы по защите приватности данных пользователей, чья личная информация содержится в

60 наборе данных. Работы были реализованы на языке Python в интерактивном вебприложении Jupyter Notebook. Каждая лабораторная включают в себя цель, теоретические сведения, задания для работы, упражнения для понимания математического аппарата механизмов обеспечения дифференциальной конфиденциальности и для анализа полученных в ходе выполнения работы результатов, а также контрольные вопросы, ответы на которые можно найти в прилагаемой теоретической части, и содержание отчета. В состав раздаточного материала для студентов входят: − набор данных, анализ которого производится в лабораторной работе; − блокнот Jupyter Notebook с теоретической информацией, шаблонами кода и заданиями для работы; − документ формата .docx с информацией, требующейся для выполнения лабораторной работы, упражнениями, контрольными вопросами и содержанием отчета. Результаты информационной работы могут безопасности, быть а использованы также другими студентами людьми, заинтересованы в теме обеспечения конфиденциальности данных. по которые

61 СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 1. Microsoft Find Cancer Clues in Search Queries. [Электронный ресурс]. URL: https://www.nytimes.com/2016/06/08/technology/online-searches-can-identifycancer-victims-study-finds.html. – (дата обращения: 20.01.2021). 2. Федеральный [Электронный ресурс]. закон URL: №152-ФЗ «О персональных данных». https://rg.ru/2006/07/29/personaljnye-dannye- dok.html. – (дата обращения: 20.01.2021). 3. Приказ Федеральной службы по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор) «Об утверждении требований и методов по обезличиванию персональных данных». [Электронный ресурс]. URL: https://rg.ru/2013/09/18/dannye-dok.html. – (дата обращения: 20.01.2021). 4. L. Sweeney k-anonymity: A model for protecting privacy//International Journal on Uncertainty, Fuzziness and Knowledge-based Systems. – 2002. –№. 5.– С. 557-570. 5. P. Samarati and L. Sweeney Generalizing data to provide anonymity when disclosing information // PODS. - 1998. - Т. 98. - №. 10.1145. - С. 275487.275508. 6. Liu K., Giannella C., Kargupta H. An attacker’s view of distance preserving maps for privacy preserving data mining //European Conference on Principles of Data Mining and Knowledge Discovery. – Springer, Berlin, Heidelberg, 2006. – С. 297-308. 7. Oliveira S. R., Za O. R. ıane,“Achieving privacy preservation when sharing data for clustering,” //Proc. Workshop Secure Data Manag. – 2004. – С. 6782. 8. Chen K., Liu L. Privacy preserving data classification with rotation perturbation //Fifth IEEE International Conference on Data Mining (ICDM'05). – IEEE, 2005. – С. 4 pp. 9. Mivule K. Utilizing noise addition for data privacy, an overview //arXiv preprint arXiv:1309.3958. – 2013.

62 10. Chamikara M. A. P. et al. Efficient privacy preservation of big data for accurate data mining //Information Sciences. – 2020. – Т. 527. – С. 420-443. 11. Ishai Y. et al. Cryptography from Anonymity Ѓ. – 2006. 12. Dwork C. Differential privacy: A survey of results //International conference on theory and applications of models of computation. – Springer, Berlin, Heidelberg, 2008. – С. 1-19. 13. Leonard M. Differential Privacy: Secure and Private AI, курс на Udacity. [Электронный ресурс]. URL: https://classroom.udacity.com/courses/ud185/ lessons/3879a8dd-9393-4c7f-a615-5ac1bdb2a629/concepts/a5f2b5e4-e6c1-4b0d-954 2-9c0b8102df68. – (дата обращения: 25.02.2021). 14. Dwork C. et al. The algorithmic foundations of differential privacy //Foundations and Trends in Theoretical Computer Science. – 2014. – Т. 9. – №. 3-4. – С. 211-407. 15. Wood A. et al. Differential privacy: A primer for a non-technical audience //Vand. J. Ent. & Tech. L. – 2018. – Т. 21. – С. 209. 16. Programming Differential Privacy. – 2020. [Электронный ресурс]. URL: https://uvm-plaid.github.io/programming-dp/notebooks/ch4.html. – (дата обращения: 14.04.2020). 17. Dwork C. et al. Our data, ourselves: Privacy via distributed noise generation //Annual International Conference on the Theory and Applications of Cryptographic Techniques. – Springer, Berlin, Heidelberg, 2006. – С. 486-503. 18. Cheruvu R. A High-level Introduction to Differential privacy. – 2018 [Электронный ресурс]. URL: https://demystifymachinelearning.wordpress.com /2018/11/20/intro-to-differential-privacy/. – (дата обращения: 14.03.2021). 19. Lundmark M., Dahlman C. J. Differential privacy and machine learning: Calculating sensitivity with generated data sets. – 2017. 20. Shaistha F., Query “Sensitivity” types and effects on Differential Privacy Mechanism. – 2020. [Электронный ресурс]. URL: https://becominghuman.ai/querysensitivity-types-and-effects-on-differential-privacy-mechanism-c94fd14b9837/. (дата обращения: 07.05.2021). –

63 21. Shaistha F., Differential Privacy – Noise adding Mechanisms. – 2020. [Электронный ресурс]. URL: https://becominghuman.ai/differential-privacy-noiseadding-mechanisms-ede242dcbb2e. – (дата обращения: 24.05.2021). 22. Desfontaines D., The magic of Gaussian noise. – 2020. [Электронный ресурс]. URL: https://desfontain.es/privacy/gaussian-noise.html. – (дата обращения: 20.05.2021). 23. Jain P., Gyanchandani M., Khare N. Differential privacy: its technological prescriptive using big data //Journal of Big Data. – 2018. – Т. 5. – №. 1. – С. 15. 24. McSherry F., Talwar K. Mechanism design via differential privacy //48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). – IEEE, 2007. – С. 94-103. 25. Microsoft Researching Blog. – 2017. [Электронный ресурс]. URL: https://www.microsoft.com/en-us/research/blog/project-privtree-blurring-locationprivacy/. – (дата обращения: 27.05.2021). 26. Erlingsson Ú., Pihur V., Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response //Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. – 2014. – С. 1054-1067. 27. Goyal B., Agrawal S., Sohi B. S. Noise issues prevailing in various types of medical images //Biomedical & Pharmacology Journal. – 2018. – Т. 11. – №. 3. – С. 1227. 28. Documentation Jupyter. [Электронный ресурс]. URL: https://jupyter.org/documentation. – (дата обращения: 27.05.2021). 29. National Estimates of Drug-Related Emergency Department Visits. – 2014. [Электронный ресурс]. URL: https://www.samhsa.gov/data/report/nationalestimates-drug-related-emergency-department-visits-2004-2011-all-visits. обращения: 17.05.2021). – (дата

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв