## # An LWE-Based Encryption Scheme

Consider such an encryption scheme:

\begin{aligned} & sk:\textbf{s}\leftarrow[\beta]^m\\ & pk:(\textbf{A},\textbf{t})= (\textbf{A}\leftarrow \mathbb{Z}_q^{m\times m},\textbf{t}=\textbf{As}+\textbf{e}_1),\textbf{e}_1\leftarrow [\beta]^m \end{aligned}

where $[\beta]=\{-\beta,...,-1,0,1,...,\beta\}$. To encrypt a message $\mu\in\{0,1\}$, the encryptor chooses $\textbf{r},\textbf{e}_2\in[\beta]^m,e_3\in[\beta]$ and compute:

$(\textbf{u}^T,v)=(\textbf{r}^T\textbf{A}+\textbf{e}_2^T,\textbf{r}^T\textbf{t}+e_3+\lceil q/2\rfloor\mu)$

where $\lceil q/2\rfloor$ is the nearest number to $q/2$.

To decrypt:

1. Compute:

\begin{aligned} v-\textbf{u}^T\textbf{s}&=\textbf{r}^T\textbf{t}+e_3+\lceil q/2\rfloor \mu-\textbf{r}^T\textbf{As}-\textbf{e}_2^T\textbf{s}\\ &=\textbf{r}^T(\textbf{As}+\textbf{e}_1)+e_3+\lceil q/2\rfloor \mu-\textbf{r}^T\textbf{As}-\textbf{e}_2^T\textbf{s}\\ &= \textbf{r}^T\textbf{e}_1+e_3+\lceil q/2\rfloor \mu -\textbf{e}_2^T\textbf{s} \end{aligned}

2. Since $\textbf{r},\textbf{e}_1,\textbf{s},\textbf{e}_2\in [\beta]^m,e_3\in[\beta]$, so $\textbf{r}^T\textbf{e}_1\in [m\beta^2],\textbf{e}_2^T\textbf{s}\in[ m\beta^2],e_3\in[\beta]$, then

$v-\textbf{u}^T\textbf{s}\in [2m\beta^2+\beta]+\lceil q/2\rfloor \mu$

3. If the choice of parameters $m,\beta$ satisfies $2m\beta^2+\beta, then the decryptor can just determine:

$\mu=\begin{cases} 1 & v-\textbf{u}^T\textbf{s}\textnormal{ is more close to q/2}\\ 0 & v-\textbf{u}^T\textbf{s}\textnormal{ is more close to 0} \end{cases}$

The security of scheme is based on the difficulties of the following problem:

Definition(Learning With Error, LWE): For positive integers $m, n, q$, and $\beta \ll q$, the $\textnormal{LWE}_{n,m,q,\beta}$ problem asks to distinguish between the following two distributions:

• $(\textbf{A},\textbf{As}+\textbf{e})$, where $\textbf{A}\leftarrow \mathbb{Z}_q^{n\times m},\textbf{s}\leftarrow[\beta]^m,\textbf{e}\leftarrow [\beta]^n$.
• $(\textbf{A},\textbf{u})$, where $\textbf{A}\leftarrow \mathbb{Z}_q^{n\times m},\textbf{u}\leftarrow \mathbb{Z}_q^n$.

We assume the that the problem is hard, i.e. the two distribution is indistinguishable. The LWE problem has been proven to have a reduction to the difficult problem in lattice problem.

The public key $(\textbf{A},\textbf{t})$ is indistinguishable from uniform distribution due to the LWE assumption,