格陷门在模上的实现及应用

### 格陷门在模上的实现及应用 #### 1. 相关定义与背景 首先介绍 Decision Module - LWEn,d,q,σ 的定义。给定均匀矩阵 \(A \in R_{q}^{m \times d}\) 以及向量 \(b = As + e \mod q\)，其中 \(s \leftarrow U(R_{q}^{d})\) 且 \(e \leftarrow D_{R^{m},\sigma}\)，需要将 \((A, b)\) 的分布与 \(R_{q}^{m \times d} \times R_{q}^{m}\) 上的均匀分布区分开来。 高效的基于陷门的方案，依赖于特定的陷门概念。这些陷门是对以往短基的改进，更加紧凑且算法更快。此前已被推广到理想格，但尚未应用于模的场景。我们的目标是将相关构造推广到模格，具体通过以下两个步骤实现： - **TrapGen 算法**：生成均匀矩阵 \(A \in R_{q}^{d \times m}\) 及其陷门 \(T \in R^{2d \times dk}\)，其中 \(k = \lceil \log_{b} q \rceil\) 且 \(m = d(k + 2)\)。陷门 \(T\) 从参数为 \(\sigma\) 的高斯分布中采样，矩阵 \(A\) 定义了困难的模 SIS 和 ISIS 问题。 - **SamplePre 算法**：利用 \(T \in R^{2d \times dk}\) 进行高效的高斯原像采样，参数为 \(\zeta\)，有效解决模 SIS 和 ISIS 问题。 高斯原像采样是从格 \(\Lambda_{q}^{\perp}(A)\) 的陪集上的球形离散高斯分布中采样，该分布的标准差 \(\zeta\) 应较小，且生成的向量不能泄露陷门 \(T\) 的信息。采样过程分为两个互补阶段： - **G - 采样**：参数为 \(\alpha\)，确保样本位于正确的陪集。 - **扰动采样**：参数为 \(\zeta\) 和 \(\alpha\)，隐藏输出分布中关于 \(T\) 的信息。 #### 2. 扰动采样 扰动采样的目标是从 \(R^{m}\) 上协方差为 \(\Sigma_{p} = \zeta^{2}I - \alpha^{2} \begin{bmatrix} T \\ I \end{bmatrix} [T \ T \ I]\) 的高斯分布中采样向量。该协方差矩阵与 G - 采样输出 \(z\) 对应的 \(\begin{bmatrix} T \\ I \end{bmatrix} z\) 的协方差矩阵互补，使得扰动 \(p\) 与 \(\begin{bmatrix} T \\ I \end{bmatrix} z\) 相加后，最终协方差矩阵 \(\Sigma_{p} + \alpha^{2} \begin{bmatrix} T \\ I \end{bmatrix} [T \ T \ I] = \zeta^{2}I\) 不泄露陷门 \(T\) 的信息。 扰动采样在环 \(P = R[X]/\langle X^{n} + 1 \rangle\) 中进行，虽然最终结果为整数，但计算使用实数。由于 \(R\) 可自然嵌入 \(P\)，可认为 \(T\) 和协方差矩阵的元素在 \(P\) 中。 Genise 和 Micciancio 在环设置中使该操作高效化，他们描述了算法 SampleFz，输入为协方差多项式 \(f\) 和中心 \(c\)，返回 \(R\) 上相应高斯分布的样本。但该方法不能直接应用于模设置，因为存在额外的秩模参数 \(d\)。我们需要处理协方差矩阵 \(\Sigma \in P^{2d \times 2d}\) 和中心 \(c \in P^{2d}\)。通过利用相关引理和 SampleFz 算法，将协方差矩阵分解为不同大小的块并更新中心，从而迭代采样扰动 \(p_{i} \in R\)。 下面介绍 SamplePerturb 算法，给定陷门 \(T\) 以及高斯参数 \(\zeta\) 和 \(\alpha\)，返回从协方差为 \(\Sigma_{p} = \zeta^{2}I - \alpha^{2} \begin{bmatrix} T \\ I \end{bmatrix} [T \ T \ I]\) 的 \(R^{m}\) 上中心离散高斯分布中采样的向量 \(p\)。该算法不直接使用 \(\Sigma_{p} \in P^{m \times m}\)，而是使用更小的矩阵 \(\Sigma \in P^{2d \times 2d}\)，可提前计算。它使用 SampleFz 算法从 \(R\) 上的离散高斯分布中采样。 算法 1 的复杂度为 \(\Theta(d^{2}n \log n)\) 标量运算（忽略对 \(\Sigma\) 的更新，其仅依赖于 \(T\) 且可在陷门生成时以 \(\Theta(d^{3}n \log n)\) 预计算），这是因为 \(P\) 中的乘法和 SampleFz 算法都需要 \(\Theta(n \log n)\) 时间。 定理 1 证明了该算法的正确性：设 \(T \in P^{2d \times dk}\)，\(\zeta, \alpha > 0\)，\(\Sigma_{p} = \zeta^{2}I - \alpha^{2} \begin{bmatrix} T \\ I \end{bmatrix} [T \ T \ I] \in P^{m \times m}\) 为导出的扰动协方差矩阵。若 \(\Sigma_{p} \succeq \eta_{\varepsilon}^{2}(\mathbb{Z}^{n m})\)，则 SamplePerturb\((T, \zeta, \alpha)\) 返回的向量 \(p \in R^{m}\) 的分布与 \(D_{R^{m},\sqrt{\Sigma_{p}}}\) 在统计上不可区分。 #### 3. 实现细节 为生成特定的离散高斯分布，我们使用以下构建块：基于 AES 的伪随机数生成器和类似于 Karney 采样器的 \(Z\) 上离散高斯采样器。选择该采样器是因为它能在常数时间内生成样本，且与中心、高斯参数和输出值无关。所有非整数计算使用不涉及次正规数的浮点运算。 陷门生成和 G - 采样的实现较为直接，下面重点介绍优化 SamplePerturb 算法的技术： - **使用中国剩余变换（CRT）**：在 \(P = R[X]/\langle X^{n} + 1 \rangle\) 中实现高效算术。CRT 是一种快速傅里叶变换，能在 \(\Theta(n \log n)\) 时间内计算多项式 \(f \in P\) 在复 \(2n\) 次单位根处的值。它与 SampleFz 算法结合良好，因为两者的递归结构相似。 - **预计算协方差矩阵值**：在 SamplePerturb 运行期间，不实际更新矩阵 \(\Sigma\)。而是在陷门生成时预计算算法执行过程中 \(\Sigma\) 会取的所有 \(2d\) 个值，并将它们“堆叠”存储在一个 \(2d \times 2d\) 的三角矩阵中。这样做的原因是在每次循环迭代中，\(\Sigma\) 是一个 \(i \times i\) 矩阵，我们只使用其最后一行和一列。这会在私钥中增加 \(d(2d + 1)\) 个 \(P\) 中的元素的存储成本，但在实际应用中能节省时间。 假设编译器为模 \(q\) 约简以及整数除法和乘法等基本操作生成常数时间代码，我们的实现是常数时间的。因为算法不需要依赖秘密值的分支或内存访问，特别是 \(Z