0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.