Маева Бенуа и Мортен Даль @ Snips
Представленные здесь результаты являются результатом серии экспериментов, проведенных в Snips с использованием различных способов частного вычисления простого, но необходимого строительного блока во многих системах статистики и машинного обучения: суммирование векторов . Возможность делать это для векторов, поступающих от нескольких пользователей, позволяет нам не только выполнять базовую аналитику, но и генерировать распределения, используемые для байесовского вывода по мере необходимости, например, в прогнозирование схем общественного транспорта или создание индивидуальных предложений для открытия новых мест.
В этом конкретном сообщении в блоге основное внимание уделяется решению этой проблемы с помощью технологии, которая получила много внимания и прогресса в последние годы, а именно технологии несколько гомоморфного шифрования (или ОНА для краткости).
Гомоморфное шифрование
По сути, гомоморфная схема шифрования похожа на любую другую схему шифрования в том смысле, что она позволяет каждому зашифровать данные с помощью открытого ключа шифрования, при этом позволяя расшифровывать только те, кто знает частный ключ дешифрования.
Однако, в отличие от традиционного шифрования, он также позволяет любому преобразовывать зашифрованные значения, даже не зная ключа дешифрования. В частности, используя операции Добавить и Mult, можно вычислить новое шифрование соответственно суммы и умножения двух зашифрованных значений, ничего не изучая.
Хотя в принципе этого достаточно для вычисления любой функции на зашифрованных значениях, на практике есть некоторые ограничения. Наиболее заметным является тот факт, что с текущими схемами любая операция сложения или умножения добавляет немного шума к результирующему шифрованию, так что после определенного количества операций больше невозможно правильно расшифровать. Умножение обычно добавляет больше шума, чем сложение, но, как мы увидим, мы также будем ограничены сложением, если мы не умны.
Для наших экспериментов мы использовали современную библиотеку SEAL от Microsoft Research, которая не только реализует схему гомоморфного шифрования, но также предоставляет инструменты для оптимизации ее производительности с помощью предложения параметров и различных кодировок.
Суммирование векторов с использованием гомоморфного шифрования
Гомоморфное шифрование кажется идеальным вариантом для нашего приложения: каждый пользователь шифрует значения в своем векторе индивидуально и отправляет этот новый вектор шифров на сервер. В свою очередь, сервер использует операцию Добавить для точечного суммирования векторов от всех пользователей, в результате чего получается один вектор шифров. Затем этот вектор расшифровывается, и специалисту по данным открывается только предполагаемый результат.
Но прежде чем более внимательно посмотреть на производительность этого решения, нам необходимо решить одну проблему, связанную с тем, кто держит ключ дешифрования. В частности, мы собираемся предположить настройку, в которой все пользователи шифруют свои векторы с помощью одного открытого ключа шифрования, и что только доверенная третья сторона, отличная от сервера, знает соответствующий ключ дешифрования.
Это означает, что, несмотря на доступ ко всем шифрам, сервер не может узнать какие-либо отдельные данные, поскольку ему неизвестен ключ дешифрования. И, несмотря на наличие ключа дешифрования, доверенная сторона не может узнать какие-либо отдельные данные, поскольку единственное шифрование, которое она видит, - это то, которое дает окончательный агрегированный результат.
Эксперименты
Конкретные числа, указанные ниже, предназначены для суммирования только одного элемента векторов. Мы предполагаем, что время, необходимое для суммирования всех элементов векторов, линейно масштабируется с размерностью векторов и, следовательно, может быть выведено из случая одного элемента. Все вычисления выполнялись на машине Xeon 8x4 с тактовой частотой 3,5 ГГц и 32 ГБ памяти.
Обратите внимание, что производительность библиотеки SEAL зависит от определения оптимизированных параметров для фактических вычислений, которые нужно выполнить. Один из этих параметров в библиотеке называется poly_modulus, и он определяет степень полиномиального модуля пространства, в котором мы будем работать: R = Z [x] / X ^ (poly_modulus) +1. Мы увидим, что это оказывает огромное влияние на производительность, которую мы получаем, не только с точки зрения времени вычислений, но и с точки зрения размера битов шифрования (всякий раз, когда степень удваивается, размер битов увеличивается в четыре раза).
Первый метод
Как упоминалось выше, один из способов суммирования - это просто зашифровать все элементы своих векторов по отдельности. Затем они отправляют этот вектор зашифрованных элементов на сервер, который может выполнять точечное суммирование n терминов, просто рассматривая каждый индекс по очереди, где n - количество пользователей.
Дело в том, что при использовании схемы гомоморфного шифрования, которую мы используем, глубина вычислений оказывает огромное влияние на рост шума и, следовательно, на размеры параметров, что, в свою очередь, увеличивает размер шифрования и время вычислений. По сути, мы не хотим каждый раз вычислять прибавление глубины n-1, поскольку это быстро приводит к увеличению размеров параметров (переход от 1024 к 2048 poly_modulus уже на 24 пользователей). В результате мы используем древовидный рекурсивный метод для уменьшения глубины, что позволяет нам переключаться с глубины n-1 на log (n). Таким образом, в проведенных нами тестах нам никогда не приходилось использовать самый высокий параметр poly_modulus в библиотеке, который равен 16 384.
На приведенном ниже графике показано изменение времени вычислений в зависимости от количества пользователей, где максимальное значение 20 связано с каждым пользователем и с использованием параметров, соответствующих poly_modulus, равному 1024.
Мы видим, что вычисление суммы до 8000 пользователей, т.е. суммирование 8000 членов, занимает менее часа. Более того, необходимая загрузка для каждого пользователя составляет 12 КБ данных (определяется как 2 * (1024 + 1) * 48 бит).
Мы также видим, что после 9000 пользователей время растет намного быстрее, чем раньше. Это соответствует моменту, когда библиотека на основе своих инструментов моделирования предлагает нам переключиться на более крупные параметры шифрования (poly_modulus увеличивается до 2048). Таким образом, использование этих более тяжелых параметров замедляет вычисления и увеличивает размер загрузки до 48 КБ, но это необходимо для того, чтобы впоследствии иметь возможность правильно расшифровать шифрование.
Второй метод
Одним из недостатков первого метода является то, что он заставляет пользователей также отправлять на сервер любые незначительные значения, которые они могут иметь. В самом деле, если размерность векторов велика, тогда может быть высокая вероятность того, что некоторые из элементов равны нулю (или в противном случае незначительны). В первом методе эти элементы по-прежнему зашифровываются и отправляются пользователями, и они по-прежнему складываются вместе сервером, который, конечно, не может сказать, что он только добавляет нули.
Вот почему в нашем втором методе мы постараемся избежать бесполезной передачи данных и вычислений, которые связаны с шифрованием нулей: мы хотим зашифровать и отправить только значимые данные. Но если мы просто отправим его в векторе, как раньше, сервер не сможет узнать, какие шифрования складывать между пользователями.
Чтобы исправить это, мы привязываем к каждому элементу метку, соответствующую используемым ранее индексам. Но все же мы не хотим, чтобы сервер знал, какие ярлыки отсутствуют, поскольку он может раскрыть некоторую информацию о пользователях. Таким образом, мы также шифруем метки, бит за битом, и теперь каждый пользователь должен отправить зашифрованную метку и зашифрованный элемент для каждой (ненулевой) записи своего вектора. Чтобы вычислить окончательный выходной вектор, сервер по очереди просматривает все возможные метки и для каждой вычисляет сумму элементов, с которыми связана эта метка.
Чтобы отфильтровать элементы для каждой конкретной метки, применяется индикаторная функция, которая сопоставляет зашифрованную метку с шифрованием 1 при совпадении и с шифрованием 0 иначе. Эта функция Ind работает с зашифрованной двоичной декомпозицией enc_label зашифрованной метки и использует незашифрованную двоичную декомпозицию plain_label незашифрованной метки, которую мы хотим совпадение:
где
Это означает, что для вычисления итоговой суммы для одной конкретной метки мы должны оценить суммирование по всем зашифрованным данным, полученным от всех пользователей, причем каждый член является произведением факторов size_label и зашифрованного значения. Чтобы упростить ситуацию, мы рассматриваем только случай, когда каждый пользователь отправляет одну пару, и в этом случае суммирование для каждой метки упрощается до
Как и раньше, для оптимизации вычислений мы упорядочиваем и произведение, и суммирование в дереве глубины соответственно log (size_label) и log (n).
Чтобы увидеть, как работает эта вторая версия, мы устанавливаем размер метки на 3 (чтобы окончательный выходной вектор имел размерность 8) и меняли количество пользователей. Затем мы снова сообщаем об эффективности вычисления одного из элементов в конечном векторе, поскольку он линейно масштабируется с размером.
Если в первом методе для 450 пользователей это вычисление занимало всего несколько секунд, то здесь оно составляет почти 5 часов. Более того, хотя выполнение умножений, необходимых для фильтрации меток, очень затратно с точки зрения вычислений, библиотека также дает нам более крупные параметры для использования, что еще больше замедляет все вычисления.
Мы также можем попробовать изменить фактор, который не имеет отношения к первой версии: размер этикеток. Вот таблица, которая показывает, как изменяется время вычислений для трех пользователей:
Мы снова видим, что каждый раз, когда параметр poly_modulus увеличивается, вычисление увеличивается примерно в 15 раз. Когда это не так, он увеличивается примерно в 3 раза от одного размера этикетки к другому. Это действительно огромный фактор, влияющий на время наших вычислений, и он в основном зависит от количества и глубины умножений, которые мы собираемся сделать.
Наконец, размер загрузки, конечно же, тоже увеличивается. Теперь каждый пользователь должен зашифровать метки бит за битом, поэтому, если каждая метка имеет биты size_label, у нас есть size_label + 1 шифрование для отправки на каждое значение. Обратите внимание, что для обоих методов параметры варьируются в зависимости от общего объема данных, которые необходимо вычислить. В очень простом случае с 10 пользователями и 8 значениями, из которых только одно ненулевое, первый метод заставляет каждого пользователя отправлять 8 * 12 КБ = 96 КБ данных, а второй метод уже требует от него отправки 4 * 192 КБ = 768 КБ, поскольку большие параметры, необходимые для умножения, также увеличивают размер шифрования.
Вывод
Кажется, что всегда будет лучше использовать первый метод, представленный выше, без умножений: хотя мы можем отправлять бесполезные шифрования нуля, он наверняка будет быстрее. В то же время, первый метод достигает производительности, которая не является полностью сумасшедшей, по крайней мере, до 8000 пользователей, отправляющих, скажем, не более 100 значений каждый: пользователям придется загружать около 1,2 МБ каждый, а общее вычисление составит около 4 дней. . Это можно улучшить, если выбрать кодировку, которая объединяет несколько значений.
К сожалению, хотя производительность библиотеки SEAL и схем SHE в целом, вероятно, со временем улучшится и откроется для очень интересных приложений, на данный момент она не превосходит другие методы безопасных вычислений (по крайней мере, для этого конкретного применение).
Что касается самой библиотеки SEAL, она позволяет нам легко использовать хорошую схему SHE. Доступно множество функций для оптимизации наших вычислений, включая функции моделирования, которые мы использовали здесь для выбора точных параметров шифрования. Более того, есть много интересных функций: например, мы можем проследить эволюцию шума при шифровании, кодировать рациональные числа или использовать метод CRT для шифрования больших чисел с меньшими параметрами. В целом использование библиотеки значительно упростило работу, которую мы хотели здесь проделать.
Спасибо Brieuc, Lounes и Ludovic за их помощь в этом проекте.
Если вам понравилась эта статья, будет действительно полезно, если вы нажмете Рекомендовать ниже и попробуете наши приложения!
Вы также можете подписаться на нас в Twitter по адресу @snips.
Если вы хотите поработать над машинным обучением и конфиденциальностью, загляните на нашу страницу вакансий!
