1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Jul 28 '19 at 23:13
  • $\begingroup$ 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. $\endgroup$ – Mark Jul 28 '19 at 23:14
  • $\begingroup$ 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. $\endgroup$ – X.G. Jul 30 '19 at 14:18
  • $\begingroup$ @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. $\endgroup$ – X.G. Jul 30 '19 at 14:26
  • $\begingroup$ 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. $\endgroup$ – Mark Jul 30 '19 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.