I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper.
And the decryption correctness proof of the scheme follows
In this proof , I can get the second last equation in decryption procedure , i.e.
$$\mathbf{m} + (t/q)(\mathbf{v}-\epsilon \cdot \mathbf{m}) + t\cdot \mathbf{r} $$
But for the last equation I don't know why.
$$(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $$
I hava some clues. We already have $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$, then for $2\cdot \delta_R \cdot B^2 + B \lt \Delta / 2$, we have $||\mathbf{v}|| \lt \frac{q}{2t}$ since $\Delta = \lfloor q/t \rfloor \le q/t$. Hence $(t/q)||\mathbf{v}|| \lt \frac{1}{2}$. This is very similar to what we want ,i.e. $(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $.
I guess there is a relation between $||\mathbf{v}||$ and $||\mathbf{v}-\epsilon \cdot \mathbf{m}||$ , but I don't know how to build the relation between them. The proof in the paper have a short explanation "Since $\mathbf{m} \in R_t$" , but I can not understand. Anyone gives some hint would be helpful.
Plus, the norm in this paper in infinity norm.
Edit20220601:
Add some explanation above.
- $\delta_R $ is called the expansion factor of a ring $R$. And $\delta_R = \max{\frac{||a\cdot b||}{||a||\cdot ||b||}},a\in R, b\in R$.
- In the above, we have $\mathbf{v} = \mathbf{e}\cdot \mathbf{u}+ \mathbf{e}_1 +\mathbf{e}_2\cdot \mathbf{s}$, since $\mathbf{e},\mathbf{u},\mathbf{e}_2,\mathbf{s} \in \chi$,so their infinity norm all have bound $B$, then $||\mathbf{e}\cdot \mathbf{u}||= \frac{||\mathbf{e}\cdot \mathbf{u}||}{||\mathbf{e}||\cdot ||\mathbf{u}||}\cdot ||\mathbf{e}||\cdot ||\mathbf{u}|| \le \delta_R \cdot B^2$,similarly, $||\mathbf{e}_2 \cdot \mathbf{s}|| \le \delta_R \cdot B^2$, so we have $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$
