Зашифруйте машинное обучение

Насколько практично гомоморфное шифрование для машинного обучения?

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

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

Что такое гомоморфное шифрование?

Гомоморфизм - это отображение между двумя алгебраическими структурами одного типа, которое сохраняет операции структур.

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

Гомоморфное шифрование - это форма шифрования, которая позволяет проводить вычисления с зашифрованным текстом, генерируя зашифрованный результат, который при расшифровке совпадает с результатом операций, выполненных с открытым текстом .²

Давайте определим обозначения для сообщения, зашифрованного текста, шифрования и дешифрования:

Предполагая гомоморфизм, мы получаем:

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

Работоспособность конструкций сохранилась, несмотря на зашифрованное значение.

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

Более реалистичный пример: если открытый ключ RSA - mod r и показатель степени e , то шифрование сообщения x осуществляется следующим образом:

Тогда гомоморфное свойство:

Потом был шум ...

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

Атака по выбранному открытому тексту (CPA) - это модель атаки для криптоанализа, которая предполагает, что злоумышленник может получить зашифрованные тексты для произвольных открытых текстов3.

Одним из способов защиты от CPA является введение случайного компонента, при котором двойное шифрование сообщения приводит к получению двух разных шифров. RSA решает эту проблему, используя сложные механизмы заполнения, которые дополнительно включают случайный компонент. Проблема в том, что на этот случайный компонент также влияет гомоморфная природа нашего алгоритма. Итак, если мы сложим два шифра вместе, мы также добавим введенный случайный компонент. Хотя мы создаем алгоритмы для удаления случайного компонента на этапе дешифрования, существует верхний предел случайности, после которого мы не можем восстановить сообщение. Мы называем введенную случайность «шумом» в гомоморфном шифровании.

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

Самостоятельная загрузка

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

Recrypt шифрует зашифрованный текст новым закрытым ключом (pk2), а затем удаляет первое шифрование (pk1) на этапе оценки с использованием зашифрованного секретного ключа (sk).

Полностью гомоморфное шифрование

Схема шифрования полностью гомоморфна, когда можно выполнять неявное сложение и умножение открытых текстов, манипулируя только зашифрованными текстами.

Все алгоритмы, доступные в 80-х и 90-х годах, были ограничены в своих гомоморфных функциях. Если они были гомоморфными, они либо не поддерживали сложение и умножение, либо криптографические ограничения делали их непригодными для полностью гомоморфного шифрования.

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

Вы спросите, почему этого достаточно? Представьте, что вы хотите зашифровать двоичный простой текст. Имея два шифра A, B, а также сложение и умножение, мы могли бы вычислить простую функцию 1 + A * B. Принимая во внимание, что вся арифметика является двоичной (то есть по модулю 2), такая функция создает следующую таблицу истинности:

A  B : 1+A*B
0  0   1+0*0 = 1
0  1   1+0*1 = 1
1  0   1+1*0 = 1
1  1   1+1*1 = 2 mod(2) = 0

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

Почему вы хотите зашифровать свою модель?

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

Гомоморфное шифрование модели

Зашифровать модель просто. В следующем примере я использую криптосистему Paillier. Система является вероятностной, поэтому она вносит некоторый шум, о котором нам нужно знать.

Схема [Пайе] представляет собой аддитивную гомоморфную криптосистему; это означает, что, имея только открытый ключ и шифрование x и y, можно вычислить шифрование x + y.

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

func (m *model) encrypt() {
  for _, weight := range m.weights {
    p := new(big.Int).SetInt64(weight)
    c, err := paillier.Encrypt(&m.enc.PublicKey, p.Bytes())
    m.encryptedWeights = append(m.encryptedWeights, c)
  }
}

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

Обучение с использованием гомоморфных зашифрованных данных

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

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

100 триллионов? Ладно, это даже на калькуляторе нереально ...

IBM значительно ускорила процесс, выполняя вычисления на 16-ядерном сервере более чем в два миллиона раз быстрее, чем в прежних системах.

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

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

Для немного больших параметров (~ 2x) гомоморфное умножение занимает 8,509 миллисекунд.

Теперь мы к чему-то приближаемся. Или мы? 3,5 мс звучит довольно быстро. На самом деле это не так. Среднее время реакции человека составляет 215 мс. Добавление в открытый текст составляет доли наносекунды. Наносекунда - это миллионная миллисекунда. И вы могли заметить, что время вычислений не зависит от выбора параметров для генерации закрытого ключа.

Microsoft утверждает, что ее система оптического распознавания на основе CryptoNet способна делать 51 000 прогнозов в час.

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

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

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

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

Заключение

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

Итак, решило ли это наши проблемы? Мы еще не достигли этого, но гомоморфное шифрование - это то, что мы определенно держим в секрете.

Эпилог

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

Если вам интересно использовать HELib на Голанге, вы найдете некоторую помощь, чтобы начать работу с helib-go.

[1] wikipedia.org/wiki/Homomorphism
[2] wikipedia.org/wiki/Homomorphic_encryption
[3] w ikipedia.org/wiki/Chosen-plaintext_attack
[4] Джентри, Крейг. Полностью гомоморфная схема шифрования. Стэнфордский университет, 2009.
[5] wikipedia.org/wiki/Paillier_cryptosystem
[6] theregister.co.uk/researchers_break_homomorphic_encryption
[7] theregister.co.uk / ibm_open_source_homomorphic_crypto
[8] Варя, Маянк, Софья Якубова и Ян Ян. Hetest: структура для тестирования гомоморфного шифрования. Международная конференция по финансовой криптографии и безопасности данных. Springer Berlin Heidelberg, 2015.
[9] Гилад-Бахрах, Ран и др. Криптонеты: применение нейронных сетей к зашифрованным данным с высокой пропускной способностью и точностью. Международная конференция по машинному обучению. 2016 г.