Эта статья от Google и называется: «Практическая безопасная агрегация для машинного обучения с сохранением конфиденциальности». Авторами являются Кит Бонавиц и др. Статья была опубликована в CCS 2017. Давайте сначала разберемся с общим контекстом этой статьи:

Introduction
Secure Aggregation for Federated Learnign
Cryptographic Primitives
Technical Intuition
A Practical Secure Aggregation Protocol
Security Analysis
Evaluation
Discussion and Future Work

вводить

Давайте начнем с картинки, просто взгляните на нее.

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

имеют $m$ клиенты $C_1, C_2, ..., C_m$ , где каждый клиент $C_i$ есть личные данные $x_i$ . Бизнес-требования требуют, чтобы все клиенты объединились, чтобы совместно найти частное и $\sum_{i=1}^m x_i$ На сервер, и при этом соблюдать требования безопасности, то есть не допускать утечки данных на сервер и другим клиентам $x_i$ .

В сценарии приложения в этой статье в основном выбирается мобильный телефон в качестве клиента, что является относительно репрезентативным сценарием FL.В этом сценарии есть две основные проблемы:

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

Поэтому в данной статье предлагаются две модели:

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

Безопасная агрегация в рамках федеративного обучения

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

Может обрабатывать многомерные векторы
communication-efficient
robust to users dropping out
Иметь надежные функции безопасности (для серверной или неавторизованной сетевой модели)

Основы криптографии

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

делиться секретами
Key Agreement
Authenticated Encryption
Генератор псевдослучайных чисел
механизм цифровой подписи
Инфраструктура открытого ключа PKI

делиться секретами

Это родственное понятие криптографии, которое можно назвать разделением секрета.Когда секрет представляет собой секретный ключ, его также можно назвать разделением секретного ключа. Его функция заключается в том, чтобы поместить секрет $s$ выделенный $n$ пользователей, то это $n$ любой из пользователей $t$ Пользователи могут восстановить секреты $s$ . Мы предполагаем, что пользовательский набор $\mathcal{U}$ . Таким образом, совместное использование секрета состоит из двух частей:

Стадия распространения: $\textbf{SS.share}(s,t,\mathcal{U})\rightarrow \{(u, s_u)\}_{u\in \mathcal{U}}$ , указывая на то, что секрет $s$ Доступно всем пользователям, все данные являются секретным ресурсом $s_u$ ;
Этап восстановления: $\textbf{SS.recon}(\{(u, s_u)\}_{u\in\mathcal{V}}, t) \rightarrow s$ , представляющий заданную серию пользователей и секретных ресурсов, а также пороговое значение $t$ , вы можете восстановить секрет $s$ .

Key Aggrement

Ключевое соглашение включает в себя следующие операции: $\textbf{KA.param, KA.gen, KA.agree}$ ,в, $\textbf{KA.param}(k) \rightarrow pp$ дает общедоступные параметры, затем $\textbf{KA.gen}(pp)\rightarrow (s_{u}^{SK},s_{u}^{PK})$ Разрешить любому пользователю генерировать открытые и закрытые ключи, а затем $\textbf{KA.agree}(s_{u}^{SK},s_{v}^{PK}) \rightarrow s_{u,v}$ представляет пользователя $u$ Вы можете комбинировать свой закрытый ключ с открытым ключом другой стороны, чтобы получить $u$ и $v$ между $s_{u,v}$ секрет.

В этой статье используется протокол обмена ключами Диффи-Хеллмана, и три операции:

$\textbf { KA.param }(k) \rightarrow\left(\mathbb{G}^{\prime}, g, q, H\right)$ , генерация простых чисел $q$ группа $\mathbb{G}^{\prime}$ , генератор есть $g$ , а задана хэш-функция $H$ ;
$\textbf { KA.gen }\left(\mathbb{G}^{\prime}, g, q, H\right) \rightarrow\left(x, g^{x}\right)$ , Выбрать $x \leftarrow \mathbb{Z}_{q}$ как закрытый ключ $s_{u}^{SK}$ , $g^x$ как открытый ключ $s_u^{PK}$
$\textbf { KA.agree }\left(x_{u}, g^{x_{v}}\right) \rightarrow s_{u, v}$ ,рассчитать $s_{u, v}=H\left(\left(g^{x_{v}}\right)^{x_{u}}\right)$ .

Таким образом, после трех вышеуказанных операций две стороны, совместно использующие данные, могут получить случайное число, известное только им. $s_{u,v} = s_{v,u}$ , в котором используется принцип $(g^{x_u})^{x_v} = (g^{x_v})^{x_u}$ , а затем задайте хеш-функцию.

Authenticated Encryption

Аутентифицированное шифрование гарантирует конфиденциальность и целостность при передаче сообщений между двумя сторонами. Он включает в себя три операции:

Алгоритм генерации секретного ключа, сгенерировать секретный ключ $c$ ;
$\textbf{AE.enc}(c,x)$ , используя данные пары ключей $x$ Зашифруйте и получите зашифрованный текст, предполагая, что зашифрованный текст $y$ Бар;
$\textbf{AE.dec}(c, y)$ , раскрыть секрет шифртекста, вывести надпись, если ее можно расшифровать, иначе вывести флаг ошибки $\perp$ .

Так что, если это правильно, есть $\textbf{AE.dec}(c, \textbf{AE.enc}(c, x))=x$ , то есть расшифровка прошла успешно

Генератор псевдослучайных чисел

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

Механизм подписи

Механизм подписи состоит из трех операций, а именно:

$\textbf { SIG.gen }(k) \rightarrow\left(d^{P K}, d^{S K}\right)$ , что означает создание пары открытый-закрытый ключ;
$\textbf{SIG.sign}\left(d^{S K}, m\right) \rightarrow \sigma$ , что указывает на то, что сообщение связано с закрытым ключом $m$ подписывать;
$\textbf{SIG.ver}{}\left(d^{P K}, m, \sigma\right) \rightarrow\{0,1\}$ , проверяет подпись с помощью открытого ключа и сравнивает ее с исходными данными $m$ Сделайте сравнение, чтобы определить, пройдена ли проверка.

инфраструктура открытых ключей

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

Техническая отправная точка

Размышляя об определении проблемы, с которого мы начали, мы имеем $n$ пользователей, каждый со значением $x_u$ , то сервер должен вычислить $\sum x_u$ , но каждый пользователь не может передавать свои данные. Поэтому автор дает такую идею, может ли пользователь 1 вычесть число, а пользователь 2 добавить число, чтобы данные пользователя 1 и пользователя 2 были неточными, но общая сумма все равно была точной. Затем эта идея расширяется, и в статье появляется схема.

Masking with One-Time Pads

Все пользователи согласовывают случайное число парами, а именно: пользователь $i$ с пользователями $j$ Согласованные случайные числа $s_{i,j}$ , а затем для данных $x_i$ Возмущение выполняется по следующей формуле, и результат $y_i$ :

\begin{aligned} y_{i} &= mask(x_i)\\ &=x_{i}+\sum_{j \in U: i < j} s_{i, j}-\sum_{j \in U: i > j} s_{j, i} \quad \bmod R \end{aligned}

Конечно, в сцене FL вышеперечисленное $x$ и $s$ на самом деле являются многомерными векторами. Для удобства иллюстрации проблемы последующее описание представлено не в виде вектора. Тогда, очевидно, можно доказать, что: $\sum y_i = \sum x_i$ . Итак, сервер вычисляет:

\begin{aligned} z&=\sum_{i \in U} y_{i} \\ &=\sum_{i \in U}\left(x_{i}+\sum_{j \in U: i < j} s_{i, j}-\sum_{j \in U: i > j} s_{j, i}\right) \\ &=\sum_{i \in U} x_{i} \quad \bmod R \end{aligned}

Например, если есть три данных $x_1, x_2, x_3$ , то процесс маскирования таков:

\begin{aligned} y_1 &= x_1 + s_{12} + s_{13}\\ y_2 &= x_2 - s_{12} + s_{23}\\ y_3 &= x_3 - s_{13} - s_{23} \end{aligned}

Ниже приведена диаграмма, иллюстрирующая проблему, а именно:

Следовательно, ** означает, что каждое случайное число вычитается один раз и добавляется снова. ** Поэтому есть:

\sum y_i = \sum x_i

Эта логика кажется идеальной, но она еще не решена и сталкивается со следующими проблемами:

Как договориться о случайных числах
Что, если клиент внезапно отключится?

Как согласовать случайные числа

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

Что делать, если клиент отключился/задержался

Вышеуказанные шаги вроде бы способны решить проблему Secure Aggregation, но возникнет новая проблема, если клиент "отвалится", что делать?

С тем же успехом мы могли бы предположить, что второй клиент отключен, тогда текущий запрос на самом деле состоит в том, чтобы спросить $y_1 + y_3$ , чтобы сервер мог запросить прибытие 1-го и 3-го клиентов $s_{1,2},s_{2,3}$ , то можно рассчитать по следующей формуле:

\begin{aligned} y_1 + y_3 - s_{1,2}+s_{2,3} = x_1+x_3 \end{aligned}

Кажется, нет никаких проблем, когда он выходит из сети. Но подумайте, что если клиент отключится на этапе восстановления? Так что нам нужен способ восстановить эти случайные числа, пока есть достаточное количество клиентов. С точки зрения понимания, мы можем думать, что каждый клиент ставит $s_{u,v}$ Распространяется секретным обменом, и пока есть $t$ Если клиент находится в сети, вы можете восстановить его обратно в $s_{u,v}$ . (На самом деле то, что распределяется, это доля открытого ключа, и то по открытому ключу и $v$ данные, можно рассчитать $s_{u,v}$ ). с этим $t$ -out-of- $n$ Схема обмена ключами, пока есть $t$ Если пользователь онлайн, он не боится отключения клиента.

Но подождите, если он не упал, аНа этот раз из-за задержки $y_2$ А если вдруг?

В это время мы можем $y_2 + s_{1,2}-s_{2,3}$ понять это $x_2$ Да, исходные данные восстановлены. Табу. так что мыДолжна быть не только возможность восстановить случайное число из-за отключения/задержки пользователя. $s$ , но и убедитесь, что данные невозможно восстановить $x$ .

Double-Masking

Итак, автор пытается ввести новое случайное число $b$ , привяжите это случайное число к данным, например:

\begin{aligned} \boldsymbol{y}_{u}=\boldsymbol{x}_{u} &+\mathbf{P R G}\left(\boldsymbol{b}_{u}\right) \\ &+\sum_{v \in \mathcal{U}: u < v} \operatorname{PRG}\left(s_{u, v}\right) -\sum_{v \in \mathcal{U}: u > v} \operatorname{PRG}\left(s_{v, u}\right) \quad(\bmod R) \end{aligned}

PRG может быть менее подробным и пониматься непосредственно как $y_u = x_u + b_u + \sum_{ u < v } s_{u,v} - \sum_{u > v} s_{u,v}$ Вот и все. Затем используйте следующую стратегию:

На этапе распределения случайное число $b$ и $s$ распространяются с использованием схемы обмена секретами и гарантируют $t$ пользователь может восстановить.
На этапе восстановления для честного пользователя $v$ , он не $b_u$ и $s_{u,v}$ Скажи это одновременно.если пользователь $u$ упал, то $v$ скажет $s_{u,v}$ , если пользователь $u$ онлайн, тогда $v$ скажет $b_u$ .

Разумеется, упомянутые выше т.н. $b_u$ на самом деле сказать $b_u$ поделитесь хоть $t$ поделиться, чтобы восстановить $b_u$ . Поскольку используются два типа случайных чисел, этот метод также называется двойной маской. То есть в том случае, если все-таки не все отключены $b$ Его можно восстановить, и схема с двумя масками эквивалентна схеме с одной маской. в пользователе $u$ В случае отключения данные $x_u$ Это будет улажено, не принося его, так что $b_u$ Просто оставьте это в покое, восстановите $s_{u,v}$ Достаточно.

общий процесс

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

Затем автор перечисляет затраты на расчет, связь и хранение на стороне пользователя и на стороне сервера на разных этапах, где количество пользователей $n$ , измерение данных каждого пользователя равно $m$ , различные затраты показаны в следующей таблице:

другие главы

Лично я чувствую, что основная часть этой статьи была понята здесь.Следующие разделы включают дальнейшее уточнение этого протокола, описание безопасности, экспериментальные результаты и связанную работу. Если вы обнаружите здесь какие-либо ямы, когда в будущем соприкоснетесь с соответствующим контентом, пожалуйста, восполните это.

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

《差分隐私》