1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Could you please provide a definition of that canonical embedding norm just to make sure you are considering the same thing I am? $\endgroup$ – Hilder Vitor Lima Pereira May 7 '18 at 7:55
  • $\begingroup$ Because I am used to papers considering a canonical embedding on a complex vector space then using the $\ell_2$ norm. $\endgroup$ – Hilder Vitor Lima Pereira May 7 '18 at 7:56
  • $\begingroup$ @HilderVitorLimaPereira I updated and I think what you are talking is same as mine. $\endgroup$ – mallea May 7 '18 at 9:03
  • $\begingroup$ @HilderVitorLimaPereira more specifically, see crypto.stackexchange.com/questions/50923/… $\endgroup$ – mallea May 7 '18 at 9:42
4
$\begingroup$

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.

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