The Learning With Error (LWE) problems have received a lot of attention mostly because of the application to the PQ cryptography. Here we give the definitions of standard LWE and the generalized Ring-LWE which has become more popular due to cheaper operations.
Standard LWE
Firstly, let’s observe classic LWE where we fix an error distribution $\mathcal{X}\colon \mathbb{Z}_p \rightarrow \mathbb{R}$. Basically, the error is always a small number such that $|e| \leq B$. Then, for the vector $\mathbf{s} \in \mathbb{Z}_p^n$ we put the Learning With Errors search problem as follows:
-
LWE-Search Problem
For a uniformly random $\mathbf{a} \in \mathbb{Z}_p^n$ and error $e$ with distribution $\mathcal{X}$ we put
\[b = \langle\mathbf{a}, \mathbf{s}\rangle + e \in \mathbb{Z}_p.\]The problem itself is to find $\mathbf{s}$ for known $\mathbf{a}$ and $b$.
-
LWE-Decision Problem
For given $\mathbf{a} \in \mathbb{Z}_p^n$ and $b \in \mathbb{Z}_p$ we should determine if:
- (a) $b$ is a uniformly random value from $\mathbb{Z}_p$, or
- (b) $b = \langle\mathbf{a}, \mathbf{s}\rangle + e$ for some error $e$ with distribution $\mathcal{X}$ and $\mathbf{s} \in \mathbb{Z}_p^n$.
Ring-LWE
Next, we put a ring $R = \mathbb{Z}_p/f(x)$ where $\deg f(x) = N$. Obviously, this ring consists of polynomials of degree at most $N$, where the coefficients are values in $\mathbb{Z}_p$, with addition and multiplication being done according to the polynomial addition and multiplication rules and modulo $f(x)$.
Let’s put the error polynomial distribution as $\mathcal{X}_{R,\delta}\colon R \rightarrow \mathbb{R}$, where the polynomial coefficients are distributed normally with mean $0$ and standard deviation $\delta$. We also note that each coefficient’s absolute value is at most $B$.
Then, for the polynomial $s \in R$ we define the corresponding search and decision problems as follows:
-
Ring-LWE-Search Problem
For a uniformly random polynomial $a \in R$ and error $e$ with distribution $\mathcal{X}_{R,\delta}$ we put \(b = a \cdot s + e \in R.\)
The problem itself is to find the polynomial $s$ for known polynomials $a$ and $b$.
-
Ring-LWE-Decision Problem
For given $a \in R$ and $b \in R$ we should determine if:
- (a) $b$ is a random polynomial from $R$, or
- (b) $b = a \cdot s + e$ for some error $e$ with distribution $\mathcal{X}_{R,\delta}$ and $s \in R$.
Basically, the idea behind modern cryptosystems that leverage RingLWE problems is to use $(a,b)$ as the public key and $s$ as the private key.