Solving LWE with Independent Hints about Secret and Errors — Lu, Feng, Pan (2025)

Reading: Lu, Feng, Pan (2025). Solving LWE with Independent Hints about Secret and Errors.

问题设定： 给定 LWE 实例 \((A, \mathbf{b} = \mathbf{s}A + \mathbf{e} \bmod q)\) 和一组精确的侧信道 hint（关于 \(\mathbf{s}\) 或 \(\mathbf{e}\) 的内积值），构造 primal attack 格基进行密钥恢复。

本文的改进： 将 Nowakowski-May (ASIACRYPT 2023) 嵌入 hint 时使用的 LLL 约简替换为 Hermite 标准型（HNF）——一个多项式次数更低的整数线性代数操作。Kyber512 上 234 个完美 hint 的基构造从 2.16 小时降至 0.35 小时。格基维度与行列式与 MN23 等价，对完美 hint 行列式略有增大。

本笔记关注： (1) 构造链——hint 转为 lattice hint 后如何通过矩阵乘法嵌入 primal attack 格基；(2) HNF 比 LLL 快在哪——多项式次数的差距及其工程含义；(3) 论文未说但值得追问的部分——带噪 hint、联合 hint、attack pipeline 完整评测的缺失。

1. 从「证明安全」到「攻击模型」：Hint 攻击的学术路线

1.1 预设知识

本笔记假设读者已熟悉 primal attack 格基（详见 lattice-part-9）的构造与 BKZ block-size 估计：

Gaussian heuristic 预测 \(\lambda_1\) 与 \(\|\boldsymbol{\tau}\|\) 的 gap 决定攻击所需 BKZ block size \(\beta\)。Hint 的作用是缩小这个 gap——缩减维度或增大行列式——从而降低 \(\beta\)。

1.2 Hint 模型的动机：侧信道与代数泄漏

物理实现的侧信道（功耗、时序、电磁）给出的是关于密钥的 额外代数约束。 在 LWE 设定下，这典型地表现为关于 \(\mathbf{s}\) 或 \(\mathbf{e}\) 的部分内积信息：

• 完美 hint： \(\langle \mathbf{v}, \mathbf{s} \rangle = \ell\)（精确整数值）。
• 模 q hint： \(\langle \mathbf{v}, \mathbf{s} \rangle \equiv \ell \pmod{q}\)。
• 模任意数 hint： \(\langle \mathbf{v}, \mathbf{s} \rangle \equiv \ell \pmod{m}\)。

这些 hint 的来源可以是多样化的：模板攻击恢复出的单个系数的 Hamming weight（经过一些代数处理后变成内积约束），乘法运算中的中间值泄漏，或者冷启动攻击中恢复出的部分密钥字节。 本文不讨论 hint 的来源，而是假设已经拥有了一组代数上精确的 hint，然后回答：有了这些信息后，如何最快地构造出能够恢复剩余未知部分的格基？

1.3 攻击路线的演化（关键节点）

• DSDGR20 (CRYPTO): 奠基性统一框架。将 hint 作为等式约束嵌入 DBDD 格基，每个 hint 增加一行一列，缩小 uSVP gap。局限：需要大量 hint 才能显著改善攻击参数；嵌入经过对偶格基，对 primal attack 的影响间接。
• DSGHK23 (CRYPTO): 引入不等式 hint（\(\langle \mathbf{v}, \mathbf{s} \rangle \in [L, U]\)），提供更几何化的 gap 分析框架。
• MN23 (ASIACRYPT): 突破性节点。直接嵌入 LWE 实例而非 DBDD，维度增长更小，统一处理完美和 modular hint。核心工具是 LLL——给定 hint 后，将 hint 矩阵与 LWE 格基组合成一个更大的矩阵，用 LLL 约简提取等效格基。缺陷：hint 数量增加时（如 Kyber512 的 200+ 个 hint），LLL 本身成为瓶颈。
• LFP25 (本文): 拒绝 LLL。用 HNF 将 hint 转换为 compact 核格基，通过矩阵乘法嵌入 primal attack 格基。全程只有整数矩阵运算——HNF、乘法、求逆、高斯消元——没有格约简。
• HSMP25 (EUROCRYPT): 平行的泛化框架，覆盖更多泄漏模型（含带噪泄漏）。在宽度上扩展，Lu 等人在深度（构造效率）上优化。
• Belief propagation 路线: 用统计推断处理带噪软信息。与 lattice reduction 线（擅长精确值泄漏）各有侧重，未来大概率收敛。

2. Lattice Hint：用格的语言描述侧信息

2.1 一个统一的观察

几乎所有的 LWE hint——不论是关于 \(\mathbf{s}\) 还是 \(\mathbf{e}\)——都可以被重新表述为：

有一个格 \(L\)，我们已知 secret（或 error，或其拼接）属于这个格。

这个观察看似 trivial，但它将 hint 从散落的线性等式提升为统一的代数对象。 一旦你接受这个视角，嵌入问题就变成了一个纯粹的格操作问题：如何将两个格基组合，使得新格基包含原 LWE 格的所有信息，同时嵌入了 hint 格的约束。

Lattice Hint (Formal Definition). 一个 lattice hint 是有序对 \((B, \text{target})\)，其中 \(B\) 为整数矩阵，\(\text{target} \in \{ \mathbf{s}, (\mathbf{s}, -1), \mathbf{e}, (\mathbf{e}, -1) \}\)，满足 target 属于 \(L(B)\)。

2.2 转化规则

齐次 hint：\(\mathbf{s}V = 0\)（整系数或模 \(q\)）。 所有满足这个等式的 \(\mathbf{s}\) 构成一个整数格。 求这个格的基 \(B_s\)，则有 \(\mathbf{s} \in L(B_s)\)。

非齐次 hint：\(\mathbf{s}V = \boldsymbol{\ell}\)。 通过将常数项吸收进变量：

转化成了关于 \((\mathbf{s}, -1)\) 的齐次形式。 因此 \((\mathbf{s}, -1) \in L(B_{(\mathbf{s}, -1)})\)， 其中 \(B_{(\mathbf{s}, -1)}\) 是上述齐次系统的核格基。

多个 modular hint：\(\langle \mathbf{v}_i, \mathbf{s} \rangle \equiv \ell_i \pmod{m_i}\)。 每个 hint 定义一个格 \(L_i\)，所有格的交集仍是格。 因此 \((\mathbf{s}, -1) \in \bigcap_{i=1}^k L(B_i)\)。

2.3 HNF 求核格基

问题的核心变成了：给定一个整数矩阵 \(V \in \mathbb{Z}^{n \times k}\)，如何高效地求出 \(\{\mathbf{s} \in \mathbb{Z}^n \mid \mathbf{s}V = 0\}\) 的格基。

最自然的方法是通过 Smith 标准型或 Hermite 标准型。 HNF 给出幺模矩阵 \(U \in \mathbb{Z}^{n \times n}\) 使得

其中 \(H\) 是 \(V\) 的上三角 HNF，且后 \(n-k\) 行全为零（因为 \(V\) 是 \(n \times k\) 且通常列满秩，只有 \(k\) 个独立约束）。 因此 \(U\) 的后 \(n-k\) 行就是核格 \(B_s\) 的一组基。

对这个公式，我们需要一个关键的观察：\(U\) 是幺模矩阵。 这意味着它定义了一个 \(\mathbb{Z}^n\) 上的基变换。 将 \(V\) 的列向量在这个新基下重新表示，就自然把零空间分离出来了——这正是 HNF 的代数本质。

对于非齐次情况，先求任意一个特解 \(\mathbf{s}_0\) 满足 \(\mathbf{s}_0 V = \boldsymbol{\ell}\)， 然后所有满足 \(\mathbf{s}V = \boldsymbol{\ell}\) 的向量构成仿射空间 \(\mathbf{s}_0 + L(B_s)\)。 因此

2.4 复杂度分析：为什么 HNF 赢

这是全文的理论分水岭。 我们来对比两者的渐近复杂度：

• LLL（May-Nowakowski 用的工具）：\(\widetilde{O}(n^5 k \log^3 B)\)。 这里 \(n\) 是输入维度（secret 维度），\(k\) 是 hint 数量，\(B\) 是矩阵元素的最大绝对值。 \(n^5\) 因子意味着当 \(n\) 达到数百（正是 Kyber 和 Dilithium 所在的区域）时，即使 \(k\) 很小，LLL 的运行时间也可能迅速膨胀。

• HNF（论文用的替代方案）：\(\widetilde{O}(n k^3 \log^2 B)\)。 注意这里的指数分布完全不同：\(n\) 的幂次从 \(5\) 降到了 \(1\)，\(k\) 的幂次保持在 \(3\)。 在典型的侧信道攻击场景下——\(n \approx 256\text{--}1024\)，\(k \ll n\)（通常几十到几百个 hint）——HNF 的多项式次数是压倒性的优势。

更具体地说，当 \(n=256, k=128\) 时，\(n^5 k \approx 2.7 \times 10^{14}\)，而 \(n k^3 \approx 5.3 \times 10^8\)——差了 六个数量级。 即使在常数因子上 LLL 的实现可能更优化（由于几十年的工程积累），这个多项式差距也是 LLL 无法追赶的。

Note: 在 MN23 的框架中，LLL 并非攻击的核心计算瓶颈（BKZ 通常更重），但它成为了 基构造 的瓶颈。 即使 BKZ block size 很小，也需要先在 LLL 上等两个小时才能开始真正的 attack——基构造工具与攻击需求之间的不匹配。

3. Secret Hint 的嵌入：分块矩阵与行列式分析

这一节展开论文最核心的三条构造链：一般嵌入公式、完美 hint 的特化、mod-q hint 的特化。 每条链都从一个 lattice hint 出发，以一个新的 primal attack 格基结束。

3.1 一般嵌入公式

一旦有了 lattice hint \(B_s\) 使得 \(\mathbf{s} \in L(B_s)\)（即存在 \(\mathbf{z}\) 使 \(\mathbf{s} = \mathbf{z}B_s\)）， 我们可以直接将 \(\mathbf{s} = \mathbf{z}B_s\) 代入 LWE 定义式 \(\mathbf{b} = \mathbf{s}A + \mathbf{e} + q\mathbf{k}\)：

这个 \(B_s^{\mathrm{LWE}}\) 就是我们的新 primal attack 格基。 它本质上是用 \(B_s\) 对 \(A\) 做了一次行空间的线性变换——将 \(n\) 维的 secret 空间压缩到了 \(n-k\) 维（因为 \(B_s\) 是 \((n-k) \times n\) 的矩阵）。

对于非齐次情况 \((\mathbf{s}, -1) \in L(B_{(\mathbf{s}, -1)})\)，构造更为紧凑。 令 \(\overline{A} = \begin{pmatrix} A \\ \mathbf{b} \end{pmatrix}\)（将 \(\mathbf{b}\) 叠在 \(A\) 下方），则

一个很有用的视角：\(B_{(\mathbf{s}, -1)} \overline{A}\) 这个乘积同时处理了 \(A\) 和 \(\mathbf{b}\)， 不需要像 Case 1 那样分三行处理。 这是因为 \((\mathbf{s}, -1)\) 天然地耦合了 secret 和常数项，使得 LWE 方程 \(\mathbf{b} - \mathbf{s}A = \mathbf{e} \pmod{q}\) 可以直接写为 \((\mathbf{s},-1) \overline{A} = -\mathbf{e} \pmod{q}\)。

3.2 完美 hint 的特化（九步推导链）

这是论文中最干净的一条构造链。 我们逐步展开，既呈现公式也解释每一步的代数理由。

场景设定： 已知 \(k\) 个完美整数 hint：\(\mathbf{s}V = \boldsymbol{\ell}\)，其中 \(V \in \mathbb{Z}^{n \times k}\)， \(\boldsymbol{\ell} \in \mathbb{Z}^k\)。

Step 1 —— 求核格基 \(B_s\)。 计算 \(V\) 的 HNF。 存在幺模 \(U \in \mathbb{Z}^{n \times n}\) 使得 \(UV = H\)， \(H\) 的后 \(n-k\) 行全零。 取 \(U\) 的后 \(n-k\) 行组成 \(B_s \in \mathbb{Z}^{(n-k) \times n}\)。

这一步的 key insight 是：HNF 不需要约简质量，它只需要矩阵的标准形。 不需要 shortest basis，只需要 any basis——因为我们用这组基的目的是在下一步嵌入 LWE 格基，而 BKZ 会在最终的格基上完成约简工作。

Step 2 —— 求特解 \(\mathbf{s}_0\)。 从 \(k\) 个线性方程中解出一个满足 \(\mathbf{s}_0 V = \boldsymbol{\ell}\) 的特解。 因为 \(V\) 的秩为 \(k\)（hint 向量线性无关——否则有冗余 hint 可以先剔除），任意特解都可以。

Step 3 —— 参数化所有满足 hint 的 secret。 这是线性代数的标准结论：齐次方程的所有解构成一个线性空间（格），加上一个特解后成为一个仿射空间：

此时 \(\mathbf{z}\) 是新的「未知量」——维度从 \(n\) 降到了 \(n-k\)，但系数的取值范围从 \(\mathbb{Z}_q\) 变成了 \(\mathbb{Z}\)（因为没有模约简，hint 是精确的整数等式）。

Step 4 —— 构造 \(B_{(\mathbf{s}, -1)}\)。

底行的 \(-1\) 编码了 \((\mathbf{s}, -1)\) 中 \(-1\) 分量恒为常数的约束。 验证 \((\mathbf{s}, -1) = (\mathbf{z}, 1) B_{(\mathbf{s}, -1)}\) 成立。

Step 5 —— 嵌入 LWE 格基。 将 \(B_{(\mathbf{s}, -1)}\) 代入 Case 2 的嵌入公式：

注意底行 \(\mathbf{b} - \mathbf{s}_0 A\) 是 「使用特解 \(\mathbf{s}_0\) 作为近似 secret 时对应的 adjusted \(\mathbf{b}\)」。 这意味着我们将 \(\mathbf{b}\) 中已知的部分（由 \(\mathbf{s}_0\) 贡献的部分）从系统中扣除， 剩下待恢复的是 \(\mathbf{z}\) 对应的残差分量。

Step 6 —— 维度分析。

每个完美 hint 从系统中消除了一个自由度（将 \(n\) 维 secret 的搜索空间缩小了一维）， 因此最终的格基维度从原始的 \(m+n+1\) 降到 \(m+n+1-k\)。 这等价于 MN23 中处理方法得到的维度——在这个指标上两者相同。

Step 7 —— 行列式与几何分析。 \(B_s\) 不是方阵，所以行列式需要从几何角度分析。 将基的前 \(m+n-k\) 行张成的子格记为 \(L_{\mathrm{sub}}\)。 底行 \((\mathbf{b} - \mathbf{s}_0A, -\mathbf{s}_0, 1)\) 在垂直于 \(L_{\mathrm{sub}}\) 的方向上的投影给出

Key Observation. \(\|\mathrm{proj}_{\perp}\| \ge 1\) 严格成立：投影向量的分量均为整数，在整数格的垂直投影方向上，任何非零整数向量的投影长度至少为 \(1\)（它是格本身的初等体积的约化因子）。

而在 MN23 中，相应的行列式为 \(\det(L_{\mathrm{sub}})\)（没有 \(\|\mathrm{proj}_{\perp}\|\) 因子）。 因此：

对于 primal attack，行列式越大越好——Gaussian heuristic 预测的最短向量长度 \(\propto \det^{1/d}\)， 而行列式增加意味着 lattice 的「稀疏度」增加，使 target vector 更「突出」。

所以对于完美 hint，Lu 等人的方法不仅在构造速度上优于 MN23，在基的 攻击质量上也有优势：相同维度，更大行列式。

Step 8 —— 与 MN23 在完美 hint 场景下的对比。

Step 9 —— 直觉总结。 整个完美 hint 的构造链可以理解为：用 \(k\) 个线性方程将 \(n\) 维 secret 空间压到 \(n-k\) 维超平面上，然后将这个超平面作为一个格嵌入 LWE 实例中。 过程中唯一「非平凡」的操作是 HNF（求出超平面的基底），其余全是矩阵乘法和加法。

3.3 Mod-q hint 的特化（九步链）

完美 hint 是强的：它要求攻击者知道精确的整数值。 更现实的情况是模 \(q\) 下的等价类信息——模 \(q\) hint \(\mathbf{s}H \equiv \boldsymbol{\ell} \pmod{q}\)。

Step 1 —— 转化。 将模等式转为 \(\mathbb{Z}\) 上的齐次形式：

此时 \(\mathbf{s} = \mathbf{s}_0 + \mathbf{z}B_s\)，其中 \(B_s\) 是 \(\mathbf{s}H \equiv 0 \pmod{q}\) 的核格基。

Step 2 —— 假设与分块。 假设 \(k\) 个 hint 向量线性无关模 \(q\)。 则存在 \(k \times k\) 可逆子块。 重新排列 \(\mathbf{s}\) 的坐标，使前 \(k\) 个坐标对应的 \(k \times k\) 子矩阵 \(H_0\) 可逆：

Step 3 —— 构造核格基 \(B_s\)。 从 \(\mathbf{s}_k H_0 + \mathbf{s}_{n-k} H_1 \equiv 0 \pmod{q}\;\text{解出}\;\mathbf{s}_k \equiv -\mathbf{s}_{n-k} H_1 H_0^{-1} \pmod{q}\)。这意味着前 \(k\) 个坐标由后 \(n-k\) 个坐标模 \(q\) 决定，但可以在 \(\mathbb{Z}\) 上自由变化 \(q\) 的倍数。 因此核格基是一个 \((n) \times n\) 的矩阵：

注意这里 \(B_s\) 是方阵（维度 \(n \times n\)），与前一种情形 \(B_s\) 是 \((n-k) \times n\) 不同。 这是因为模 \(q\) 约束不压缩维度——它只将前 \(k\) 维锁定为后 \(n-k\) 维的模 \(q\) 线性函数。

Step 4 —— 划分 \(A\)。 按照 \((k, n-k)\) 的分块：

其中 \(A_{11} \in \mathbb{Z}_q^{k \times k}, A_{12} \in \mathbb{Z}_q^{k \times (m-k)}, A_{21} \in \mathbb{Z}_q^{(n-k) \times k}, A_{22} \in \mathbb{Z}_q^{(n-k) \times (m-k)}\)。

Step 5 —— 构造 \(B_{q,H_s}^{\mathrm{LWE}}\)（\(5 \times 5\) 分块矩阵）。 将 \(B_s\) 和分块的 \(A\) 代入 Case 1 嵌入公式（此时 \(\mathbf{s} \in L(B_s)\)），得到论文中最复杂的单个公式：

这个矩阵看起来吓人，但它的块结构有清晰的逻辑：

• 前两行 \((qI_k, 0, \ldots)\) 和 \((0, qI_{m-k}, \ldots)\) 编码模 \(q\) 关系。
• 第三行 \((qA_{11}, qA_{12}, qI_k, \ldots)\) 来自 \(B_s A\) 乘积的前 \(k\) 行。
• 第四行 \((\widetilde{A}_0, \widetilde{A}_1, -H_1 H_0^{-1}, I_{n-k}, 0)\) 来自 \(B_s A\) 的后 \(n-k\) 行和 \(B_s\) 自身的下半部分。
• 第五行来自 \(\mathbf{b}\) 和 \(\mathbf{s}_0\)。

Step 6 —— 行变换消去。 用第一行消去第三行中的 \(qA_{11}\) 部分，用第二行消去第三行中的 \(qA_{12}\) 部分。 这是完全合法的格基变换（行变换对应左乘幺模矩阵，不改变格）：

Step 7 —— 消去冗余列，降维。 \(B_1\) 的第 \(m+1\) 至 \(m+k\) 列（对应 \(qI_k\)）只包含 \(q\) 的倍数。 因为 BKZ 在格上操作时不依赖特定的列排列， 这些列与它们的行可以在不影响格结构的情况下被消去：

维度从 \(m+n+k+1\) 降到了 \(m+n+1-k\)，与 MN23 一致。

Step 8 —— 行列式。 \(\det(B_{q,H_s}^{\prime\mathrm{LWE}}) = q^m\)，与原始 LWE 格基相同。 这与 MN23 一致。

Step 9 —— 恢复被消去的 \(\mathbf{s}_k\)。 BKZ 恢复出 \((\mathbf{e}, \mathbf{s}_{n-k}, -1)\) 后，\(\mathbf{s}_k\) 可以通过模等式反推：

这一步不需要额外的格操作。

3.4 Mod-q hint 对比总结

对于模 \(q\) hint，Lu 等人的方法与 Nowakowski-May 在格基的维度、行列式、和攻击质量上完全等价。 差异在构造速度上——HNF 替代了 LLL。 因为维度相同、行列式相同，这 5-7 倍的加速是纯粹工程上的收益，不影响攻击的可行性条件。

3.5 一个容易被忽略的细节：\(H_0\) 的可逆性

在模 \(q\) hint 的构造中，\(H_0\) 的可逆性假设是关键的。 如果 hint 向量集合恰好不能形成 \(k \times k\) 可逆子块， 行列置换后总可以找到一个可逆子块（因为 hint 向量是线性无关的），但这意味着需要重新排列 \(\mathbf{s}\) 的坐标——在实际的 SageMath 实现中需要处理这个置换。

如果 hint 向量线性相关呢？ 此时 \(H\) 的秩小于 \(k\)，表示有冗余 hint。 可以预处理：求出最大无关 hint 组，丢弃多余的。 这个预处理可以用高斯消元在 \(O(nk^2)\) 时间内完成，不会成为瓶颈。

4. Error Hint 的嵌入：三变量线性系统

4.1 前置：Secret 嵌入后的基

在 secret hint 嵌入完成后（§3 的输出），我们拥有一个形如

的格基，且存在整数向量 \((\mathbf{k}, \mathbf{z}, -1)\) 满足

将矩阵乘法展开为分量等式：

第一个等式是我们处理 error hint 的起点：它把 \(\mathbf{e}\) 表示成了两个自由变量 \(\mathbf{k}\)（mod-\(q\) 消去向量，每一条 LWE 样本对应一个自由度） 和 \(\mathbf{z}\)（secret 的参数化系数）的线性组合。

4.2 三变量系统：\((\mathbf{k}, \mathbf{z}, \mathbf{w})\) 的来源

现在引入 error hint。以 Case 1 为例：已知整数矩阵 \(B\) 使得 \(\mathbf{e} \in L(B)\)。 这意味着存在整数向量 \(\mathbf{w}\) 满足 \(\mathbf{e} = \mathbf{w}B\)。

将 \(\mathbf{e} = \mathbf{w}B\) 代入 \(-\mathbf{e} = q\mathbf{k} + \mathbf{z}T - \mathbf{t}\)：

三变量线性系统。 方程 \(q\mathbf{k} + \mathbf{z}T + \mathbf{w}B = \mathbf{t}\) 包含三个未知块： \(\mathbf{k}\)（长度 \(m\)，编码每条 LWE 样本的模 \(q\) 自由量）、 \(\mathbf{z}\)（长度取决于 secret hint 的数量，编码 \(\mathbf{s}\) 的参数化）、 \(\mathbf{w}\)（长度取决于 error hint 容器的维度，编码 \(\mathbf{e}\) 的参数化）。

相比之下，§3 的 secret hint 嵌入中只有 \(\mathbf{z}\) 一个变量。 这额外的两个变量——\(\mathbf{k}\) 和 \(\mathbf{w}\)——使得 error hint 嵌入的代数复杂度高出一个小阶。

4.3 Case 1：\(\mathbf{e} \in L(B)\) —— 五步构造

Step 1 —— 整理方程。 令齐次部分为 \(q\mathbf{k} + \mathbf{z}T + \mathbf{w}B = 0\)， 则原方程是它的一个非齐次偏移（右端是 \(\mathbf{t}\)）。

Step 2 —— 求齐次核格基。 求解齐次线性系统 \(q\mathbf{k} + \mathbf{z}T + \mathbf{w}B = 0\)，得到核格基 \((K, Z, W)\)。 \(K\) 的行数（核的维数）决定了最终格基的行数。 这一步可以用整数线性代数（高斯消元或 HNF）完成——不涉及格约简。

Step 3 —— 求特解。 找一个特解 \((\mathbf{k}_0, \mathbf{z}_0, \mathbf{w}_0)\) 满足整方程 \(q\mathbf{k}_0 + \mathbf{z}_0 T + \mathbf{w}_0 B = \mathbf{t}\)。 因为方程是线性且一致（hint 来自真实 secret/error，一定存在解），特解总是存在的。

Step 4 —— 参数化 \((\mathbf{k}, \mathbf{z})\)。 所有解可写为

其中 \(\boldsymbol{\omega}\) 是新的自由整数向量（维度等于核的维数）。 由此提取出最终需要的 \((\mathbf{k}, \mathbf{z})\) 部分：

Step 5 —— 乘回 \(B_s^{\mathrm{LWE}}\)，得到最终的 primal attack 基。

注意最末行的 \(-1\) 保持完整——确保 target vector \((-\mathbf{e}, \mathbf{s}, -1)\) 在新基中仍以 \((\boldsymbol{\omega}, 1)\) 的整数组合形式存在。构造全程只用矩阵乘法、HNF（核格求解）、和加减法——无 LLL 参与。

4.4 Case 2：\((\mathbf{e}, -1) \in L(\overline{B})\) —— 仅符号变化

当 lattice hint 的目标是 \((\mathbf{e}, -1)\) 而非单独的 \(\mathbf{e}\) 时， 使用 \(\overline{B}\) 表示该 hint 的格基。记 \(\overline{B}'\) 为 \(\overline{B}\) 的前 \(m\) 列（提取 \(\mathbf{e}\) 的坐标部分）。

从 \((\mathbf{e}, -1) = \mathbf{w}\overline{B}\) 得 \(\mathbf{e} = \mathbf{w}\overline{B}'\)。 代入 \(-\mathbf{e} = q\mathbf{k} + \mathbf{z}T - \mathbf{t}\)：

与 Case 1 的方程 \(q\mathbf{k} + \mathbf{z}T + \mathbf{w}B = \mathbf{t}\) 相比， 唯一的差异是 hint 矩阵从 \(B\) 换成了 \(\overline{B}'\)， \(\mathbf{w}\) 项的符号保持不变（都是 \(+\)，因为我们消去了 \(-\mathbf{e}\) 与 \(-\mathbf{w}\overline{B}'\) 之间的负号）。 后续的核格求解、特解、参数化、和矩阵乘法步骤与 Case 1 完全相同：

本质上，Case 2 是 Case 1 的「把 \(\mathbf{e}\) 改写成 \((\mathbf{e}, -1)\) 的格成员关系」的语法变形， 不引入额外的代数结构。

4.5 嵌入成本与边际收益

与 secret hint 嵌入相比，error hint 嵌入的核心额外开销是求解三变量线性系统。 这一步仍然是整数线性代数（HNF / 高斯消元），不是格约简——因此额外开销是多项式级别的， 随 hint 数量多项式增长而非指数增长。

但从攻击者的角度，一个更实际的问题是边际收益。 每个 hint（不论是关于 \(\mathbf{s}\) 还是 \(\mathbf{e}\)）消去一个自由度，格基维度减 1， 行列式不变，Gaussian heuristic 预测的 \(\lambda_1 \propto \det^{1/(d-1)}\) 略微增大——有助于攻击。 然而 \(\mathbf{e}\) 在许多 LWE 参数选择中比 \(\mathbf{s}\) 更短， \(\mathbf{e}\) 自身的短向量属性在 BKZ 阶段已经构成自然优势。 因此从 \(\mathbf{e}\) 中消去自由度的边际改善可能不如从 \(\mathbf{s}\) 中消去来得大。 这本质上是一个实验问题——论文没有提供 \(\mathbf{s}\)-only 与 \(\mathbf{e}\)-only hint 的对比攻击数据。

4.6 独立假设的局限

论文框架要求每个 hint 只涉及 \(\mathbf{s}\) 或 \(\mathbf{e}\) 之一， 不处理形如 \(\langle \mathbf{v}_s, \mathbf{s} \rangle + \langle \mathbf{v}_e, \mathbf{e} \rangle = \ell\) 的联合 hint。 这个限制是构造性的——一旦 hint 同时涉及两者， lattice hint 的 target 就无法简单设为 \(\mathbf{s}\) 或 \(\mathbf{e}\) 之一， 对应的三变量线性系统也会退化为不同形式。

在实际攻击中，许多侧信道泄漏确实只涉及一方（例如 Kyber 加密中只有 \(\mathbf{s}\) 参与多项式乘法）。 但解密过程的模板攻击可能同时恢复两方的部分信息。 处理联合 hint 需要更一般的格基构造方法——这是本路线的一个自然延伸方向。

5. 实验与数据分析

5.1 实验设置

所有实验在 SageMath 10.3 上运行，MacBook Pro M1，最高 CPU 频率 3.2 GHz。 对比基准是 Nowakowski & May (2023) 的方法在相同参数下的实现。

需要注意的一点是：MN23 的原始实现未必是针对 hint 大量场景优化的——如果对 MN23 的代码做工程优化（例如使用更好的 LLL 实现、或针对 hint 矩阵的特殊结构做预处理），LLL 的绝对运行时间可能有所下降。 但多项式级别的差距（\(n^5\) vs \(n^1\)）不会因为常数因子优化而消失——这正是理论分析的价值所在。

5.2 Kyber512 数据

5.3 Falcon512 数据

5.4 趋势分析

几条值得注意的观察：

加速比的非单调性。 在 Kyber512 上，128 hints 的加速比（7.21×）优于 234 hints（6.26×）。 Falcon512 上同样的模式。 这暗示 HNF 的 \(k^3\) 因子在 hint 数量很大时开始显现——当 \(k\) 从 128 增长到 234（约 1.8×），\(k^3\) 增长约 6×，但 LLL 的 \(n^5 k\) 中 \(k\) 是线性的。 所以加速比在 \(k\) 的中等区间达到峰值，之后 HNF 的相对优势略微缩小。 这并不意味着 HNF 变慢了——它的绝对时间仍然远小于 LLL——只是 LLL 在这个区间「追回」了一些。

Falcon512 的加速比整体低于 Kyber512。 Falcon 的 secret 分布和维数参数与 Kyber 不同，这可能影响 LLL 在 MN23 中的内部行为（LLL 的性能高度依赖输入基的「质量」和结构）。 但在所有测试点上 HNF 方法都保持了显著的速度优势。

234 hints 场景的绝对时间对比。 MN23 在 Kyber512 上用了 2.16 小时——仅仅是为了构造格基，还没有开始 BKZ。 而 Lu 等人的方法只需 20.7 分钟。 在实际攻击的 pipeline 中（包括 BKZ 的后续阶段），这近两个小时的节省可能意味着攻击的可行性差异——特别是在需要重复运行（尝试不同的 hint 组合、或者验证 hint 的正确性）的场景下。

5.5 实验报告的局限

实验仅报告了基构造时间，没有报告：

• BKZ 阶段的运行时间。 基构造完成后，实际攻击仍需要运行 BKZ（block size \(\beta\) 由 target vector 和 Gaussian heuristic 的 gap 决定）。 如果 BKZ 阶段的运行时间是 \(2^{0.292\beta}\)，基构造的 2 小时对 20 分钟的差异在 \(\beta\) 较大时可能被 BKZ 的运行时间淹没。 但对于 \(\beta\) 较小的情况（hint 很多时 \(\beta\) 降低），基构造时间的差异就更显著。

• 内存消耗。 HNF 的峰值内存使用可能与 LLL 不同——这对于在有限资源上运行大规模实验的用户很重要。

• 数值精度。 LLL 通常在浮点近似下运行（\(L^2\) 或 floating-point LLL），而 HNF 是精确的整数运算。 精确运算在大数系数下可能产生大的多精度整数，影响实际运行时间。

6. 代码架构（实现正在落实）

这一节是 API 签名和模块结构的占位——实际的 SageMath/Python 实现将在后续版本中填充。

6.1 模块树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

lwe_hints/
  __init__.py
  lwe_instance.py          # A, b, q, dimension, validation
  lattice_hints.py         # hint → lattice hint 的转换
  hnf_kernel.py            # HNF 核格求解与整数线性代数
  secret_embedding.py      # B_s^LWE 和 B_(s,-1)^LWE 的构造
  error_embedding.py       # secret 嵌入后的 error hint 嵌入
  primal_attack.py         # BKZ/LLL 编排与向量验证
  estimates.py             # 行列式、Gaussian heuristic、目标范数、beta 估计
  experiments.py           # 复现计时实验

6.2 核心数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

from dataclasses import dataclass
from typing import Literal

# Matrix 和 Vector 类型别名在实际实现中使用 SageMath 的 Matrix 或 numpy

@dataclass
class LWEInstance:
    """LWE 实例 (A, b = sA + e mod q)。"""
    A: 'Matrix'       # n × m 在 Z_q 上
    b: 'Vector'       # 长度 m 在 Z_q 上
    q: int
    n: int
    m: int

@dataclass
class PerfectHint:
    """完美 hint ⟨v, s⟩ = ℓ。"""
    v: 'Vector'       # 长度 n
    ell: int

@dataclass
class ModQHint:
    """模 q hint ⟨v, s⟩ ≡ ℓ (mod q)。"""
    v: 'Vector'
    ell: int
    q: int

@dataclass
class ModularHint:
    """模 m hint ⟨v, s⟩ ≡ ℓ (mod m)。"""
    v: 'Vector'
    ell: int
    modulus: int

@dataclass
class LatticeHint:
    """Lattice hint：目标向量属于 L(B)。"""
    B: 'Matrix'
    target: Literal["s", "s_minus_one", "e", "e_minus_one"]

6.3 主要函数 API

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

# ---- lattice_hints.py ----

def lattice_hint_from_perfect_secret_hints(V, ell):
    """
    将完美 hint sV = ℓ 转换为 lattice hint。

    Input:
        V:  n × k 整数矩阵（hint 向量）
        ell: 长度 k 的整数向量（目标值）

    Output:
        Bs: (n-k) × n 核格基，{s | sV = 0} = L(Bs)
        s0: 特解 s0·V = ell
        B_s_minus_one: (n-k+1) × (n+1) 基，(s,-1) ∈ L(B_s_minus_one)
    """
    # 实现正在落实
    pass


# ---- secret_embedding.py ----

def embed_secret_s_in_lattice(A, b, q, Bs):
    """
    构造 B_s^LWE：s ∈ L(Bs) 的情况。

    Input:
        A:  n × m (Z_q)
        b:  长度 m (Z_q)
        q:  模数
        Bs: (n-k) × n 核格基

    Output:
        B_s_LWE: (m+n-k+1) × (m+n-k+1) 格基
    """
    # 实现正在落实
    pass


def embed_secret_s_minus_one_in_lattice(A, b, q, B_s_minus_one):
    """
    构造 B_(s,-1)^LWE：(s,-1) ∈ L(B_s_minus_one) 的情况。
    """
    # 实现正在落实
    pass


# ---- hnf_kernel.py ----

def construct_Bs_from_modq_hints(H, q):
    """
    从模 q hint sH ≡ 0 (mod q) 构造 Bs。

    假设 H = [H0; H1] 且 H0 在 Z_q 上可逆。
    返回 Bs = [[q I_k, 0], [-H1·H0^{-1}, I_{n-k}]]。
    """
    # 实现正在落实
    pass


def recover_eliminated_secret_part(sn_minus_k, H1, H0_inv, ell):
    """
    从 BKZ 恢复的 s_{n-k} 反推 s_k：
        s_k ≡ -s_{n-k}·H1·H0^{-1} + ell·H0^{-1}  (mod q)
    """
    # 实现正在落实
    pass


# ---- error_embedding.py ----

def embed_error_hint_e_in_L(B_secret, B_error):
    """
    在 secret hint 嵌入后嵌入 error hint：e ∈ L(B_error)。
    """
    # 实现正在落实
    pass


def embed_error_hint_e_minus_one_in_L(B_secret, B_error_bar):
    """
    在 secret hint 嵌入后嵌入 error hint：(e,-1) ∈ L(B_error_bar)。
    """
    # 实现正在落实
    pass


# ---- primal_attack.py ----

def validate_recovered_vector(v, A, b, q, hints):
    """
    验证 BKZ 恢复的候选向量：
    1. 形状与 (-e, s, -1) 或约简形式兼容
    2. 最后一个坐标为 ±1
    3. 恢复的 s 满足 b ≡ sA + e (mod q)
    4. s 和 e 范数符合期望分布
    5. 所有输入 hint 被满足
    """
    # 实现正在落实
    pass

7. 贡献、局限与后续方向

7.1 贡献

MS23 的 LLL 嵌入方法在 hint 数量增加时，基构造本身成为瓶颈——LLL 的 \(\widetilde{O}(n^5 k)\) 与本应受益的其他攻击阶段不成比例。

Lu 等人的核心洞察：hint 是一组精确的线性约束，其解空间是一个可以用整数线性代数——而非格约简——计算的格。 接受这一点后，构造链退化为 HNF 求核格基、矩阵乘积做嵌入、高斯消元做降维。每步的代数依据都是标准的整数线性代数。

实验上 5–7× 的加速是实质性的。Kyber512 在 234 个完美 hint 下基构造从 2.16 小时降至 20.7 分钟——从「需要专门规划计算资源」到「笔记本上可运行」的粒度切换。

7.2 局限

（a）精确 hint 假设。 论文假设 hint 完全精确。真实侧信道 hint 通常带噪声。HNF 对错误等式不具有容错性——一个错误 hint 会将格基推向错误方向。需要额外的预处理层（belief propagation 或多次采样与投票）来过滤。

（b）评测不完整。 仅报告基构造时间，未报告完整 attack pipeline（含 BKZ）。若 BKZ 占总时间的 95%，基构造加速对整体时间的影响会相应稀释。

（c）缺乏 hint 选择策略。 论文回答「给定一组 hint 后如何最快嵌入」，不回答「哪些 hint 对攻击帮助最大」。对于攻击者可以主动选择测量目标的场景，hint 的信息论价值分析是缺失的 prior。

（d）联合 hint 不在框架内。 如 §4.5。双变量泄漏（\(\mathbf{s}\) 与 \(\mathbf{e}\) 同时暴露的场景）需要额外处理。

7.3 后续方向

• BP + HNF 融合： BP 做带噪 hint 预处理（去噪、软判决）→ 清理后的 hint 送入 HNF 管道做格基构造。对 HSMP25 框架（EUROCRYPT 2025）的实现级补充。
• Hint selection 优化问题： 固定测量预算下选择最优 hint 子集，最大化攻击效果。组合优化 + hint 之间的信息冗余分析。
• Ring/Module-LWE 推广： Module 结构的代数约束在转换为 \(\mathbb{Z}\)-格时会损失代数效率增益——需要特殊的格基构造技巧。
• 代码开源： MN23 和 Lu 等人的方法目前缺乏标准实现。一旦有可靠的 SageMath/Python 库，这条攻击路线将从学术工具进入安全评估和 CTF 社区。

7.4 继续阅读

• lattice-part-9：primal attack 框架与 BKZ block-size 估计
• lattice-part-10：侧信道泄漏类型与实现断层线
• Toy exercise：用 \(n=4, m=10, q=17\) 手动走一遍完美 hint 的 HNF 构造链——小维度上的矩阵变化即大维度版本的 scale-down
• 取 Kyber512 标准参数，用 lwe-estimator 估算需要多少 hint 才能将 BKZ block size \(\beta\) 降至安全边界以下

参考文献

• DSDGR20: Dachman-Soled, Ducas, Gong, Rossi. LWE with Side Information: Attacks and Concrete Security Estimation. CRYPTO 2020.
• DSGHK23: Dachman-Soled, Gong, Hanson, Kippen. Revisiting Security Estimation for LWE with Hints from a Geometric Perspective. CRYPTO 2023.
• MN23: Nowakowski, May. Too Many Hints — When LLL Breaks LWE. ASIACRYPT 2023.
• HSMP25: Hermelink, Streit, Mårtensson, Petri. A Generic Framework for Side-Channel Attacks against LWE-based Cryptosystems. EUROCRYPT 2025.
• LFP25: Lu, Feng, Pan. Solving LWE with Independent Hints about Secret and Errors. 2025.
• CN11: Chen, Nguyen. BKZ 2.0: Better Lattice Security Estimates. ASIACRYPT 2011.
• APS15: Albrecht, Player, Scott. On the Concrete Hardness of Learning with Errors. 2015.
• KB79: Kannan, Bachem. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM Journal on Computing, 1979.

关联阅读：lattice-part-9（Primal/Dual 攻击与 BKZ 具体安全性估计）；lattice-part-10（格子实现中的断层线与侧信道泄漏类型）。