Basic LWE Problem

经历春天观赏夜樱，夏天挂玉菊，秋天听仁和贺戏，四季变换，而这条街始终喧嚣热闹，门前的这条大街，10 分钟不到就有 75 辆车来来往往。

# 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<q/4$, 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:

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