Применяйте гомоморфные операции к большим зашифрованным данным
В настоящее время экспериментирую с гомоморфным шифрованием с использованием библиотеки PALISADE .
Я хочу применить простые операции, такие как сложение и умножение, к большим зашифрованным входным данным. Например, ввод A[3200]и ввод B[4096]обоих векторов / массивов значений int зашифровываются. С этими двумя входами Enc(A)и Enc(B)я хочу применить умножение:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
Насколько мне известно, реализация вышеописанных требований может быть решена двумя разными способами:
Упакуйте входные данные в один зашифрованный текст (как SIMD) и для операций, которые я мог бы использовать,
EvalIndexAt()чтобы получить правильное значение из зашифрованного ввода.Зашифруйте каждое значение из A и B отдельно.
Я не совсем уверен, какое из описанных решений было бы лучшим с точки зрения эффективности . Первый подход имеет то важное преимущество, что требуется только один процесс шифрования для всего ввода, но это имеет недостаток, заключающийся в том, что мне всегда нужно обращаться к правильному элементу с помощью EvalAtIndex()метода, и чем больше вводимые данные, тем медленнее вычисляются полученные EvalAtIndexKeyGen(). (По крайней мере, на моей машине)
Второй подход кажется более подходящим, поскольку EvalAtIndex()в нем нет необходимости, но он связан с затратами на шифрование каждого значения отдельно, что занимает довольно много времени.
Какие-нибудь мысли рекомендации?
Ответы
Спасибо за вопрос.
Основное преимущество подхода №1 (SIMD) заключается в том, что вы можете выполнять сложение и умножение векторов (из 4096 или более целых / действительных чисел), используя одно гомоморфное сложение или умножение (очень эффективно). Вращение (называемое EvalAtIndexв PALISADE) - это дополнительная операция, которая позволяет одному обращаться к отдельным индексам или выполнять эффективное суммирование (как во внутреннем произведении), умножение матриц и т. Д. Этот подход также имеет гораздо меньший коэффициент расширения зашифрованного текста (в 4096 раз или больше), чем подход №2. Как правило, на практике предпочтительнее вариант №1 (и я не могу придумать ни одного реального варианта использования, в котором я бы хотел использовать вариант №2).
Чтобы свести к минимуму затраты на умножение, возможно, вы могли бы упаковать вектор в смежные блоки, чтобы вам понадобилось одно вращение для одного блока. Например,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
Вы можете использовать еще один метод EvalFastRotation(доступен только для CKKS и BGVrns в PALISADE v1.10.x). Если вам нужно несколько поворотов одного и того же зашифрованного текста, вы можете предварительно вычислить что-то для зашифрованного текста, а затем использовать более дешевые повороты (наибольшая выгода достигается при переключении ключа BV) - см.https://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp для примера.
Есть также способы минимизировать количество ключей, которые должны быть сгенерированы, если вам нужно несколько поворотов (только вычислите примерно квадратный корень из количества необходимых поворотов), например, используя технику «маленький шаг-гигантский шаг», описанную в https://eprint.iacr.org/2018/244 (эти методы могут быть реализованы в вашем приложении на основе PALISADE).
Вы также можете использовать особый порядок упаковки вектора, если известен шаблон для выполнения умножения (таким образом, ваше вращение подготовит несколько блоков по вектору с помощью одной операции вращения). Вращения являются циклическими (циклическими) как в CKKS, так и в BGVrns, когда # слоты открытого текста (размер пакета) равны ring dimension/ 2. Если у вас вектор меньшего размера, вы всегда можете клонировать / реплицировать маленький вектор столько раз, сколько необходимо. заполнить ring dimension/ 2.
Таким образом, наибольшее повышение эффективности может быть достигнуто, если вы думаете о своей проблеме с точки зрения SIMD-подобных векторов. Затем вы можете переформулировать свою проблему / модель, чтобы в полной мере воспользоваться набором инструментов, который предоставляет HE. В некотором смысле это похоже на программирование с использованием векторизованных инструкций, например AVX, или матрично-ориентированного программирования (как в MATLAB).