# Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext slot'' in other works (e.g., [SV11]).

Let's focus on the $$m$$-th cyclotomic number field $$K = \mathbb{Q}(\zeta_m)$$ where $$\zeta_m$$ is an abstract element of order $$m = 2^k$$ for some $$k$$. For canonical embedding $$\sigma$$, it is comprised of $$\left| \mathbb{Z}_m^* \right| = \varphi(m)$$ embeddings $$\sigma_i: K \mapsto \mathbb{C}$$. More precisely, $$\sigma_i(\zeta_m) = \omega_m^i$$ and $$\sigma(a) = (\sigma_i(a))_{i \in \mathbb{Z}_m^*}$$ for the primitive $$m$$-th root of unity $$\omega_m$$ and $$a \in K$$. The canonical embedding maps an element in $$K$$ to the vector space $$H$$ which is defined to be $$\begin{gather} H = \{ \textbf{x} \in \mathbb{C}^{\mathbb{Z}_m^*}: x_i = \overline{x_{m-i}},\ \forall i \in \mathbb{Z}_m^* \}. \end{gather}$$ Notice that $$x_i = \overline{x_{m-i}}$$ holds for all $$i \in \mathbb{Z}_m^*$$. So using canonical embedding, it seems that there are only $$\varphi(m)/2$$ instead of $$\varphi(m)$$ ''slots'' for an vector in $$H$$ to encode complex numbers. If we want to encode a vector $$\mathbf{v}$$ of real numbers into an element in $$K$$ via $$\sigma^{-1}$$, is it true that the number of elements in $$\mathbf{v}$$ should be at most $$\varphi(m)/2$$ instead of $$\varphi(m)$$? (Question 1)

To generate plaintext slots, we can apply Chinese Remainder Theorem (CRT) to the polynomial ring $$R_p = \mathbb{Z}_p[X]/\Phi_m(X)$$ for the $$m$$-th cyclotomic polynomial $$\Phi_m(X)$$. Note that $$\Phi_m(X) = \prod_{i \in \mathbb{Z}_m^*} (X - \zeta_m^i) \mod p$$ where $$(\zeta_m)^m \equiv 1 \mod p$$ and CRT will result in $$\varphi(m)$$ slots for component-wise addition and multiplication. This CRT is indeed a kind of number-theoretic transform (NTT) by evaluating some polynomial $$b \in R_p$$ at $$b(\zeta_m^i)$$ for $$i \in \mathbb{Z}_m^*$$, which is quite similar to the situation where the embedding $$\sigma_i$$ is applied to $$\mathcal{O}_K$$, the ring of integers of $$K$$. Why do we have $$\varphi(m)$$ slots here while there are only $$\varphi(m)/2$$ ''slots'' in canonical embedding? (Question 2)

Many thanks

My understanding (updated on 29/07/19)

It seems that the difference between canonical embedding and plaintext slot comes from the difference between $$\omega_m$$ and $$\zeta_m$$, in which $$\omega_m^m = 1 \in \mathbb{C}$$ and $$\zeta_m^m = 1 \in \mathbb{Z}_p$$. For some $$a \in \mathcal{O}_K$$ and $$i \in \mathbb{Z}_m^*$$, we have $$\begin{gather} \sigma_i(a) = a(\omega_m^i) = a(\overline{\omega_m^{m-i}}) = \overline{a(\omega_m^{m-i})} \in \mathbb{C}, \end{gather}$$ in which the last equality is derived from the property of complex conjugate. The last equality implies that once one half of the $$\sigma_i(a)$$'s are fixed, the rest of them will be fixed as complex conjugate, which results in the factor $$1/2$$. However, note that there is no counterpart of this property of complex conjugate in $$\mathbb{Z}_p$$. That is, for some $$b \in R_p$$, $$\begin{gather} b(\zeta_m^i) = b((\zeta_m^{m-i})^{-1}) \neq (b(\zeta_m^{m-i}))^{-1} \mod p. \end{gather}$$ So it is safe to encode different values to the $$\varphi(m)$$ slots and there must exist a coresponding polynomial in $$R_p$$ using NTT.

Am I right?

• While this isn't a full answer, one thing to note is that $\mathbb{Q}(\zeta_m)$ is a dimension $\varphi(m)$ field extension over $\mathbb{Q}$, but $H$ is a dimension $\varphi(m)/2$ field over $\mathbb{C}$. Using $\mathbb{C}\cong\mathbb{R}^2$, you get that $H$ is actually a $\varphi(m)$ field over $\mathbb{R}$. This is a way of looking at things to get the dimensions to match up, although $\mathbb{Q}$ being countable and $\mathbb{R}$ being uncountable is an obstacle to this being the full argument. – Mark Jul 28 '19 at 23:13
• Of course since the embedding isn't a bijection, there's no need for them to have the same cardinality. Still, computing $\sigma^{-1}$ would require having some good description of its domain, which is left out of the above argument. – Mark Jul 28 '19 at 23:14
• To encode a vector of reals, one may abandon the imaginary part of each entry in $\mathbb{C}_{\mathbb{Z}_m^*}$. This will result in one half of the vector is identical to the other half. The inverse mapping $\sigma^{-1}$ is similar to fast fourier transform (FFT), I think. – X.G. Jul 30 '19 at 14:18
• @Mark, thank you for your helpful comments. It takes me a day to think about the isomorphism $\mathbb{C}\cong\mathbb{R}^2$. Of course we have such unitary matrix B (c.f., Section 2.2 in LPR13 ) that contributes to the isomorphism $H \mapsto \mathbb{R}^{\varphi(m)}$. However, it seems that the conponent-wise addtion and multipilication in $H$ cannot be transfromed into $\mathbb{R}^{\varphi(m)}$ using B. So, although we have dimensions match up, we still have $\varphi(m)/2$ space in $H$ to encode reals. – X.G. Jul 30 '19 at 14:26
• I think you're assuming that if we want to encode an element with real coefficients in $\mathbb{Q}(\zeta_m)$ (so $\varphi(m)$ coefficients), we can do it by encoding an element with real coefficients in $H$ (so $\varphi(m)/2$ real coefficients). This isn't the case, because $\sigma$ doesn't map real numbers to real numbers (note that specifically $\sigma(1) = \zeta_m$ is complex). In general, you're asking about the "canonical" or "minkowski" embedding, of which there are non-cryptographic resources you can consult. It might be useful for you to try some explicit computations with a CAS. – Mark Jul 30 '19 at 19:41