Использование автоморфизмов Галуа в гомоморфном шифровании

Question

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 - примитивный 2-й корень единицы по модулю t.

Изображение приведенного выше уравнения можно найти здесь (Stackoverflow пока не позволяет мне отображать изображения)

В тех же разделах также говорится, что сопоставление текстовых кортежей в \prod_{i=0}^{n} \mathbb{Z}_t в \mathbb{Z}_t[x]/(x^n+1) может быть выполнено с использованием Galois Automorphims.

Точнее, 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)?Или иначе говоря, как работает операция Compose ?А как вы используете автоморфизмы Галуа (вращения строк и столбцов) для его вычисления?

==============================================================================

Answer 1

1. Изоморфизм просто вычисляет многочлен у корня единицы, чтобы получить элемент из Z _t .Обратите внимание, что это работает, потому что соответствующий корень единства находится в Z _t .Вся система дозирования - это просто большая старая китайская теорема об остатках: интервалы дозирования - это сокращения открытого полинома по модулю x-zeta ^{2i + 1} для разных i.Возвращение требует стандартной реконструкции CRT.

2. На практике CRT реализуется через Теоретическое преобразование числа (БПФ над конечным полем) и его обратное.Автоморфизм Галуа действует на корни единства, переставляя их, образуя две орбиты.Если мы упорядочим слоты матрицы открытого текста таким образом, чтобы значение порции порции, соответствующее следующему сопряжению Галуа примитивного корня, всегда находилось слева (или справа) от значения слота, соответствующего этому корню примитива, то действие Галуа переставитстроки матрицы циклически.Две орбиты также можно поменять местами, что соответствует повороту столбца (своп).

Ситуация еще более осложняется тем фактом, что алгоритм NTT, который использует SEAL, приводит к так называемому порядку вывода «бит с обратным битом».Это необходимо учитывать, когда определяется правильное упорядочение значений дозирования перед выполнением любого NTT или обратного NTT.