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

Could you please provide a definition of that canonical embedding norm just to make sure you are considering the same thing I am? — Hilder Vitor Lima Pereira, May 07 '18 at 07:55
Because I am used to papers considering a canonical embedding on a complex vector space then using the $\ell_2$ norm. — Hilder Vitor Lima Pereira, May 07 '18 at 07:56
@HilderVitorLimaPereira I updated and I think what you are talking is same as mine. — mallea, May 07 '18 at 09:03
@HilderVitorLimaPereira more specifically, see https://crypto.stackexchange.com/questions/50923/what-is-the-intuition-of-canonical-embedding-in-homomorphic-encryption-based-on — mallea, May 07 '18 at 09:42

Hilder Vitor Lima Pereira · Answer 1 · 2021-04-01T14:33:10.110

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:

"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)$;
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.

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

1 Answers1