摘要

随着量子计算技术的快速发展, 传统公钥密码体制面临严峻安全威胁. 本文针对 NIST 后量子密码标准化中的核心问题, 深入研究环学习带错误(RLWE) 和模学习带错 误(MLWE) 问题的求解方法与安全性分析. 首先, 基于分圆多项式理论精确计算了环 Rq = Zq[X]/(Xn + 1) 中主理想(a(X)) = Rq 的概率. 其次, 提出完整的RLWE 问题 求解框架: 通过旋转矩阵构造将RLWE 转化为标准LWE 问题, 利用q-ary 格理论约化 为最近向量问题(CVP), 再通过Kannan 嵌入技术转换为最短向量问题(SVP). 实验成 功恢复多种参数设置下的RLWE 实例中的秘密多项式s 与错误多项式e, 其中第1-5 问求的解均满足题目模长要求. 本研究为评估基于格的后量子密码方案(如NIST 标准 ML-KEM 和ML-DSA) 的实际安全强度提供了理论基础与实用工具.

关键词： 格密码; RLWE; 格基约化; 最短向量问题

引言

大规模量子计算机的潜在威胁对传统公钥密码学的安全性构成根本性挑战. 为应对 此挑战, 后量子密码学(Post-Quantum Cryptography, PQC) 应运而生, 其核心在于构建 基于量子计算下困难数学问题的密码体制, 旨在替代当前广泛依赖的传统公钥密码学, 实现密钥封装, 数字签名等核心功能. 在此背景下, 美国国家标准与技术研究院（NIST）于2016 年启动全球性后量子密 码标准化进程. 经过多轮严格评估, NIST 于2024 年8 月正式发布首批后量子密码标准:

• FIPS 203(基于模格学习带错误问题的密钥封装机制ML-KEM)
• FIPS 204(基于模格学习带错误问题的数字签名ML-DSA)
• FIPS 205(无状态哈希数字签名SLH-DSA) 其中,FIPS 203（Crystals-Kyber）与FIPS 204（Crystals-Dilithium）均基于模格学习 带错误问题(Module Learning With Errors, MLWE). 这些方案的理论安全性本质依赖 于底层MLWE 及其变种（如环学习带错误问题RLWE）的计算困难性. 因此, 深入理 解LWE 问题家族的计算复杂度并优化其求解算法, 构成评估后量子密码方案安全性的 理论基础.

相关工作

近年来关于攻击LWE 以及其变体的相关研究大致如下: 格基约简与基础攻击框架. 格基约简算法构成了几乎所有LWE 攻击的理论基础, 其核心是通过系统性地投影向量到线性子空间来缩小尺寸并寻找短向量. LLL 算法1 作 为多项式时间算法, 能生成近似正交的短格基, 但其解的质量仅达到指数级近似. Block Korkine-Zolotarev (BKZ) 算法2 虽能获得更短向量, 却以指数时间复杂度为代价. 其改 进版本如BKZ2.03 和渐进式BKZ4–6 显著提升了效率. 值得注意的是, BKZ 的子程序需 在低维子格中求解最短向量问题, 筛法7,8 因其能在短时间内生成指数级短向量而成为重 要选项, 但其内存消耗同样呈指数增长. 最新提出的Flatter 算法9 通过精细的精度管理 技术, 在保持LLL 级别解的质量的同时实现了更快的格基约简. 多样化攻击范式. 针对Search-LWE 的攻击主要分为四类: uSVP 攻击10、机器学 习攻击11, Cool&Cruel 攻击12 以及针对Decision-LWE 的对偶攻击13,14. uSVP 攻击通 过构造特殊格结构, 将秘密向量恢复问题转化为寻找格中唯一最短向量问题10. 对偶攻 击则通过寻找对偶格中的短向量来解决Decision-LWE 问题15, 其核心变种包括: 混合 对偶攻击16: 将矩阵A 分割为两部分, 分别进行格基约简和猜测计算, 特别适用于稀疏 秘密. 中间相遇攻击(MitM)14: 通过构建部分秘密猜测表来提升成功率, 但需指数级内 存. 机器学习攻击以SALSA 框架为代表11,17–19, 通过训练Transformer 模型从约简样 本(A, b) 中预测b 并构建预言机, 最终在维度n ≤1024 下成功恢复稀疏二元/三元秘 密11. Cool&Cruel 攻击12 则利用格基约简后矩阵的” 悬崖现象”——前部列保持未约简 状态(”Cruel” 位), 后部列显著缩小(”Cool” 位), 先通过暴力破解恢复Cruel 位, 再用贪 心算法高效恢复Cool 位.

本研究主要工作

具体研究工作涵盖:

1. 计算环Rq 中均匀随机元素a(X) 满足主理想(a(X)) = Rq 的概率;
2. 基于Primal Attack 求解不同参数下的搜索RLWE 问题, 成功恢复短模长的秘 密向量s 与错误向量e (攻击流程见图1, 图中Search-RLWE 和Search-LWE 分别 简写为S-RLWE 和S-LWE).

图 1 为规约流程图，对应的主线为：S-RLWE → S-LWE → CVP → SVP，中间三步依次是 Reduction to LWE、Reduction to CVP 与 Kannan Embedding。

一、前置知识及符号说明

这里先把后文会反复用到的符号和定义整理出来。

对于奇素数 $q$，记

$$Z_q = Z \cap \left[-\frac{q}{2}, \frac{q}{2}\right).$$

对两个向量 $v = (v_1, \ldots, v_d),\; w = (w_1, \ldots, w_d) \in R^d$，定义它们的内积和欧氏范数分别为

$$\langle v, w \rangle = \sum_{i=1}^d v_i w_i, \qquad \|v\| = \sqrt{\langle v, v \rangle}.$$

这里的 $A^\top$ 表示矩阵 $A$ 的转置。

定义 1（搜索 LWE 问题）. 固定秘密向量 $s \in Z_q^n$。LWE 分布 $A_{s,\chi}$ 生成样本对 $(a,b) \in Z_q^n \times Z_q$，其中向量 $a$ 在 $Z_q^n$ 上均匀随机选取，且

$$b = \langle a, s \rangle + e \pmod q,$$

噪声项 $e$ 采样自分布 $\chi$。给定任意独立样本，搜索 LWE 问题要求恢复秘密向量 $s$。

定义 2（搜索环 LWE 问题）. 固定秘密元素 $s(X) \in R_q$。环 LWE 分布 $A_{s,\chi}$ 生成样本对 $(a(X), t(X)) \in R_q \times R_q$，其中多项式 $a(X)$ 在商环 $R_q$ 上均匀随机选取，且

$$t(X) = s(X) \cdot a(X) + e(X),$$

噪声多项式 $e(X)$ 采样自分布 $\chi$。给定任意独立样本，搜索环 LWE 问题要求恢复秘密 $s(X)$。

这里的旋转操作后面会直接用来把 RLWE 写成矩阵形式。对元素

$$f(x)=f_0 + f_1 X + \cdots + f_{n-1} X^{n-1} \in R\; (\text{或 }R_q),$$

其系数向量记为 $f = (f_0, f_1, \ldots, f_{n-1})$。定义旋转操作为

$$\operatorname{rot}(f)=(-f_{n-1}, f_0, f_1, \ldots, f_{n-2}). \tag{1.1}$$

这个向量正好对应环 $R$ 中元素 $x f(x)$ 的系数表示。进一步，对任意 $1 \le i \le n$，旋转向量 $\operatorname{rot}^i(f)$ 对应元素 $x^i f(x)$ 的系数表示。特别地，由 $R$ 中关系 $x^n=-1$ 可得

$$\operatorname{rot}^n(f) = -f.$$

格是欧几里得空间 $R^d$ 中的离散加法子群。任意格 $L$ 可由 $R^d$ 中线性无关的行向量组 $b_1, \ldots, b_h$ 生成：

$$L = L(b_1, \ldots, b_h) = \left\{ \sum_{i=1}^h z_i b_i \mid z_i \in Z \right\}. \tag{1.2}$$

向量组 $B=(b_1, \ldots, b_h)$ 称为 $L$ 的格基，生成格 $L$ 的极大线性无关向量数称为格的维度（或秩），记为 $\dim(L)$。当 $\dim(L)=d$ 时，称 $L$ 为 $R^d$ 中的满秩格。定义 $\lambda_1(L)$ 为格 $L$ 的第一逐次极小值，即 $L$ 中最短非零向量的范数。

下面这个 $q$ 元格会在 LWE 到 CVP 的规约里直接出现。设 $q$ 为奇素数，若满秩格 $L \subset R^d$ 满足包含关系 $qZ^d \subseteq L \subseteq Z^d$，则称 $L$ 为 $q$ 元格。对于给定 LWE 实例，可构造如下的 $q$ 元格：

$$\Lambda_q(\hat A) = \{\hat z \in Z^d \mid \hat z \equiv s\hat A \pmod q,\; \exists s \in Z^n\}. \tag{1.3}$$

该 $q$ 元格可由矩阵

$$\begin{pmatrix} \hat A \\ qI_d \end{pmatrix}$$

的行向量生成，其中 $I_d$ 为 $d$ 维单位矩阵。

LLL 约化和 BKZ 约化是后文规约算法真正落地时的两种基本工具。对参数 $\delta \in (1/4, 1)$，格 $L \subset R^m$ 的基 $B=(b_1, \ldots, b_d)$ 称为 $\delta$-LLL 约化基，当且仅当它同时满足：

$$|\mu_{ij}| \le \frac{1}{2} \qquad (i>j),$$

其中

$$\mu_{ij}=\frac{\langle b_i, b_j^* \rangle}{\langle b_j^*, b_j^* \rangle},$$

以及 Lovász 条件

$$\delta \|b_{k-1}^*\|^2 \le \|b_k^* + \mu_{k,k-1} b_{k-1}^*\|^2, \qquad 2 \le k \le d.$$

这里的 $b_i^*$ 表示 Gram-Schmidt 正交化向量。令

$$\alpha = (4\delta - 1)^{-1/2},$$

则该约化基满足上界

$$\|b_1\| \le \alpha^{d-1} \lambda_1(L), \qquad \|b_1\| \le \alpha^{(d-1)/2} \operatorname{vol}(L)^{1/d}.$$

对于 BKZ，设正交投影算子 $\pi_j$ 为向量在子空间 $(b_1, \ldots, b_{j-1})^\perp$ 上的投影，令

$$B[j:k] = (\pi_j(b_j), \pi_j(b_{j+1}), \ldots, \pi_j(b_k)),$$

并定义子格 $L[j:k]=L(B[j:k])$。对块大小 $\beta \ge 2$，若基 $B$ 满足尺寸约减条件，且对所有 $1 \le j \le d-1$ 都有

$$\|b_j^*\| = \lambda_1\bigl(L[j:k]\bigr), \qquad k = \min(j+\beta-1, d),$$

则称其为 $\beta$-BKZ 约化基。特别地，当 $\beta = n$ 时即为 HKZ 约化基。

BKZ 的核心思路是在每个块上先做 LLL，再调用精确 SVP 算法求短向量。其典型长度上界写成

$$\|b_1\| \le \gamma_\beta^{\frac{d-1}{2(\beta-1)}} \lambda_1(L),$$

其中 $\gamma_\beta$ 为维度 $\beta$ 的 Hermite 常数。这个式子想表达的重点很简单：块大小 $\beta$ 越大，短向量质量通常越好，但代价是计算量也会迅速上升。

二、环Rq 中主理想(a(X)) = Rq 的概率计算

1. 理论基础与计算方法

这一节真正要算的是：在分圆环 $R_q = Z_q[X]/(X^n+1)$ 中，随机元素 $a(X)$ 生成整个主理想 $R_q$ 的概率。换句话说，也就是它在这个商环里成为可逆元的概率。

在商环 $Z_q[X]/(f(X))$ 中，$a(X)$ 可逆的充要条件是

$$\gcd(a(X), f(X)) = 1 \qquad \text{于多项式环 } Z_q[X].$$

这里取的是

$$f(X)=X^n+1 = X^{256}+1.$$

由分圆多项式理论，

$$X^{512}-1=(X^{256}-1)(X^{256}+1)=\prod_{d\mid 512} \Phi_d(X).$$

因为 $512=2^9$ 且 $n\times 2=512$，于是

$$f(X)=X^{256}+1=\Phi_{512}(X). \tag{2.1}$$

这个等式说明我们只需要研究 $\Phi_{512}(X)$ 在有限域 $Z_q$ 上的分解情况。

接下来把题目参数 $q=3329$ 代进去，有

$$q \equiv 3329 \equiv 257 \pmod{512},$$

并且

$$257^2 = 66049 \equiv 1 \pmod{512}$$

（因为 $512 \times 129 = 66048$），所以 $q$ 在模 $512$ 下的乘法阶为 $2$。于是 $\Phi_{512}(X)$ 在 $Z_q[X]$ 中分解为

$$\frac{\varphi(512)}{\operatorname{ord}_{512}(q)} = \frac{256}{2}=128$$

个互异的首一不可约二次多项式，即

$$X^{256}+1 = \prod_{i=1}^{128} p_i(X), \qquad \deg p_i = 2.$$

因此，$a(X)$ 与所有这些不可约因子都互素的概率就是所求概率。由独立性可得

$$p = \left(1 - \frac{1}{q^2}\right)^{128}. \tag{2.2}$$

2. 数值结果

把 $q=3329$ 代入上式，得到具体概率

$$p = \left(1 - \frac{1}{3329^2}\right)^{128}. \tag{2.3}$$

这里这个式子其实说明概率非常接近 1，也就是说在标准参数下随机拿到一个可逆元并不稀奇。

三、RLWE 和MLWE 问题的求解

1. RLWE 到LWE 的规约

这一部分的核心是把“环上的乘法”改写成“矩阵乘法”。对 RLWE 分布 $A_{s,\chi}$ 的一个样本 $(a(X), t(X))$，设 $a(X)$ 的系数向量为

$$a = (a_0, a_1, \ldots, a_{n-1}),$$

则可以构造对应的 $n \times n$ 旋转矩阵

$$A= \begin{pmatrix} a \\ \operatorname{rot}(a) \\ \operatorname{rot}^2(a) \\ \vdots \\ \operatorname{rot}^{n-1}(a) \end{pmatrix} = \begin{pmatrix} a_0 & a_1 & \cdots & a_{n-1} \\ -a_{n-1} & a_0 & \cdots & a_{n-2} \\ -a_{n-2} & -a_{n-1} & \cdots & a_{n-3} \\ \vdots & \vdots & \ddots & \vdots \\ -a_1 & -a_2 & \cdots & a_0 \end{pmatrix}. \tag{3.1}$$

这个矩阵的作用就是把环乘法编码成普通向量乘法。于是样本关系可写成

$$t \equiv sA + e \pmod q,$$

其中 $t,s,e$ 分别是多项式 $t(X), s(X), e(X)$ 的系数向量。

如果把 $X=(1, X, X^2, \ldots, X^{n-1})$ 看成环 $R$（或 $R_q$）的基，那么原来的环关系

$$t(X)=s(X)a(X)+e(X)$$

可以依次写成

$$tX^\top = t(X), \tag{3.2}$$ $$t(X)=s(X)a(X)+e(X), \tag{3.3}$$ $$= sAX^\top + eX^\top, \tag{3.4}$$

从而得到

$$t = sA + e \pmod q. \tag{3.5}$$

这一步想表达的重点其实很简单：单个环 LWE 样本可以直接生成一个 $n \times n$ 的 LWE 实例 $(A,t)$，其秘密向量为 $s$，错误向量为 $e$。

1.1 多样本扩展

考虑从 $A_{s,\chi}$ 获取 $m \ge 1$ 个独立 RLWE 样本 $(a_1(X), t_1(X)), \ldots, (a_m(X), t_m(X))$。令 $A_i$ 表示按式 (3.1) 构造的、对应 $a_i(X)$ 的 $n \times n$ 矩阵，则有

$$t_i \equiv sA_i + e_i \pmod q, \qquad 1 \le i \le m. \tag{3.6}$$

把这些关系拼接起来，就得到尺寸为 $n \times d$ 的 LWE 实例：

$$(\hat A, \hat t), \qquad \hat t \equiv s\hat A + \hat e \pmod q, \tag{3.7}$$

其中 $d=mn$，且

$$\hat A = (A_1 \mid \cdots \mid A_m), \qquad \hat t = (t_1 \mid \cdots \mid t_m), \qquad \hat e = (e_1 \mid \cdots \mid e_m). \tag{3.8}$$

为保证秘密向量 $s$ 的唯一可恢复性，文中要求系统满足超定条件 $m \ge 2$，也就是 $d>n$。

2. LWE 到CVP 的规约

把 RLWE 拉成 LWE 之后，下一步就是把它看成一个格上的最近向量问题。对 LWE 实例 $(\hat A, \hat t)$，目标向量是 $\hat t$，而最近的格点则是 $s\hat A$。如果错误向量 $\hat e$ 足够短，那么两者之间的距离正好就是 $\|\hat e\|$，因此这实际上是一个有界距离解码（BDD）问题，也就是 CVP 的一个特例。

当条件化 RLWE 问题要求 $s(X)$ 为短多项式时，可构造如下 $2n$ 阶整数矩阵：

$$A_{\mathrm{ex}}= \begin{pmatrix} A & -I_n \\ qI_n & 0 \end{pmatrix} \in Z^{2n \times 2n}. \tag{3.9}$$

令 $\Lambda$ 为 $A_{\mathrm{ex}}$ 列向量张成的格，并定义目标行向量

$$t_{\mathrm{ex}} = (t^*, 0) \in Z^{2n}. \tag{3.10}$$

那么存在整数向量

$$s_{\mathrm{ex}} = (s^*, r) \in Z^{2n},$$

使得格点 $s_{\mathrm{ex}}A_{\mathrm{ex}}$ 与目标向量 $t_{\mathrm{ex}}$ 的差向量满足

$$t_{\mathrm{ex}} - s_{\mathrm{ex}}A_{\mathrm{ex}} = (t^*,0) - (s^*,r) \begin{pmatrix} A & -I_n \\ qI_n & 0 \end{pmatrix} = (e^*, s^*) \in Z^{2n}. \tag{3.11--3.12}$$

这里的重点是：一旦最近向量被恢复，错误向量 $e^*$ 和秘密向量 $s^*$ 就会同时出现在差向量里。

3. CVP 到SVP 的规约

到了这里，问题已经变成：在格 $L(A_{\mathrm{ex}})$ 中寻找最靠近 $t_{\mathrm{ex}}$ 的格点。为了继续下推，文中使用的是 Kannan 嵌入技术（Kannan embedding），把 CVP 转成 SVP。

构造如下 $(2n+1) \times (2n+1)$ 维嵌入格矩阵：

$$A^{\star}= \begin{pmatrix} A_{\mathrm{ex}} & 0 \\ t_{\mathrm{ex}} & M \end{pmatrix} \in Z^{(2n+1) \times (2n+1)}. \tag{3.13}$$

其中 $M$ 为标准嵌入常数（通常取 $M=1$）。对格 $L(A^{\star})$ 应用 LLL 或 KZ 格基约简算法，就有机会把包含 $(e^*, s^*)$ 信息的短向量规约出来。

文中接着还给出了一个扩展版本：通过引入旋转操作和扩展参数 $k$，在嵌入格里同时放入多个等长短向量，以提高 BKZ 成功率。给定 LWE 实例 $(\hat A, \hat t)$，构造扩展矩阵

$$A^{\star}= \begin{pmatrix} \hat A & 0 & 0 & \cdots & 0 \\ \hat t & \eta & 0 & \cdots & 0 \\ \operatorname{rot}(\hat t) & 0 & \eta & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \operatorname{rot}^{k-1}(\hat t) & 0 & 0 & \cdots & \eta \end{pmatrix}. \tag{3.14}$$

这里 $\hat A$ 为 $q$-ary 格基，$\hat t$ 为目标向量，$\eta$ 为小常数，$\operatorname{rot}^i(\cdot)$ 表示向量循环移位。这个矩阵生成一个维度为 $d+k$ 的新格 $\bar\Lambda_k$，其中嵌入了 $k$ 个等长短向量：

$$\bigl\{(\hat t, \eta, 0, \ldots, 0),\; (\operatorname{rot}(\hat t), 0, \eta, \ldots, 0),\; \ldots,\; (\operatorname{rot}^{k-1}(\hat t), 0, 0, \ldots, \eta)\bigr\}.$$

这一扩展的直观作用是：把“同长度的好向量”一次性塞进格里，给 BKZ 更多机会碰到正确结构。

通过调整右下块结构，可增大格体积而不增加错误向量长度，从而优化求解过程。实验表明（参数 $n=32, q=577, d=96, \sigma=11.0, \beta=65$），扩展方法显著提升成功率：当 $k=1$（原始嵌入）且 $\eta = 1, \lceil \sigma \rceil, 2\lceil \sigma \rceil$ 时，成功率分别为 $55\%, 69\%, 62\%$；而 $k=2,3,4,5$ 时成功率最高可达 $75\%, 78\%, 76\%, 79\%$（较原始最大提升 $23\%$）。需注意，成功率随 $k$ 增加呈波动性，且受误差标准差 $\sigma$ 和 BKZ 块大小 $\beta$ 等因素影响，但合理选择 $k$ 可稳定获得显著增益。

4. SVP 问题的求解

这一节主要是在说明：上面规约完之后，剩下真正难的是高维格上的 SVP，而求 SVP 的效率基本就决定了攻击是否现实。

文中提到，当前主流方法包括 BKZ 框架、枚举法和筛法。枚举法的核心思想是穷举一个以原点为中心、半径为 $R$ 的高维超球内的格点；它在低维效果很好，但高维时复杂度会迅速膨胀。文中把这个增长写成

$$2^{\Theta(n \log n)}.$$

筛法则是另一条主路线，随着 AKS 筛法、NV 筛法、GaussSieve、G6K 等工作的推进，在工程上已经成为很多高维实验的关键工具。

经过前面的规约，本文最后需要处理的是维度

$$N = 2n + 1$$

的格上的最短向量问题。文中实验参数为 $n=64,96,128,256$，对应的格维度分别为 $129,193,257,513$。在 $257$ 维和 $513$ 维上直接求精确 SVP 难度已经很高，因此最终调用了 SGAE 框架中的 LLL、BKZ 和 G6K 来做实验。

表 1 如下，直接保留为 Markdown 版表格，便于复制和检索：

题目	$n$	$N$	$\|e\|$	$\|s\|$	SVP-Solver	是否满足条件
2.1	64	129	8.54	7.99	LLL	是
2.2	64	129	1.73	1.41	BKZ	是
2.3	96	197	9.38	9.27	BKZ	是
2.4	128	257	11.1	11.44	BKZ	是
2.5	128	257	13.74	2.82	BKZ	是
2.6	256	513	13.71*	4.00*	LLL	是
2.7	256	513	10.58*	4.00*	LLL	是
2.8	256	513	-	-	G6K	-

这里 * 表示时间限制下求得的近似解，- 表示受设备限制未能在短时间内求解。

实验环境为：CPU i9-13900H@2.6 GHz，RAM 32GB。

四、结论

本文深入研究了 RLWE 问题的求解方法，旨在推进后量子密码学的安全性评估。基于分圆多项式理论，文中精确计算了环

$$R_q = Z_q[X]/(X^n+1)$$

中主理想 $(a(X)) = R_q$ 的生成概率，并在标准参数 $n=256, q=3329$ 下得到

$$\left(1-\frac{1}{q^2}\right)^{128}$$

这一理论结果。

随后，文中构建了一个完整的 RLWE 求解框架：首先通过旋转矩阵把 $n$ 维 RLWE 问题转成 $n \times n$ 维 LWE 问题；接着利用 $q$-ary 格理论把 LWE 约化为格中的最近向量问题（CVP）；最后通过 Kannan 嵌入把 CVP 转化为最短向量问题（SVP）。

在算法实现层面，文中比较了多种格基约简技术，包括 LLL、BKZ 以及基于 G6K 求解器的 3-sieve 算法，并在若干 RLWE 实例上恢复出了秘密多项式和错误多项式，验证了方法的有效性。

总体而言，这篇论文的主要结论是：RLWE 求解复杂度的细化分析不仅能帮助理解底层代数结构，也能为评估 ML-KEM、ML-DSA 这类 NIST 标准后量子密码方案的参数安全边界提供实际参考。

附录 I

解题结果

下面这一节记录的是各题恢复出来的实验结果。

• s = [...] 表示恢复出的秘密向量（或秘密多项式的系数向量）
• e = [...] 表示恢复出的误差向量（或错误多项式的系数向量）
• s.norm / e.norm 表示对应向量的欧氏范数
• wt(s(x)) 表示多项式的汉明重量

1. 题目(2.1)

s = [1, -2, 0, 0, 1, 0, -1, 1, 1, -1, 1, 2, 1, 1, -1, -1, 0, 1, 0, -1, -1, 0, 0, 2, 1, -1, 0, -1, 0,
2, 0, 1, 1, -1, 0, 0, -1, 2, -1, -1, 0, -1, -1, 2, 1, -1, 1, -1, 2, 1, 1, 0, -1, 1, -1, 0, -2, 1, 0, 1,
-2, 0, 0, 1]

s.norm=8.54400374531753

e = (-1, 1, 0, -1, 1, 0, -1, 0, -1, -1, 0, 1, -1, -1, -2, -2, -1, -1, 0, 0, -1, 1, 2, 2, -1, -1, 0,
0, -1, -1, 0, 1, -1, -1, -2, -1, 1, 0, -1, 0, 0, -1, 1, 0, 1, -2, 0, 1, 0, -1, -1, -1, 1, 1, -1, -1, 1, 1,
0, 1, 0, -1, 0, -1)

e.norm=7.999999999999999

2. 题目(2.2)

s= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

s.norm= 1.73205080756888

wt(s(x))=3

e= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0]

e.norm= 1.41421356237310

3. 题目(2.3)

s = [-1, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 1, -1, 1, 0, 1, -2, 0, -1, 0, 0, -1, 0, 1, 1, -2, 0, 0,
-2, 1, 1, 1, -1, 1, -1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 1, -1, -1, -1, 1, -1, 1, -1, 0, 0, 0, 0,
-1, 0, 0, -1, -1, 0, 1, 0, -1, 0, 2, 1, -2, -2, -1, 0, 1, 0, 1, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, -1, -2, 0,
-2, -2, 0]

s.norm = 9.38083151964686

e = [-1, 0, 1, 0, 0, 1, -1, -1, 0, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -2, 0, -1, -1, 1, -2, 0, 0, -1,
0, 0, -1, 0, 2, -1, 1, -2, 0, 0, 1, -1, 1, 0, 0, 2, 0, 1, -1, 0, 1, -1, 1, 1, 1, -1, 0, -1, 0, 0, -1, -1,
0, -1, 0, -1, -1, 0, 0, -1, 0, 0, 0, -2, -2, 1, -1, -1, 0, -2, 0, 0, -2, 0, 0, -1, 2, 0, 0, 0, 0, 0, 1, 2,
-1, 0, 1, 1]

e.norm = 9.27361849549571

1. 题目(2.4)

s=[0, 0, 0, 0, -1, 1, 1, -1, -1, 0, 0, -1, -1, -1, -2, 1, -1, -1, 1, -1, 1, 0, 1, -1, -1, 0, 1, -1,
-1, -2, 1, 0, 0, 0, 0, -1, 1, 0, -2, 0, -1, 0, 0, 1, 0, 2, -1, 1, 0, 0, 0, 2, -2, 2, -1, 0, 1, 0, 1, 2, 0,
0, -2, -1, 0, 0, -1, 0, -1, 0, 2, -2, 0, 0, -1, 0, -1, 2, -1, -1, -1, 1, 1, -1, 0, -1, 0, -1, -1, -1, 0, 1,
-1, 0, 0, -1, 0, 2, -1, 0, 0, 0, -1, 0, -2, 1, 0, 0, 0, -2, 0, 1, 1, 1, 1, 0, 0, -1, -1, 0, -2, 0, -2, 0,
0, 0, 0, 0]

s.norm=11.1803398874989

e=[0, -2, 1, 1, 1, 0, 1, 0, 0, -1, -1, -1, 0, 0, 0, 1, 0, 0, 1, -2, 0, -2, 0, -1, 0, -1, -1, 0, 1,
-1, 1, -1, -1, 2, -1, 0, 0, 1, 1, 2, 0, 2, -1, 0, 0, -1, 0, 2, 2, 1, 1, 0, -1, 1, -1, -1, -1, 0, -2, 0,
-1, -1, 1, 1, 0, 0, 0, 1, 0, 2, 0, 2, 0, -1, -1, -1, 1, -1, -1, -1, -1, 0, -1, 1, 0, 1, 2, 0, -1, -2, 1,
0, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 1, 0, 1, 0, 1, 1, 1, 0, 0, -1, 0, -1, -1, 1, 0, 0, 2, -2, -1,
-1, 1, -2, -1, -1]

e.norm=11.4455231422596

5. 题目(2.5)

s=[1, -1, 0, 0, -1, 1, -1, -1, 1, 1, 2, -1, 0, -1, -1, 0, 0, -2, -1, 1, 0, 0, 2, 1, 2, 0, -2, 1, 0,
-2, 0, -1, 1, 0, 1, 0, 0, 1, 0, 0, -1, 0, 0, 0, -1, -1, 1, -1, -2, 0, -2, 1, -1, -2, -1, -1, 1, -1, 1, 0,
1, 3, -1, 1, -1, 0, 0, 2, -1, 1, 2, 1, 2, 2, 2, -1, 1, -2, -1, 0, 0, 1, 0, 1, 1, 1, 1, 0, -1, 1, 0, 0, -1,
-1, -2, 0, 1, -2, 1, 1, -1, 1, -1, 2, 2, 1, -2, 3, 0, 0, -2, 1, 1, 0, -2, 0, 0, 1, -2, -1, 1, -1, -1, -3,
-2, 1, 0, -1]

s.norm=13.7477270848675

e=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0,
0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0]

e.norm=2.82842712474619

6. 题目(2.6)*

s=[0, -1, -1, -1, -1, -1, 0, 0, -2, 0, 2, 0, 0, -1, -1, -1, 2, -2, 0, 0, 0, 0, 1, 1, 0, -1, -1, -2,
1, 1, 1, -1, 0, -1, 1, 1, 0, 0, 0, -2, 0, -1, 0, 0, 0, -2, -1, -2, 0, -2, 1, 2, 0, 0, 1, 1, 0, 0, 1, 2, 0,
1, 1, 1, 0, 1, 2, 0, -1, 0, 0, 0, 0, 0, 1, -2, -1, 0, 0, -1, -1, -1, 2, 1, -2, -1, -2, 0, 0, 0, -2, -1, 1,
0, 1, 0, 0, 2, 0, 1, -1, 1, -1, 0, 1, 0, -1, 0, 0, -2, 1, -2, 1, 1, 0, 0, -2, 0, 0, -2, 1, 1, -1, 1, 1, 2,
-1, 0, -1, 2, 0, 0, 2, -1, -1, 0, -2, 1, 1, 1, -1, 1, 0, -1, 1, 0, 1, 0, 0, 1, -1, 1, 2, 0, 0, 1, 0, 0, 0,
-1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0]

s.norm(): 13.7113092008021

e=[4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

e.norm=4.00000000000000

7. 题目(2.7)∗

s=[2, 0, -1, 0, -2, 0, 0, 0, 0, 0, 1, -1, -1, -1, 1, 0, 0, 0, 0, 1, -1, 0, 0, 1, 0, 1, 0, 0, 0, 2,
1, -1, 0, 0, -1, -1, 0, 0, 0, 1, 0, 0, -1, 1, 1, 0, 0, 1, 0, 0, 0, 1, -1, -1, 0, 0, 0, 0, -1, -1, 0, 0, 1,
-1, 0, -2, 0, 1, 0, 1, -1, 1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, -1,
-1, -1, 2, 1, -1, 0, -1, 2, -1, 0, 2, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1, 1, 0, -1, 0, 0, 0, 0, -1, 0, -1, 1,
0, 0, 1, -1, 0, 1, 0, -1, 0, -1, 1, -1, -1, 0, 1, 1, -1, 0, 0, -1, -1, 1, 2, 0, 0, 0, -1, 0, -2, 0, 1, -1,
1, -1, 0, 1, 1, 1, 0, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0]

s.norm=10.5830052442584

e=[4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

e.norm=4.00000000000000

注：“*”为时间与设备限制下求取的近似解。

附录 II

1. 代码

下面这段是附录给出的 Sage 代码片段，主要展示如何把 RLWE 规约到嵌入格后再做格基约简。这里保留原有逻辑，只把版式整理成可读代码块。

n = 
q = 
A =  # a(x) 的多项式各项系数
B =  # t(x) 的多项式各项系数

# 将 A 转换为矩阵形式
poly_mul_mat = Matrix(ZZ, n, n)
for i in range(n):
    for j in range(i + 1):
        poly_mul_mat[j, i] = A[i - j]
    for j in range(n - i - 1):
        poly_mul_mat[j + i + 1, i] = A[-(j + 1)] * (-1)

# 将 RLWE 问题规约为 SVP 问题
I = identity_matrix(n)
B_mat = Matrix(ZZ, B)
O = diagonal_matrix([0] * n)
O_vec = Matrix(ZZ, 1, n)
O_vec_T = Matrix(ZZ, n, 1)
L = block_matrix(ZZ, [[p * I, O, 0], [poly_mul_mat, I, O_vec_T], [B_mat, O_vec, 1]])  # Kannan embedding

# 格基规约，LLL 或 BKZ
# L_LLL = LLL()
L_LLL = L.BKZ()

# 得到 s(x) 和 e(x) 的各项系数
s = res[n, 2 * n]
e = res[0, n]

2. 各题解题参数

• (1) LLL(default)
• (2)(3) BKZ(block_size=20)
• (4)(5) BKZ(algorithm='NTL', fp='qd', prune=10, block_size=20)
• (6)(7) LLL(algorithm='NTL:LLL', fp='qp', transformation=true)

注：由于设备与时间限制，文中未尝试使用更高的 block_size 进行求解；若继续提高 block_size，理论上可以进一步提升格基规约质量。

参考文献

[1] A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” 1982. [2] C.-P. Schnorr, “A hierarchy of polynomial time lattice basis reduction algorithms,” Theoretical computer science, vol. 53, no. 2-3, pp. 201–224, 1987. [3] Y. Chen and P. Q. Nguyen, “Bkz 2.0: Better lattice security estimates,” in International Conference on the Theory and Application of Cryptology and Information Security, pp. 1–20, Springer, 2011. [4] Y. Aono, Y. Wang, T. Hayashi, and T. Takagi, “Improved progressive bkz algorithms and their precise cost estimation by sharp simulator,” in Advances in Cryptology-EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35, pp. 789–819, Springer, 2016. [5] L. Wang, W. Xia, G. Wang, B. Wang, and D. Gu, “Improved pump and jump bkz by sharp simulator,” Cryptology ePrint Archive, 2022. [6] W. Xia, L. Wang, D. G. GengWang, D. Gu, and B. Wang, “Improved progressive bkz with lattice sieving.,” IACR Cryptol. ePrint Arch., vol. 2022, p. 1343, 2022. [7] M. R. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, and M. Stevens, “The general sieve kernel and new records in lattice reduction,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 717–746, Springer, 2019. [8] L. Ducas, M. Stevens, and W. van Woerden, “Advanced lattice sieving on gpus, with tensor cores,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 249–279, Springer, 2021. [9] K. Ryan and N. Heninger, “Fast practical lattice reduction through iterated compression,” in Annual International Cryptology Conference, pp. 3–36, Springer, 2023. [10] M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, et al., “Homomorphic encryption standard,” Protecting privacy through homomorphic encryption, pp. 31–62, 2021. [11] S. Stevens, E. Wenger, C. Li, N. Nolte, E. Saxena, F. Charton, and K. Lauter, “Salsa fresca: angular embeddings and pre-training for ml attacks on learning with errors,” arXiv preprint arXiv:2402.01082, 2024. [12] N. Nolte, M. Malhou, E. Wenger, S. Stevens, C. Li, F. Charton, and K. Lauter, “The cool and the cruel: separating hard parts of lwe secrets,” in International Conference on Cryptology in Africa, pp. 428–453, Springer, 2024. [13] M. R. Albrecht, S. Bai, P.-A. Fouque, P. Kirchner, D. Stehlé, and W. Wen, “Faster enumeration-based lattice reduction: root hermite factor time,” in Annual International Cryptology Conference, pp. 186–212, Springer, 2020. [14] J. H. Cheon, M. Hhan, S. Hong, and Y. Son, “A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret lwe,” IEEE Access, vol. 7, pp. 8949789506, 2019. [15] D. Micciancio and O. Regev, “Lattice-based cryptography,” in Post-quantum cryptography, pp. 147–191, Springer, 2009. [16] M. R. Albrecht, “On dual lattice attacks against small-secret lwe and parameter choices in helib and seal,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 103–129, Springer, 2017. [17] E. Wenger, M. Chen, F. Charton, and K. E. Lauter, “Salsa: Attacking lattice cryptography with transformers,” Advances in Neural Information Processing Systems, vol. 35, pp. 34981–34994, 2022. [18] C. L. J. S. E. Wenger, Z. Allen-Zhu, F. Charton, and K. Lauter, “Salsa verde: a machine learning attack on learning with errors with sparse small secrets,” [19] C. Y. Li, J. Sotáková, E. Wenger, M. Malhou, E. Garcelon, F. Charton, and K. Lauter, “Salsapicante: a machine learning attack on lwe with binary secrets,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 2606–2620, 2023. [20] D. Micciancio and O. Regev, “Lattice-based Cryptography,” in Post-Quantum Cryptography (D. J. Bernstein, J. Buchmann, and E. Dahmen, eds.), pp. 147–191, Berlin, Heidelberg: Springer, 2009. [21] R. Kannan, “Minkowski’s convex body theorem and integer programming,” Mathematics of Operations Research, vol. 12, no. 3, pp. 415–440, 1987. [22] S. Nakamura and M. Yasuda, “An extension of kannan’s embedding for solving ringbased lwe problems,” in Cryptography and Coding (M. B. Paterson, ed.), (Cham), pp. 201–219, Springer International Publishing, 2021. [23] M. Ajtai, R. Kumar, and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, (New York, NY, USA), p. 601–610, Association for Computing Machinery, 2001. [24] D. Micciancio and P. Voulgaris, Faster exponential time algorithms for the shortest vector problem, pp. 1468–1480. [25] P. Q. Nguyen and T. Vidick, “Sieve algorithms for the shortest vector problem are practical,” Journal of Mathematical Cryptology, vol. 2, no. 2, pp. 181–207, 2008. [26] X. Wang, M. Liu, C. Tian, and J. Bi, “Improved nguyen-vidick heuristic sieve algorithm for shortest vector problem,” in Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, pp. 1–9, 2011. [27] F. Zhang, Y. Pan, and G. Hu, “A three-level sieve algorithm for the shortest vector problem,” in International Conference on Selected Areas in Cryptography, pp. 29–47, Springer, 2013. [28] S. Bai, T. Laarhoven, and D. Stehlé, “Tuple lattice sieving,” LMS Journal of Computation and Mathematics, vol. 19, no. A, pp. 146–162, 2016. [29] P. Mukhopadhyay, “Faster provable sieving algorithms for the shortest vector problem and the closest vector problem on lattices in ￿p norm,” Algorithms, vol. 14, no. 12, p. 362, 2021. [30] T. Laarhoven, “Sieving for shortest vectors in lattices using angular locality-sensitive hashing,” in Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I 35, pp. 3–22, Springer, 2015. [31] A. Becker, L. Ducas, N. Gama, and T. Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” in Proceedings of the twentyseventh annual ACM-SIAM symposium on Discrete algorithms, pp. 10–24, SIAM, 2016. [32] T. Laarhoven, M. Mosca, and J. Van De Pol, “Solving the shortest vector problem in lattices faster using quantum search,” in Post-Quantum Cryptography: 5th International Workshop, PQCrypto 2013, Limoges, France, June 4-7, 2013. Proceedings 5, pp. 83–101, Springer, 2013. [33] T. Laarhoven and A. Mariano, “Progressive lattice sieving,” in International Conference on Post-Quantum Cryptography, pp. 292–311, Springer, 2018. [34] L. Ducas, “Shortest vector from lattice sieving: a few dimensions for free,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 125–145, Springer, 2018. [35] A. Chailloux and J. Loyer, “Classical and quantum 3 and 4-sieves to solve svp with low memory,” in International Conference on Post-Quantum Cryptography, pp. 225–255, Springer, 2023. [36] M. R. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, and M. Stevens, “The general sieve kernel and new records in lattice reduction.” Cryptology ePrint Archive, Paper 2019/089, 2019. https://eprint.iacr.org/2019/089.