Posted on: April 30, 2026 | Reading time: 13 minutes | Word count: 2733 words | Author: Dang Duong Minh Nhat
Hello everyone, it has been a long time since the last post. I glad to share you that this March, I had a change to attend to Mini-course: Introduction to Lattice-based cryptography of Professor Alfred Menezes at Vietnam Institute for Advanced Study in Mathematics (VIASM). There are two main parts in this mini-course, the first part is about the Lattice, which we have already covered in the previous posts, so in this post, we will cover the second part, which is about the Learning With Errors problem. This is one of the most important problems in modern post-quantum cryptography. To better understand this blog, I advice you to read other posts in the series. Okey, let’s start!
Learning with errors problem
Learning with errors problem depends on four parameters, including two integers $m$ and $n$ with $m \gg n$, a modulus prime $q$, and a noise bound $B$ satisfying $B \ll q/2$.
Observe that if $B = 0$, then we absolutely have $e = 0$; therefore, the problem becomes problem of solving the linear equation $As=b \pmod{q}$, which we can easily find the solution $s$ by using Gaussian elimination. So, the dificulty of LWE problem is due to $e$, then we assume that $B \ne 0$.
Because we also have $m$ is much greater than $n$, this leads to the fact that we have the assumption that the solution of the LWE problem is unique with high probability. To explain this, we see that $t = As \pmod{q} \in \mathbb{Z}_q^m$ is a vector in a $q^m$-sized vector space. And each of $s \in \mathbb{Z}_q^n$, we define a circle surrounding elements, called $T_s = {t + e \pmod{q} \ | \ e \in [-B,B]^m}$ with vector $t$ is center and there are $| T_s | = (2B + 1)^m$ elements in a circle, and each element is the result $b$ of the LWE problem. Also, we the number of $s$ values is $q^n$, so the total area of all cicles is $q^n(2B+1)^m \ll q^m$. This leads to the probability of two circles intersecting is very small, so we can say that the solution of the LWE problem is unique with high probability.
The LWE lattice
LWE Lattice. Let a $\text{LWE}(m, n, q, B)$ have instance $(A,b)$, the LWE lattice is defined
$$ L_A = {y \in \mathbb{Z}^m \ : \ y = Az \ \pmod{q} \ | \ z \in \mathbb{Z}^n}. $$
Let $A_1$ be a submatrix $n \times n$ including the first $n$ rows of $A$. With high probability following the way we choose $A$, then $A_1$ is invertible modulo $q$. To better understand, we assume this condition is true. Then, we have the following theorems.
We have that lattice is a linear combination of its basis, and $q\mathbb{Z}^m={(qk_1, \cdots,qk_m)\ : \ k_i \in \mathbb{Z}}$, let
$$ B = \begin{bmatrix} q & 0 & \cdots & 0 \\ 0 & q & \cdots & 0 \\ \vdots & & \ddots & \\ 0 & 0 & \cdots & q \end{bmatrix} = qI_m, $$
then
$$ Bx = qI_m \cdot \begin{bmatrix} k_1 \\ \vdots \\ k_m \end{bmatrix} = \begin{bmatrix} qk_1 \\ \vdots \\ qk_m \end{bmatrix}, $$
so $q\mathbb{Z}^m = { Bx : x \in \mathbb{Z}^m }$ is a lattice with rank $m$.
The next theorem is following.
We easily see that $L_A$ is a discrete additive group in $\mathbb{Z}^m$, so $L_A$ is an interger lattice. We also have $q\mathbb{Z}^m \subseteq L_A$, so $L_A$ contains at least $m$ independent vectors, therefore $L_A$ has full rank $m$. Then, we can rewite $L_A$ as
$$ A = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}, $$
with $A_1 \in \mathbb{Z}_q^{n \times n}$ and $A_2 \in \mathbb{Z}_q^{(m-n) \times n}$. Then, let $D_2 = A_2 A_1^{-1} \pmod{q}$ and the matrix
$$ D = \begin{bmatrix} I_n & 0 \\ D_2 & qI_{m-n} \end{bmatrix} \in \mathbb{Z}^{m \times m}. $$
Now, to prove that $\text{vol}(L_A) = q^{m-n}$, we have to show that $D$ is a basis of $L_A$ and $|\text{det}(D)| = q^{m-n}$. With a random vector $x \in \mathbb{Z}^m$, let
$$ y = Dx = \begin{bmatrix} I_n & 0 \\ D_2 & qI_{m-n} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} x_1 \\ D_2x_1 + qx_2 \end{bmatrix}, $$
this means that we will prove that $y \in L_A$ or exist $z \in \mathbb{Z}^n$ such that $z = Ay \pmod{q}$, that is equal to prove that $x_1 = A_1 z \pmod{q}$ và $D_2x_1 + qx_2 = A_2 z \pmod{q}$ and $D_2x_1 + qx_2 = A_2 z \pmod{q}$ have solution $z$ (this is correct because $z = A_1^{-1}x$ is satisfy). In conclusion, $D$ is basis of $L_A$. And we also have
$$ \det(D) = \det\begin{bmatrix} I_n & 0 \\ D_2 & qI_{m-n} \end{bmatrix} = \det(I_n)\cdot \det(qI_{m-n}) = 1 \cdot q^{m-n} = q^{m-n} $$
because a triangular matrix has determinant is the product of its diagonal blocks. Therefore, $L_A \subseteq \mathbb{R}^m$ is a lattice that is full-rank with volume is $q^{m-n}$.
The hardness of LWE problem
Let LWE problem has instance $(A,b)$ with $b = As+e \pmod{q}$, and we define $y = As \mod{q} \in L_A$. Because the error vector $e \in [-B,B]$, so $\parallel b-y\parallel _2 = \parallel e\parallel _2 \le \sqrt{m}B.$ This means that the lattice vector $y$ is close to the target vector $b$. Therefore, it leads to the natural relationship beteen the LWE problem and the following Bounded Distance Decoding (BDD) problem.
$\text{BDD}_\alpha$ can be considered as a promise version of the problem $\text{CVP}_\gamma$. Next, we will use the embedding technique of Kannan to reduce $\text{BDD}_\alpha$ to SVP problem with assumption that $\alpha < \dfrac{\lambda_1(L)}{\sqrt{2}}$. Let
$$ D’ = \begin{bmatrix} D & -b \\ 0 & \alpha \end{bmatrix} \in \mathbb{R}^{(m+1)\times(m+1)} $$
and the lattice
$$ L’ = L(D’) = \left\lbrace \begin{bmatrix} v - cb \\ c\alpha \end{bmatrix} : v \in L(D),\ c \in \mathbb{Z} \right\rbrace. $$
Consider the case $(v, c) = (y, 1)$, we get the lattice vector
$$ \tilde{v} = \begin{bmatrix} y - b \\ \alpha \end{bmatrix} \in L' $$
with
$$ \parallel \tilde{v}\parallel _2 = \sqrt{\parallel y - b\parallel _2^2 + \alpha^2} \le \sqrt{2}\alpha. $$
So,
$$ \lambda_1(L’) \le \sqrt{2}\alpha < \lambda_1(L). $$
Assume that
$$ v’ = \begin{bmatrix} v - cb \\ c\alpha \end{bmatrix} \in L' $$
is a shortest vector that is not equal to zero, then because of uniqueness of the solution of BDD problem, then
$$ \parallel v - b\parallel _2 > \parallel y - b\parallel _2 \Rightarrow \parallel v’\parallel _2 = \sqrt{\parallel v - b\parallel _2^2 + \alpha^2} > \sqrt{\parallel y - b\parallel _2^2 + \alpha^2} = \parallel \tilde{v}\parallel _2 $$
This is contradiction to the hypothesis that $v’$ is the shortest vector. Therefore, $v’ = \pm \tilde{v}$. This means that the shortest vector in $L’$ is
$$ \pm \begin{bmatrix} y - b \\ \alpha \end{bmatrix} $$
In conclusion, $\pm \tilde{v}$ are the only vectors that have length $\lambda_1(L’)$ in $L’$. Therefore, solving the SVP problem in $L’$ will directly give the solution $y$ of the BDD problem or we can say that if SVP is solved, then BDD is also solved. Returning to the BDD problem with LWE, according to Gaussian heuristic, we have
$$ \lambda_1(L_A) \approx \sqrt{\dfrac{n}{2 \pi e}} \text{vol}(L_A)^{\dfrac{1}{n}}. $$
If we choose the condition that $\sqrt{m}B < \sqrt{\dfrac{n}{2 \pi e}} \text{vol}(L_A)^{\dfrac{1}{n}} = \sqrt{\dfrac{n}{2 \pi e}} q^{\dfrac{m-n}{n}}$ then $\parallel e\parallel _2 < \dfrac{\lambda_1(L)}{\sqrt{2}}$, this means that we can transform the LWE problem to BDD problem and then reduce it to SVP problem by using the embedding technique of Kannan; therefore, we just need to solve the SVP problem over the open lattice to get the solution of the LWE problem.
On the other hand, in the paper of Oded Regev in 2005, he proved that of the approx-SIVP problem is hard in the worst case (in some particular hard cases) with attacks (both in quantum and classical), then the LWE problem is also hard in the average case (this means almost cases), or we can say that there are not any efficient algorithms to sove the problem with the significant probability. To conclude, if we believe that approx-SIVP problem is hard in the worst case, then we must also believe that LWE problem is hard in the average case.
The Decisional LWE problem
This is a variant of the LWE problem, and the problem here is to distinguish the instance of LWE problem $(A,b)$ from the random instance $(A,r)$ with $r \in_R \mathbb{Z}_q^m$ is chosen uniformly at random. In this case, we hope that the equation $As+e=r \pmod{q}$ has no solution (we don’t know exactly the condition of having solution or not).
We have the following theorem.
The idea is to solve the LWE problem can reduce to the DLWE problem (this means that if we can solve the DLWE problem, then we can also solve the LWE problem, notation is $\text{LWE} \le \text{DLWE}$) and the opposite way (notation is $\text{DLWE} \le \text{LWE}$).
Fistly, we will show that $\text{LWE} \le \text{DLWE}$. Let $(A,b)$ be a instance of the LWE problem, that means that $b = As + e \pmod{q}$. Assume that we have a DLWE-solver, which is used to guess $s = (s_1, s_2,\cdots, s_n)$ with each element in a time, starting with $s_1$ (we know that $s$ is existed). This process can consume $qn$ times recursively to determine $s$. For the random $d \in \mathbb{Z}_q$, in order to test whether $s_1 = d$, we choose $\Delta \in_R \mathbb{Z}^m_q$ randomly and caculate the new matrix $A’$ by adding $\Delta$ to the first column of $A$, and caculate $b’=b+ d \Delta$.
If $s_1 = d$, then we have $b’=A’s+e$, so $(A’b)$ is a valid instance of the LWE provlem, therefore, the probability that the DLWE-solver can solve the problem is significantly greater than $\dfrac{1}{2}$, or we can say that the DLWE-solver is successful.
If $s_1 \ne d$, then we have $b’=A’s+e+(d-s_1)\Delta$. Because $d-s_1$ is non-zero, and $\Delta$ is chosen uniformly at random to $A’$, $s$, $e$, this leads to $b’$ is also chosen uniformly at random to $A’$. And if we put the instance $(A’,b’)$ (this is an invalid instance of the LWE problem if $e+(d-s_1)\Delta$ is not equal to zero) tp the DLWE-solver, then it will succeed with the low probabilty, or we can say that DLWE-solver is failed. Therefore, we can determine each element of $s$ and solve the LWE problem.
Next, we will show the reverse way, that is $\text{DLWE} \le \text{LWE}$. Assuming that we have a LWE-solver, we will use it to solve the DLWE problem. We will use DLWE to call the LWE-solver (as the game attack in Cryptography 2: Semantic Security Prevents Message Recovery Attacks — A Security Reduction Proof) and return the result when comparing $c=b$ or $c=r$ (depending on the result that there is a solution or not of the LWE-solver because $As+e=r \pmod{q}$ has no solution).
The ss-LWE problem
In “short-secret” variant of the LWE problem, the secret vector $s$ is chosen from the same distribution as the error vector $e$.
Then we have the following theorem.
The idea of the proof is to show that this problem is not harder than the other problem.
Firstly, we will show that $\text{ss-LWE}(m,n,q,B) \le \text{LWE}(m, n, q, B)$, this means that if we can solve the LWE problem, then we can also solve the ss-LWE problem. Consider an instance of $\text{ss-LWE}(m,n,q,B)$ with $(A,b)$, this means that $b = As +e \pmod{q}$ with $s \in_R [-B,B]^n$ and $e \in_R [-B,B]^m$. Choose a random vector $d \in_R \mathbb{Z}_q^n$ and let $b’ = b + Ad = (As + e) + Ad = A(s+d) + e \pmod{q}$. Then, $(A, b’)$ is an instance of $\text{LWE}(m,n,q,B)$. If $(s’,e)$ is the solution of this LWE instance, then $(s’-d,e)$ is the solution of the original ss-LWE instance. Therefore, the ss-LWE problem is not harder than the LWE problem because the LWE problem is enough to solve the ss-LWE problem.
Next, we will show that $\text{LWE}(m, n, q, B) \le \text{ss-LWE}(m - n,n,q,B)$. We assume that $(A,b)$ is an instance of $\text{LWE}(m, n, q, B)$, this means that $b = As +e \pmod{q}$. We can rewrite the matrix $A$, the vectors $b$ and $e$ as
$$ A = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}, \quad b = \begin{bmatrix} b_1 \\ b_2 \end{bmatrix}, \quad e = \begin{bmatrix} e_1 \\ e_2 \end{bmatrix}, $$
such that $A_1 \in \mathbb{Z}_q^{n\times n}$, $A_2 \in \mathbb{Z}_q^{(m - n)\times n}$, $b_1, e_1 \in \mathbb{Z}_q^n$ and $b_2, e_2 \in \mathbb{Z}_q^{m-n}$. Assume that $A_1$ is invertible modulo $q$ (if not, we can permutate the rows to make it invertible), let $A’ = -A_2A_1^{-1} \in \mathbb{Z}_q^{(m-n)\times n}$ and $b’ = A’b_1 + b_2 \in \mathbb{Z}^{m-n}_q$. Then, we have
$$ \begin{aligned} b’ &= A’ b_1 + b_2 \\ &= (-A_2 A_1^{-1})(A_1 s + e_1) + (A_2 s + e_2) \\ &= -A_2 s - A_2 A_1^{-1} e_1 + A_2 s + e_2 \\ &= A’ e_1 + e_2. \end{aligned} $$
Therefore, $(A’,b’)$ is an instance of $\text{ss-LWE}(m - n,n,q,B)$. Then, solving this ss-LWE instance will give us $e_1$, and then we can recover immediately the orginal secret, and therefore, we can solve the original LWE instance. In conclusion, $\text{LWE}(m,n,q,B) \le \text{ss-LWE}(m-n,n,q,B)$.
Finally, we have the same definition below.
Decisional short-secret LWE problem, notation is $\text{ss-DLWE}(m,n,q,B)$. Given $A \in_R \mathbb{Z}_q^{m \times n}$, $s \in_R [-B,B]^n$, $e \in_R [-B,B]^m$, $r \in_R \mathbb{Z}_q^m$. Let $b = As + e \ (\mathrm{mod}\ q) \in \mathbb{Z}_q^m$. Given
$$ d = \begin{cases} b & \text{with probability } \dfrac{1}{2}, \\ r & \text{with probability } \dfrac{1}{2}. \end{cases} $$
Given the instance $(A, d)$, the target is to determine whether $b=d$ of $d=r$ with the successful probability is significantly greater than $\dfrac{1}{2}$.
The Learning With Errors problem sits at the heart of modern lattice-based cryptography. We have shown that the LWE lattice $L_A$ is a full-rank lattice with volume $q^{m-n}$, and that solving LWE reduces naturally to the Bounded Distance Decoding problem, which in turn reduces to SVP via Kannan’s embedding technique. Crucially, Regev’s 2005 result establishes that if the worst-case approximate SIVP is hard, then LWE is hard on average — providing a strong theoretical foundation for its use in cryptography. We also demonstrated that the decisional variant DLWE and the short-secret variant ss-LWE are each computationally equivalent to the standard LWE problem, making all three interchangeable as hardness assumptions in cryptographic constructions. In the next post, we will build on these foundations to construct concrete cryptographic schemes from LWE.
References
- Alfred Menezes. (2025, April 30). A Gentle Introduction to Lattice-Based Cryptography. Retrieved from https://drive.google.com/file/d/1-G9qYuQhuHr0W4-YglVGub1PxdLyFHC6/view
- Alfred Menezes. Textbook of Applied Cryptography. Retrieved from https://drive.google.com/file/d/1xGAODc0PyMvH65spbGBCW-Xgkbe0leif/view
Connect with Me
Connect with me on Facebook, LinkedIn, via email at dangduongminhnhat2003@gmail.com, GitHub, or by phone at +84 829 258 815.