Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller, Micciancio and Peikert proposed a CCA-secure encryption.
However, I am confused about the step in decryption algorithm (p.36 Lemma 6.2.).
That is, $\mathbf{v}^t \begin{bmatrix} R \\I \end{bmatrix} = 2(\mathbf{s}^th(u)\mathbf{G}$ mod $q$) + encode(m) mod $2q$.
And why $2(\mathbf{s}^th(u)\mathbf{G}$ mod $q) = 0$ mod $2q$, such that decode($\mathbf{v}^t \begin{bmatrix} R \\I \end{bmatrix})$ = decode(encode(m)).
You misunderstand what "decode" does. As mentioned earlier in the paper:
The system has message space $\{0,1\}^{nk}$, which we map bijectively to the cosets of $\Lambda/2\Lambda$ for $\Lambda = \Lambda(G^t)$ via some function encode that is efficient to evaluate and invert. Concretely, letting $S \in\mathbb{Z}^{nk×nk}$ be any basis of $\Lambda$, we can map $m \in\{0,1\}^{nk}$ to $encode(m) = Sm \in\mathbb{Z}^{nk}$.
This is to say that encode is a function from $\{0,1\}^{nk}\to \Lambda/2\Lambda$, and decode is therefore a function from $\Lambda/2\Lambda\to\{0,1\}^{nk}$. Note that your expression is of the form:
$$\underbrace{2(\overbrace{s^th(u)G\bmod q}^{\in\Lambda})}_{\in 2\Lambda} + \overbrace{encode(m)\bmod 2q}^{\in \Lambda/2\Lambda}$$ Note that $\Lambda/2\Lambda$ is (by construction) invariant under translation by elements of $2\Lambda$. The construction is simply adding an element of $2\Lambda$ to $encode(m)$, which by the aforementioned invariance will not impact decoding. Note that this may map the particular representative you've chosen of $\Lambda/2\Lambda$ to a different representative, but all of these representatives are viewed as "the same" in $\Lambda/2\Lambda$.
Concretely, consider if you have $\Lambda = \mathbb{Z}$. Say $encode(m) = b\in\mathbb{Z}/2\mathbb{Z}$. If you add an element of $2\mathbb{Z}$ to this, you'll get something of the form $b + 2k$ for $k\in\mathbb{Z}$ (abbreviated as $b + 2\mathbb{Z}$). But $decode(b + 2\mathbb{Z})$ is a function from $\mathbb{Z}/2\mathbb{Z}$ to the message space --- it should be the same for any particular representative of an element of $\mathbb{Z}/2\mathbb{Z}$ you give it, so you should freely add any element of $2\mathbb{Z}$ to it without impacting the correctness of decoding.
To be even more concrete, in this situation $decode$ is a function that says "I only care if my input is even or odd, no other details matter". Since adding an even number to any other number doesn't impact its parity, you have that: $$decode(encode(m) + 2\mathbb{Z}) = m$$ Similarly, in the protocol we have that: $$decode(encode(m) + 2\Lambda) = m$$
