CKKS encoding notation and doubt with why project to base

Question

I'm trying to understand CKKS (non bootstrappable) and I'm struggling with the encoding part. Particularly with to questions. I'm using the original paper , "Homomorphic Encryption for Arithmetic of Approximate Numbers ", also this notes "Lattices, Homomorphic Encryption, and CKKS" and this blog.

Given a vector $z\in \mathbb{C}^{N/2}$ they use the canonical embedding $\sigma^{-1}$ to map it to $\mathcal{R} =\mathbb{Z}[X]/(X^N+1)$. So you want $\sigma^{-1}:z\to\mathcal{R}$. First they expand (or projects) z adding the complex conjugates so $\pi^{-1}(z)\in\mathbb{H}\subset \mathbb{C}^{N}$.

First question.

1. They use this notation for the space of this expansion that I don't understand: $\mathbb{H}=\{(z_j)_{j\in \mathbb{Z}^{*}_M}:z_{-j}=\overline{z_j},\forall j\in\mathbb{Z}_M^*\}\subseteq \mathbb{C}^{\Phi(M)}$

Where $T$ is a subgroup of the multiplicative group $\mathbb{Z}^*_M$ satisfying $\mathbb{Z}^*_M/T=\{\pm1\}$ and $\Phi(M)$ is the M-th Cyclotomic polynomial (I think... here it change a little bit the notation of this, the "original" was $\Phi_M(X)$).

1.1) So what it means that something is a subset of $\mathbb{C}^{\Phi(M)}$? This is really $\mathbb{C}^{N}$?

1.2) What this formula means in english? I know what the expansion do. Example: $\pi_{-1}((1+2i, 3-4i))\to (1+2i, 3-4i, 3+4i, 1-2i)$, but can't figure out the notation.

Second question.

2. Before they apply $\sigma^{-1}$ to $\pi^{-1}(z)$ they need to use a round-off algorithm to discretize so that the output becomes an integral polynomial. Because they say that an element of $\mathbb{H}$ is not necessarily in $\sigma(\mathcal{R})$. Why?

2.1) This is because an particular element of $\mathbb{H}$ may be imposible to create with the base of $\sigma(\mathcal{R})$?

Answer 1

1. You don't mention $T$ in your definition of $\mathbb{H}$. Still, the idea is that it's a mathematical fact that the embeddings $\sigma_i$ (for $i\in(\mathbb{Z}/N\mathbb{Z})^*$, i.e. there are $\varphi(N)$ total, which for $N = 2^k$ is $2^{k-1} = N/2$) come in two kinds

   a. "Real embeddings" --- meaning the image of $\sigma_i$ is a subset of $\mathbb{R}\subseteq \mathbb{R}$

   b. "Conjugate Pairs" --- meaning there are a pair of embeddings $(\sigma_i, \sigma_j)$ such that $\sigma_i(x) = \overline{\sigma_j(x)}$ are related by complex conjugation.

   I believe this notation $\mathbb{H}$ is an (explicit) way of describing these second type of embeddings (I don't think cyclotomics have real embeddings). Conceptually, one can view $\mathbb{Y}$ as being made entirely of these "conjugate pairs", so (as you say) you add conjugate pairs if they are missing.

1.1 No. In general, for a number field $K$, it embeds into $\mathbb{C}^M$ for $M$ the order of the "Galois group" (= number of embeddings into $\mathbb{C}$). For a cyclotomic of degree $N$, then $M = |\mathsf{Gal}(K/\mathbb{Q})| = \varphi(N)\neq N$. For $N = 2^k$ a power of two, $M = \varphi(N) = 2^{k-1} = N/2\neq N$. Note that for power-of-two cyclotomics, we do have that it embeds into $\mathbb{C}^M = \mathbb{C}^{N/2}\cong\mathbb{R}^N$, but this is really a coincidence.

1.2. In english, given a polynomial $a(x) = \sum_i a_ix^i$, $\sigma_j(a)$ is given by evaluating it at $\zeta_N^j = \exp(2\pi ij/N)$ for $j\in(\mathbb{Z}/N\mathbb{Z})^*$. As mentioned, these come in conjugate pairs, as $\overline{\zeta_N} = \zeta_N^{-1}$ (so $\overline{\sigma_i} = \sigma_{-i\bmod N}$).

2. $\mathbb{H}$ is the image of $\mathbb{R}^N$ under all of the relevant embeddings. Instead, we (roughly) want the image of $\mathbb{Z}^N$ under all of the relevant embeddings. So morally, $\mathbb{H}\neq \sigma(\mathcal{R})$ for similar reasons why $\mathbb{Z}^N\neq \mathbb{R}^N$.

2.1 Yes, at least with integer coefficients. If you use arbitrary real coefficients you can do it (I'm pretty sure), but this isn't useful for cryptography.