Canonical inclusion map in subfield attack on overstretched NTRU

Question

I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does the canonical inclusion map relative to finite fields mean? And where can I read more about this construction?

Answer 1

When $\mathbb{L}$ is a subset (or can be view as a subset) of $\mathbb{K}$, the canonical inclusion map just means "take an element of $\mathbb{L}$ and treat it as element of $\mathbb{K}$".

In general, we do it implicitly and it is not necessary to think about it. For example, when we multiply a real number $r$ by a complex number $a + bi$, we are actually representing $r$ as $r + 0i$ and using the complex number multiplication.

Most probably, the authors defined this map explicitly to keep things formal and because $\mathbb{L}$ and $\mathbb{K}$ have different dimensions when view as vector spaces over $\mathbb{Q}$, so they want to make sure that there would be no confusion about how to compute the norms and other quantities of elements of $\mathbb{L}$ when we use them as elements of $\mathbb{K}$.

For exemple, if $\mathbb{L} := \mathbb{Q}(\sqrt 2)$ and $\mathbb{K} = \mathbb{Q}(\sqrt 2, \sqrt 5)$, then, the elements of $\mathbb{L}$ are of the form $a_0 + a_1\sqrt 2$ and those of $\mathbb{Q}$ are $a_0 + a_1\sqrt 2 + a_2\sqrt 5 + a_3\sqrt{10}$. Moreover, $\mathbb{L}$ can be seen as a vector space of dimension $2$ and $\mathbb{K}$ as a vector space of dimension $4$ over $\mathbb{Q}$.

Thus, it is clear that we can see elements of $\mathbb{L}$ as elements of $\mathbb{K}$ with $a_2 = a_3 = 0$. Thus, when you use the canonical inclusion map from $\mathbb{L}$ to $\mathbb{K}$, you are also taking vectors of dimension $2$ and using them as vectors of dimension $4$.

All that said, notice that the authors do not simply use the canonical inclusion map to lift elements of $\mathcal{O}_{\mathbb{L}}$ to $\mathcal{O}_{\mathbb{K}}$, as they want to guarantee some properties after lifting (like lifted elements being multiples of the secret NTRU vector $(f, g)$ and being small).