1
$\begingroup$

In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm. What is the intuition behind canonical-embedding?

$\endgroup$

1 Answer 1

4
$\begingroup$

Consider the $m^{\text{th}}$ cyclotomic ring $R = \mathbb{Z}[\zeta] \cong \mathbb{Z}[X]/\Phi_m(X)$, where $\zeta$ is the $m$th primitive root of unity and $\Phi(X)$ is the $m$th cyclotomic polynomial. There are many possible bases for this ring, including the power basis $\{ \zeta^0, \zeta^1, \ldots, \zeta^{n-1}\}$, where $n = \phi(m)$ (Euler totient function).

In lattice crypto, it is useful to have a notion of a short ring element. The metric used is often a function of the coefficients of the polynomial in $R$. However, different bases of this ring can result in different coefficients, including cases where 'short' elements have long coefficient vectors.

It is necessary, then, to define geometric quantities independently of the basis representation of $R$. This the use of the canonical embedding $\sigma$, which creates a map $\sigma\colon R \mapsto \mathbb{C}^n$ that is independent of the representation of $R$. $$ a \in R, \ \ \sigma(a) = \left<a(\zeta_m^i)\right> \ \ \text{for all } i \in (\mathbb{Z}/m\mathbb{Z})^* $$We can now define all geometric quantities with respect to the canonical embedding. This results in a 'canonical embedding norm' which is really just any norm taken with respect to the canonical embedding. E.g. For $a \in R$, $||a||_2^{can} = ||\sigma(a)||_2$ or $||a||_\infty^{can} = ||\sigma(a)||_\infty$

There are many other useful properties of the canonical embedding, such as coordinate-wise addition and multiplication.

$\endgroup$
6
  • $\begingroup$ Thanks @leo, Is $\sigma(\alpha)$ itself a kind of fourier transform? $\endgroup$
    – mallea
    Aug 18, 2017 at 19:19
  • $\begingroup$ Yep! this procedure is very related to the Vandermonde matrix over the complex primitive m roots of unity, which is the DFT matrix $\endgroup$
    – cryptocog
    Aug 18, 2017 at 20:17
  • $\begingroup$ Hi, could you please give me the intuition of a ring constant? It seems to depend on the index of $\Phi_m(X)$,i.e. $m$ though... I'm also interested in how to decide the value of the constant given $m$. $\endgroup$
    – mallea
    Aug 25, 2017 at 18:04
  • $\begingroup$ Hi, I'm not sure what you mean by a ring constant. Could you give reference that uses this concept? $\endgroup$
    – cryptocog
    Sep 6, 2017 at 14:11
  • $\begingroup$ Hi there is the concept in eprint.iacr.org/2012/099.pdf Appendix A.2. $\endgroup$
    – mallea
    Sep 6, 2017 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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