$\ell_2$-norm vs canonical embedding norm on ring-lwe

Question

Ring-LWE based encryption (I pick up homomorphic encryption here) requires canonical embedding norm rather than $\ell_2$ norm to quantify the polynomial size (e.g. noise).

Why is this better than $\ell_2$ norm?

Isn't $\ell_2$ norm always be correct?

Canonical embedding is just a embedding which maps a ring element to a complex element by evaluating the original polynomial by complex $n$-th roots of unities, where $n$ is the degree of base polynomial. Canonical embedding norm is taking a maximum of the complex numbers (Since we evaluate a polynomial by $n$-distinct complex root of unities, we have $n$-dimensional vector, i.e. point-value representation of the original polynomial).

Answer 1

I think you are mixing up some concepts... There are two things here: the embedding and the norm.

Those schemes are defined over polynomial rings, but for several reasons (e.g. to relate them with lattice problems, to have some geometry) we want to analyze them in vector spaces.

So, representing those ring elements as vectors is what we call embedding. There are several ways to embed them. For instance:

1. "The naïve way": just represent a polynomial $p(x) = \sum_{i=0}^n a_i$ as a vector $\vec{p} = (a_0, a_1, ..., a_n)$;
2. The canonical embedding: For $1 \le j \le n$, define the isomorphism $\sigma_j$ from $\mathbb{Q}[x] / \langle \Phi_m(x) \rangle$ to $\mathbb{C}$ as $x \mapsto \zeta^j$, where $\zeta$ is an $m$-th root of unity in $\mathbb C$. Then for any polynomial $p(x) = \sum_{i=0}^n a_i$, associate the vector $\vec{p} = (\sigma_1(p), \sigma_2(p), ..., \sigma_n(p)) \in \mathbb{C}^n$.

Once you have an embedding, you can just use the norms as usual, because you are working on a vector space. And that is what papers usually do: they use the $\ell_2$ and the $\ell_\infty$ norms after choosing one method to embedding elements.

Therefore, what you are calling canonical norm is just the usual $\ell_2$ or $\ell_\infty$ on vectors obtained by the canonical embedding.

Maybe what is tricking you is "why to use the canonical embedding instead of the naïve one?". If this is the case, I suggest that you read at least the introduction and the section 2 of A Toolkit for Ring-LWE Cryptography.