1

SEAL（简单加密算术库）使用伽罗瓦自同构来实现批量计算（即，在一次操作中并行地添加和乘法许多密文）。

批处理过程在SEAL 2.3.1 手册的5.6 伽罗瓦自同构和7.4 CRT 批处理中进行了描述。

特别是，上面的两个部分指出以下环是同构的。

\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 是单位模 t 的原始 2n 次根。

可以在此处找到上述等式的图像（Stackoverflow 暂时不允许我显示图像）

相同的部分还指出，可以使用 Galois Automorphims将明文元组映射\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)？或者换一种说法，Compose操作是如何工作的？你如何使用伽罗瓦自同构（行和列旋转）来计算它？

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

4

1 回答 1

1

  1. 同构简单地在单位根处计算多项式以获得 Z t的元素。请注意，这是有效的，因为相关的统一根本身在 Z t中。整个批处理系统只是一个古老的中国剩余定理：批处理槽是明文多项式模 x-zeta 2i+1对不同 i 的约简。回去需要一个标准的 CRT 重建。

  2. 在实践中，CRT 是通过数论变换（有限域上的 FFT）及其逆变换实现的。伽罗瓦自同构通过置换它们，形成两个轨道来作用于单位根。如果我们以这样一种方式对明文矩阵槽进行排序，即对应于原始根的下一个伽罗瓦共轭的批处理槽值总是在对应于该原始根的槽值的左侧（或右侧），那么伽罗瓦动作将置换循环矩阵的行。两个轨道也可以互换，对应柱子旋转（交换）。

由于 SEAL 使用的 NTT 算法导致所谓的“位反转”输出顺序，事情变得更加复杂。在可以执行任何 NTT 或逆 NTT 之前确定批处理值的正确排序时，需要考虑这一点。

于 2018-09-18T07:46:47.493 回答