 Cryptography

# Trapdoors for Lattices: CCA-secure encryption

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)). ## Solution

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 efcient to evaluate and invert. Concretely, letting $$S \in\mathbb{Z}^{nknk}$$ 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$$