模块-LWE从模块-NTRU的熵硬度与对称密钥密码学新算法

### 模块-LWE从模块-NTRU的熵硬度与对称密钥密码学新算法 #### 模块-LWE的熵硬度相关研究 在模块学习误差（Module-LWE，简称M-LWE）问题的研究中，涉及到多个重要方面，包括其熵硬度的证明以及与其他相关问题的对比等。 1. **推论3的证明**：由于τ是双射，集合S和S′具有相同的熵。通过结合定理5和引理2可得到第一个陈述。对于第二个陈述，考虑有界分布。在M-LWE的实际应用中，通常对多项式的系数进行界定，所以会考虑对秘密的系数嵌入的无穷范数进行限制。为了使用引理2，需要将这个界限转换为S′中秘密在欧几里得范数下的界限。因为K是分圆域，可以选择$B_R = (U^{\dagger}HV)^{-1}$，这样就有$B_R\sigma_H = \tau$，从而满足定理5的要求$S′ = B_R\sigma_H(S)$。对于从S中采样的s，有$\|s′\|_2 = \|B_R\sigma_H(s)\|_2 = \|\tau(s)\|_2 \leq \eta\sqrt{nd}$，应用引理2即可得到第二个陈述。 2. **M-LWE的统计熵硬度**：当高斯分布$\psi = D_{R,\gamma}$足够宽，且q分解的因子不太多时，M-NTRU问题在统计上是困难的。具体定理如下： - 设K是次数为n的数域，R是其整数环，m, d ≥ 1，q是不分歧素数，且$\min_{p|qR, p\text{ prime}}N(p) = 2^{\Omega(n)}$，定义$N_{max} = \max_{p|qR, p\text{ prime}}N(p)$。当$\gamma \geq \max\{2nq^{m/(d + m) + 2/(n(d + m))}, 2^{1/(2d - 1)}|\Delta_K|^{1/n}N_{max}^{(d - 1)/(n(2d - 1))}\}$时，设$X_{\gamma}$是$GF_q^{-1} \bmod qR$的分布，其中$(F, G) \leftarrow D_{R,\gamma}^{d\times d} \times D_{R,\gamma}^{m\times d}$且$F \in GL_d(R, q)$，$F_q^{-1}$是F在$R_q$中的逆。则有$\Delta(X_{\gamma}, U(R_q^{m\times d})) \leq 2^{-\Omega(n)}$。 - 这一结果为熵M-LWE的温和硬度提供了统计上的证明，但参数γ大约为$2n\sqrt{q}$，使得M-LWE的参数在实际中难以使用。因为秘密分布的熵必须非常大，秘密和掩码噪声的大小至少为$\sqrt{q}$，这使得基于它构建可用的密码系统变得困难。所以该统计结果更多是理论证明的有趣副产品，而非实际应用中的突破性成果。 3. **相关工作对比**：为了简化参数的具体比较，使用2的幂次分圆域的情况和推论3的形式。 - **降维特性**：降维过程保持了模块秩，即M-NTRU假设中的模块秩等于熵M-LWE的最终模块秩。这对具体的硬度分析有优势，但在调整参数以实现小秘密方面的空间较小，无法实现均匀二进制秘密。 - **参数示例**：给出了一组满足推论3条件的参数示例，如下表所示： | n | d | m | q | γ | ε | s | η | s0 | |----|----|----|----|----|----|----|----|----| | 256 | 4 | 4 | 1105625551361 | 297 | 2⁻¹⁰⁰ | 11894537 | 4780 | 34450257913 | - **与其他结果的比较**：将结果与Lin等人的工作进行比较，需要对他们的结果进行一些修改以适应原始环和本文对M-LWE的定义。主要区别在于比较$k\log_2 q$和$d\log_2(nd\log_2 n)$，当γ低至n时，在某些参数范围内，本文的证明方法能得到稍优的参数。例如，当n = 256，q = n³，且k接近d时，在噪声和秘密大小方面能取得更好的参数。具体比较如下表： | 比较项 | [19] | 推论3 | |----|----|----| | 数域 | 任意 | 任意（推论3针对分圆域） | | 常数秘密 | 是 | 否 | | 保持秩 | 否 | 是 | | 硬度假设 | M - LWE$_{k,D_R,s_1