Мортен Даль и Джозеф Дюро @ Snips

Осведомленность, отраслевые стандарты, а также законодательство, касающееся конфиденциальности, неуклонно развиваются, превращая конфиденциальность в стратегическое и этическое позиционирование. Крупные компании, такие как Google и Apple, учли эти возможности и ограничения и устанавливают высокие стандарты в этой области.

Хотя есть некоторые практические решения, такие как хранение ограниченного объема данных, удаление уникальных идентификаторов, периодическое стирание баз данных и т. Д., Мы все предпочли бы, чтобы конфиденциальность была основана на математических свойствах.

Дифференциальная конфиденциальность (или сокращенно DP) - интересное решение этой проблемы. Идея заключается в том, что вы хотите добавить шум к пользовательским данным, чтобы вы не могли ничего узнать на индивидуальном уровне, при этом подавляя шум на уровне агрегированной совокупности.

Локальная и глобальная дифференцированная конфиденциальность

Дифференциальная конфиденциальность бывает двух видов: локальная и глобальная.

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

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

  1. Подбрось монетку
  2. Если хвост, ответьте честно
  3. Если орел, подбросьте еще одну монету и ответьте "да", если решка, и "нет", если решка.

Но есть более сложные механизмы, такие как недавно представленный для аналитики Apple, и система RAPPOR от Google (это то, с чем мы будем сравнивать).

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

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

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

К счастью, современная криптография дает выход из ситуации, когда слепо доверять агрегатору: безопасное многостороннее вычисление или сокращенно MPC. Используя различные методы, такие как совместное использование секрета и гомоморфное шифрование, оказывается, что мы действительно можем построить криптографическую систему, которая обеспечивает такую ​​же конфиденциальность, как и локальная модель, но предполагает гораздо меньшие шаги веры!

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

В этой системе пользователи шифруют свои входные данные и отправляют шифрование агрегаторам. Затем агрегаторы вычисляют агрегирование вместе без дешифрования (они не могут, потому что не знают ключа дешифрования) и добавляют шум один раз в конце. Наконец, они входят в процесс дешифрования вместе с специалистом по обработке данных, так что только последний изучает результат.

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

РАППОР против Global DP

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

Наш эксперимент включает классический пример, включенный в исходную статью RAPPOR: вселенная состоит из списка из 100 строк-кандидатов, вероятность появления которых экспоненциально распределена, а также 100 совершенно маловероятных строк-кандидатов. Можем ли мы классифицировать, какие из них имеют строго положительную вероятность появления после того, как был добавлен шум для обеспечения дифференциальной конфиденциальности?

Мы провели анализ для ряда пользователей от 100 до 1 000 000, каждый из которых отправил по одному образцу. Конфиденциальность, измеряемая параметром epsilon в соответствии с определением DP, установлена ​​на ln (3). В частности, для p установлено значение 0,5, q равно 0,75, f равно 0, размер фильтров Блума составляет 32 бита, одно хеширование функция используется с 64 когортами. Это одна из стандартных параметризаций, используемых в статье, соответствующая так называемому одноразовому базовому RAPPOR. Для глобального DP мы выбрали канонический механизм Лапласа, в котором шум, распределенный согласно Lapl (чувствительность / эпсилон), добавляется к каждому бину гистограммы. Если каждый образец поступает от другого пользователя, чувствительность гистограммы к вкладу каждого пользователя равна 1.

Для каждого количества выборок наблюдения отбираются в соответствии с основным распределением: 100 кандидатов с экспоненциальным распределением и 100 кандидатов с вероятностью 0, что дает исходное распределение выборки. Затем эти образцы обрабатываются с помощью механизма RAPPOR, создавая распределение RAPPOR. Исходное распределение выборки обрабатывается с помощью механизма Лапласа, что дает распределение Лапласа.

RAPPOR включает в себя этап, который определяет, имеет ли каждый кандидат существенно ненулевую вероятность появления. Аналогичная операция выполняется с распределением Лапласа, проверяя, превышают ли оцененные частоты по распределению Лапласа 95-й квантиль шума Лапласа, который был добавлен. Характеристики классификации по каждому механизму показаны ниже:

Мы видим, что в условиях этого эксперимента механизм Лапласа с 1000 выборок предлагает аналогичную производительность предсказания, чем RAPPOR с 1,000,000 выборок, гарантируя при этом такой же уровень дифференциальной конфиденциальности. Это означает, что DP доступен стартапам с несколькими тысячами пользователей и крупным компаниям с сотнями миллионов!

Применение DP к машинному обучению

Сравнение с RAPPOR полезно в качестве ссылки на текущее состояние дел в отрасли. Но мы хотели продвинуть анализ немного дальше, исследуя количество пользователей, которое нам понадобится в нашей практической ситуации, если мы выберем глобальный DP.

В настоящее время мы работаем над помощником, который поможет пользователю, когда ему нужно куда-то пойти. Он анализирует места, с которыми он взаимодействовал (посещал, искал, упоминал в сообщениях), чтобы предоставить контекстные рекомендации о местах, которые могут быть ему интересны.

Такие сервисы, как Foursquare, довольно хорошо определяют популярные места и новые места, которые имеют тенденцию. Но им не хватает глубокого понимания контекста и предпочтений пользователя из-за ограниченного объема личных данных, которыми они располагают. Хотя мы можем положиться на Foursquare, чтобы получать предложения о новых местах, мы предпочли бы иметь модель, которая определяет оптимальные параметры для передачи Foursquare, такие как тип мест, которые нравятся пользователю, или расстояние, которое он готов пройти.

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

В каждой ситуации нас интересует возможность предсказать три наиболее популярные категории из 8 категорий мест высокого уровня (еда, магазин, на открытом воздухе, искусство и развлечения и т. Д.). После выбора категории аналогичная модель может определить расстояние, которое пользователь готов пройти.

Ниже мы изобразили точность получения трех верхних категорий в каждом контексте, принимая во внимание, что каждый пользователь отправляет контекст вокруг мест, которые он посетил, и что мы стремимся к ln (3) дифференциальной конфиденциальности.

Здесь мы снова видим, что, хотя большее количество данных позволяет создавать более точные модели, наличие нескольких тысяч пользователей уже позволяет использовать DP в приложениях машинного обучения!

Заключение

Наша интуиция подсказывала, что использование глобальной модели дает больше преимуществ, чем использование локальной модели, когда у нас небольшая база пользователей. Это было подтверждено на каноническом примере, на котором проводилось тестирование RAPPOR, где аналогичная полезность может быть достигнута с помощью глобальной модели с количеством пользователей в 1000 раз меньше.

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

Остается один вопрос: насколько сильно мы теряем производительность при использовании криптографии в мобильных настройках. Хотя есть готовые решения MPC, ни одно из них не подходит для нашего случая использования, и вместо этого нам пришлось разработать индивидуальное решение, более точно подходящее к общему приложению. Это то, о чем мы расскажем в одном из следующих постов в блоге!

Если вам понравилась эта статья, будет действительно полезно, если вы нажмете Рекомендовать ниже и попробуйте наши приложения!

Вы также можете подписаться на нас в Twitter: @mortendahlcs, @jodureau и @snips.

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