# Correctness Proof of GLWE-based Encryption

While reading a GLWE-based encryption described in section 3.1 of BGV12. The paper says that correctness is obvious and it only became obvious to me after a bit. This should cover most of the proof outline.

Proof: We have to show that the dot product of $\textbf{c}$ and $\textbf{s}$ reduces to the message. Let $\textbf{b}_i$, $\textbf{r}_i$, and $\textbf{s}'_i$ be the $i$th element in $\textbf{b}$, $\textbf{r}$, and $\textbf{s}'$ respectively. We will zoom in the construction of $\textbf{b}$ as a start. Remember that it’s defined as $\textbf{b} \leftarrow \textbf{A}'\textbf{s}'+2\textbf{e}$. I will notate $a'_{ij}$ to be the element of the matrix $\textbf{A}'$.

We have $\textbf{c}=\textbf{m}+\textbf{A}^T \textbf{r}$. $\textbf{c}=$ $\begin{bmatrix} m \\ 0 \\ \vdots \\ 0 \end{bmatrix}$ + $% $ = $\begin{bmatrix} m + b_1 r_1 + \dots + b_N r_N\\ -a'_{11} r_1 - \dots -a'_{N1} r_N\\ \vdots\\ -a'_{1n} r_1 - \dots -a'_{Nn} r_N \end{bmatrix}$

Now performing the dot product $\langle \textbf{c}, \textbf{s}\rangle$ we get: $\textbf{c} \cdot \textbf{s} = \begin{bmatrix} m + b_1 r_1 + \dots + b_N r_N\\ -a'_{11} r_1 - \dots -a'_{N1} r_N\\ \vdots\\ -a'_{1n} r_1 - \dots -a'_{Nn} r_N \end{bmatrix} \cdot \begin{bmatrix} 1 \\ s'_1 \\ \vdots \\ s'_n \end{bmatrix} = m+\sum_{k=1}^N r_k ( b_k - \sum_{l=1}^n a'_{1l} s_l)$ Note that in $\textbf{b}$ we can neglect $2\textbf{e}$ to compute our message since it’s $0 \mod 2$. For any $r_k=1$ we have the term $b_k$ to be equal to the inner summation module 2. Thus, we will be left with $m$.