SEAL (Простая зашифрованная арифметическая библиотека) использует автоморфизмы Галуа для обеспечения возможности пакетных вычислений (т. е. сложения и умножения множества зашифрованных текстов параллельно за одну операцию).
Процедура пакетной обработки описана в разделах 5.6 Автоморфизмы Галуа и 7.4 Пакетная обработка CRT документа руководство по SEAL 2.3.1.
В частности, в двух приведенных выше разделах утверждается, что следующие кольца изоморфны.
\prod_{i=0}^{n} \mathbb{Z}_t \cong \prod_{i=0}^{n} \mathbb{Z}_t[\zeta^{2i+1}] \cong \mathbb{Z}_t[x]/(x^n+1)
где \ zeta - примитивный корень 2n-й степени из единицы по модулю t.
Изображение приведенного выше уравнения можно найти на здесь (Stackoverflow пока не позволяет мне отображать изображения)
В тех же разделах также говорится, что отображение кортежей открытого текста в \prod_{i=0}^{n} \mathbb{Z}_t
на \mathbb{Z}_t[x]/(x^n+1)
может быть выполнено с помощью автоморфимов Галуа.
Точнее, n-мерный \mathbb{Z}_t
-векторный открытый текст можно рассматривать как матрицу 2 на (n / 2), а автоморфизмы Галуа будут соответствовать поворотам столбцов и строк этой матрицы.
После применения автоморфизмов Галуа к вектору открытого текста (вращения строк и столбцов) можно получить соответствующий элемент в \mathbb{Z}_t[x]/(x^n+1)
, который будет использоваться для пакетных вычислений.
У меня следующие вопросы.
1- Почему \mathbb{Z}_t[\zeta^{2i+1}]
изоморфен \mathbb{Z}_t
?
2- Как автоморфизмы Галуа используются для точного отображения n-мерных \mathbb{Z}_t
-векторных открытых текстов на элементы в \mathbb{Z}_t[x]/(x^n+1)
? Или, иначе говоря, как работает операция Составить? И как использовать автоморфизмы Галуа (вращение строк и столбцов) для его вычисления?
========================================================================