LWE问题的代数求解方式

The Algebraic Way to Solve LWE

摘要: 本文研究了基于错误学习(LWE)问题的密码学构造，重点探讨了通过Kannan嵌入方法将其转化为代数问题的理论框架。我们系统分析了Kannan嵌入在LWE实例中的应用，证明了该转化过程的严谨性及其在密码分析中的有效性。具体而言，本文展示了如何将LWE的搜索问题嵌入到格结构中，并利用代数工具(如最短向量问题，SVP)求解，同时严格论证了转化后的代数形式与原问题的等价性。此外，我们讨论了该方法在参数选择、计算复杂度及安全性证明中的优势，为基于LWE的密码方案设计提供了理论支撑。实验结果进一步验证了该方法的可行性与效率。

Abstract: This paper studies cryptographic constructions based on the Learning With Errors (LWE) problem, with a focus on exploring the theoretical framework of transforming it into an algebraic problem through Kannan’s embedding method. We systematically analyze the application of Kannan’s embedding in LWE instances and prove the rigor of this transformation process and its effectiveness in cryptographic analysis. Specifically, this paper demonstrates how to embed the search problem of LWE into a lattice structure and solve it using algebraic tools (such as the Shortest Vector Problem, SVP), while strictly proving the equivalence between the transformed algebraic form and the original problem. Additionally, we discuss the advantages of this method in parameter selection, computational complexity, and security proof, providing theoretical support for the design of LWE-based cryptographic schemes. Experimental results further validate the feasibility and efficiency of this approach.

1. 引言

LWE (Learning With Errors)问题由Oded Regev于2005年提出[1]，是一个基于格理论的数学难题。其核心思想是在线性方程组中引入随机误差，使得即使已知部分信息，恢复秘密值也变得极其困难。LWE问题的困难性不仅在经典计算模型下成立，而且在量子计算模型下也被认为是难以解决的。这一特性使得基于LWE问题的密码学方案成为后量子密码学中的重要组成部分。基于LWE问题的重要性，已经开发出了多种解法。其中一种方法是将LWE问题重新表述为一个优化问题，其解向量由私钥和误差向量组成。假设这两个向量的元素具有较小的绝对值，因此这些问题被称为短向量问题(SVP)。与LWE问题不同，SVP的解是在整数环上的向量，这使得解法的设计更为简单，因为无需模运，仅需使用标准整数运算即可。

但目前尚无有效算法能求解实际规模的SVP。为了简化SVP的求解，常使用诸如Lenstra-Lenstra-Lovász基约简算法(LLL算法) [2]或Block Korkine-Zolotarev算法(BKZ算法) [3]。这些算法将SVP的解视为格中的元素，并将格基转换为几乎正交且由短向量组成的新基。借助这样的基，可以更便捷地计算或逼近SVP的解。在某些情况下，格基本身就可能包含SVP的解。故在本研究中，将针对不同规模的LWE问题去选择更合适的格基约化算法。

LWE问题的研究具有深远的实际意义。首先，它为构建抗量子攻击的密码学原语提供了坚实的理论基础。基于LWE问题，可以设计出安全的公钥加密，数字签名，伪随机函数等多种密码学工具。这些工具不仅能够抵御量子计算攻击，还能在经典计算环境下保持高效性。其次，LWE问题的困难性可以归约到格理论中的最坏情况假设，这意味着破解LWE问题等价于解决格理论中的某些困难问题(如最短向量问题，SVP)。这种归约为LWE问题的安全性提供了强有力的理论支持，使其成为密码学研究中备受信赖的难题[4]。

本文主要是通过数学角度来去证明如何将LWE问题重新表述为一个优化问题，其解向量由私钥和误差向量组成。并与短向量问题联系起来，通过代数学的角度来去简化问题。

2. 理论基础

2.1. 格理论以及格上的数学问题

格(Lattice)是一个在向量空间中由一组线性独立的基向量生成的离散集合。形式上，一个格$L\left(b\right)$ 可以定义为：

$L\left(B\right)=\left\{{\displaystyle \sum _{i=1}^n{c}_i{v}_i}:\forall i\in \left[n\right],c_i\in Z\right\}$

其中B为n维空间中的一组基[5]。

格的最短向量问题(SVP)：给定一个格$L\left(b\right)$ ，其由一组线性无关的向量$B_1,B_2,\cdots ,B_n$ 生成，目标是找到格中一个非零的最短向量u，使得其欧几里德范数最小。我们称u为该格$L\left(b\right)$ 中的最短向量，记作${\lambda }_1\left(L\right)$ 。

在实际问题当中，有时我们并不需要找出真正的最短向量而只需要找出一个“足够短”的向量即可。这样我们就得到了近似最短向量问题。

近似最短向量问题(aSVP)：给定一个n维的格L和一个目标向量$v\in R^n$ 以及近似参数$\gamma \ge 1$ ，目标是找到格中一个向量$v\in R^n$ ，使得其满足$\Vert u\Vert \le \gamma {\lambda }_1\left(L\right)$ 。

2.2. LWE问题

在2005年，Regev提出了一种基于LWE的加密算法。与之前的基于格的密码系统相比，基于LWE的密码系统的密文大小和密钥大小大大减少。因此，LWE开始被应用于许多密码原语，例如Key-Dependent Message (KDM)，完全同态加密等等。

n是正整数，q为奇素数，X是在上服从离散高斯分布的$Z_q$ 错误分布。$s$ 是$Z_q^n$ 上的秘密向量，秘密向量服从均匀分布，$L_{s,x}$ 是$Z_q^n*Z_q$ 上的可能分布，通过随机地在$Z_q^n$ 上选择a和$Z_q$ 上服从X分布的错误e，最终得到$Z_q^n*Z_q$ 上的：

$\left(a,z\right)=\left(a,\langle a,s\rangle +e\right)$

LWE问题就是利用$L_{s,x}$ 中给出的大量的例子也就是方程，找到秘密向量s [6]。

3. 理论证明

现有LWE问题的分析方法可以分为组合方法、代数方法、格方法和穷举搜索。组合方法主要指的是高斯消元法的扩展应用，但它需要大量的样本。代数方法指的是Arora-Ge算法，其复杂度也与LWE维度的数量呈指数关系。主要有三种格方法：对偶方法用于通过解决对偶格上的短整数解问题来攻击决策——LWE实例；解码方法用于直接解决原始格上的有界距离解码问题(BDD)；最主要也是最常用的方法是将有界距离解码(BDD)问题进一步简化为唯一最短向量问题。由于穷举搜索的时间复杂度较高，所以它不适合实际应用[7]。

本文主要是从代数角度给出求解LWE问题的一种可行方法并予以证明。

LWE问题就是利用$L_{s,x}$ 中给出的大量的例子也就是方程，找到秘密向量s。如何去通过代数学的角度去处理LWE问题，可以采用Kannan嵌入法将LWE问题放入更高维的格中去考虑。

将LWE问题表述为矩阵形式

$b=A\cdot s+e\in Z_q^m$

其中矩阵$A\in Z_q^{m\times n}$ 为随机公开矩阵，$s\in Z_q^n$ 是秘密向量，$\text{e}\in Z^m$ 是小误差向量。

目标是从$\left(A,b\right)$ 中恢复$s$ 或$e$ 。

构建如下形式的格基矩阵$B$

$B=\left(\begin{array}{cc}{I}_m& A\\ 0& q{I}_n\end{array}\right)\in Z^{\left(m+n\right)\times \left(m+n\right)}$

现在我们去证明在$L\left(b\right)$ 中必定存在一向量$v=\left(-e,s\right)$ 。并且由于e是小范数向量，此时$v=\left(-e,s\right)$ 还是$L\left(b\right)$ 中的短向量。

证 矩阵$A\in Z_q^{m\times n}$ 为随机公开矩阵，通过嵌入法将其放到一个更高维度的矩阵B当中。此时我们通过观察，因为矩阵B是相当于矩阵A和单位矩阵扩充而成，所以矩阵A的秩不会影响到矩阵B是一个满秩矩阵。

此时矩阵B是一个满秩矩阵，由格的定义我们可知，可以将矩阵B可以视作一组基，其整系数线性组合构成了一个格$L\left(B\right)$ 。

现在我们需证明在格$L\left(B\right)$ 中必定存在一向量$v={\left(-e,s\right)}^{{\rm T}}$ 。

对于格中任一向量$\nu$ ，可以将其表示成

$\begin{array}{c}\nu =\left(\begin{array}{cc}{I}_m& A\\ 0& q{I}_n\end{array}\right)\left(\begin{array}{c}{Z}_1\\ Z_2\end{array}\right)\\ =\left(\begin{array}{c}{Z}_1+A{Z}_2\\ q{Z}_2\end{array}\right)\end{array}$

其中$Z_1,Z_2$ 为任意整数。

若存在向量$\left(\begin{array}{c}-e\\ s\end{array}\right)=\left(\begin{array}{c}{Z}_1+A{Z}_2\\ q{Z}_2\end{array}\right)$ ，则需满足

$Z_1=-e-A{Z}_2$ ,

$Z_2=\frac{s}{q}$ ,

由于$\text{s}\equiv q{Z}_2$ ，不妨设$Z_2=s-kq$ ，k为整数。此时

$\begin{array}{c}{Z}_1=-e-A{Z}_2\\ =-e-A\left(s-qk\right)\\ =-b+kqA.\end{array}$

当取$k=0$ 时，有

$Z_1=-e-As=-b$ ,

$Z_2=s$ .

故我们可知，当$Z_1=-b,Z_2=s$ 时，在格$L\left(B\right)$ 中存在向量$v$ ，满足$v=\left(-e,s\right)$ 。由于$\text{e}\in Z^m$ 是小误差向量，且秘密向量$s$ 长度较小，故我们可知向量$v$ 是一个近似短向量。这样我们就将LWE问题转化为一个代数学问题，其解向量由私钥和误差向量组成。然后我们通过LLL算法与BKZ算法来进行其解向量的求解。

Kannan嵌入是一种简单通用但效率受限的求解工具，其优势在于理论直观和算法复用性，可以将LWE问题转化成代数学问题，但在高维或高精度需求场景下表现不佳。实际应用中，常需与其他技术(如预处理基规约、参数调优)结合，以平衡效率和解的质量。