如何像Kyber/Dilithium一样精准枚举LWE密钥

# 如何像Kyber/Dilithium一样精准枚举LWE密钥 ## 1. LWE - Search运行时分析 ### 1.1 列表构建与内存消耗 使用经典的平方根复杂度Meet - in - the - Middle方法为大小为$S(d - 1)$的搜索空间构建$d$级列表。在$1\leq j\lt d$的层级上，枚举搜索空间大小$S(j)$的$\frac{1}{R(j)}$部分。列表大小计算公式如下： - $L(d)=\sqrt{S(d - 1)}$ - $L(j)=\frac{S(j)}{R(j)}$，其中$1\leq j\lt d$ 由于根列表$L(0)_1$可以即时构建且无需存储，总内存消耗$M = \max\{L(j)\}$。 ### 1.2 运行时间计算 设$r(d) = 0$，在$1\leq j\lt d$层级构建列表时，将两个大小为$L(j + 1)$的相邻列表$L(j + 1)_{2i - 1}$和$L(j + 1)_{2i}$在$r(j)-r(j + 1)$个坐标上匹配成一个列表$L(j)_i$，忽略低阶项（如排序），此操作时间为： $T(j)=\max\{L(j + 1),\frac{(L(j + 1))^2}{q^{r(j)-r(j + 1)}}\}$ 过滤掉$L(j)_i$中权重分布不正确的元素，得到列表大小$L(j)$。根列表$L(0)_1$通过Odlyzko的哈希函数在剩余$N - r(1)$个未匹配坐标上近似匹配两个大小为$L(1)$的一级列表得到，此操作时间为： $T(0)=\max\{L(1),\frac{(L(1))^2}{2^{N - r(1)}}\}$ 总运行时复杂度为： $T=\max\{T(0),\cdots,T(d - 1)\}$ ### 1.3 不同深度分析 分析了深度$d = 3$和$d = 4$的LWE - Search，运行时指数如下表所示： | d | log T(0) | log T(1) | log T(2) | log T(3) | log T(4) | log M | | --- | --- | --- | --- | --- | --- | --- | | 3 | 1.090N | 1.103N |.583N |.510N | - | 1.045N | | 4 | 1.090N | 1.103N |.605N |.405N |.320N | 1.045N | 可以观察到深度3已足够，因为深度4并未降低最大指数。 ### 1.4 定理1（Rep - 0） 在MLWE表示启发式下，设$(A, t)\in Z_q^{N\times N}\times Z_q^N$是一个$(M)LWE$实例，其中$q = \Omega(N)$，秘密密钥$s, e\sim B(3)N$（对于MLWE，$N = nk$），那么使用Rep - 0表示的LWE - Search能在$O(2^{1.103N})$时间内（以恒定概率）找到$s$。证明过程使用运行时公式计算了$T(0)$、$T(1)$、$T(2)$和$T(3)$，最终得出总运行时间为$\max T(j)=O(2^{1.103N})$。 ```mermaid graph TD; A[开始] --> B[构建d级列表]; B --> C[枚举1 ≤ j < d层级搜索空间]; C --> D[计算列表大小L(j)]; D --> E[计算内存消耗M]; E --> F[ ```