Шифрование Homomorphi c: умножение матрицы на вектор с использованием библиотеки PALISADE

Question

Всем экспертам:

Я хочу реализовать умножение матрицы на вектор с очень большими матрицами (600000 x 55). В настоящее время я могу выполнять такие операции, как сложение, умножение, внутренний продукт и т. Д. c. с небольшими входами. Когда я пытаюсь применить эти операции к большим входам, я получаю такие ошибки, как Invalid next size (normal), или у меня заканчивается основная память, пока ОС не убьет процесс (код выхода 9).

Есть ли у вас какие-либо рекомендации / примеры, как заархивировать эффективный способ реализации умножения матрицы на вектор или чего-то подобного? (Используя BFV и CKKS).

PS: Я использую библиотеку PALISADE, но если у вас есть лучшие предложения, такие как SEAL или Helib, я бы с радостью использовал их.

Answer 1

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

Для умножения матрицы на вектор вы можете использовать методы, описанные в https://eprint.iacr.org/2019/223, https://eprint.iacr.org/2018/254 и дополнительная информация https://eprint.iacr.org/2020/563. Основная идея - выбрать правильную кодировку и воспользоваться преимуществами упаковки SIMD. Вы будете работать с векторным размером степени двойки и можете упаковать матрицу либо как 64xY (несколько строк) на зашифрованный текст, либо как часть каждой строки на зашифрованный текст, в зависимости от того, какой из них более эффективен.