In quick post, we will prove how the complex space $$\mathbb{H} = \{[\mathbf{z} = (z_j)_{j \in \mathbb{Z}_M^*} \in \mathbb{C}^N : z_j = \bar{z_{-j}}, \forall j \in \mathbb{Z}_M^*\}$$ is isomorphic to $\mathbb{R}^N$
This property is fundamental to the CKKS cryptosystem. Let’s prove it in two ways.
The Quick Proof: Counting Real Numbers
The isomorphism becomes clear when we simply count the “degrees of freedom” required to define a vector in $\mathbb{H}$.
The key is the constraint: $z_j = \bar{z}_{-j}$.
A general vector in $\mathbb{C}^N$ requires $N$ complex numbers. Since each complex number has a real and an imaginary part, this is a total of $2N$ real numbers.
The constraint links the components into $N/2$ pairs of the form $(z_j, z_{-j})$.
Let’s look at one pair. If we freely choose $z_j = a_j + i b_j$, we have picked two real numbers ($a_j$ and $b_j$). The constraint immediately fixes the value of its partner:
$$z_{-j} = \overline{z_j} = a_j - i b_j$$
So, two real numbers are sufficient to define two complex numbers in the vector.To define the entire vector $\mathbf{z}$, we must specify the $N/2$ independent components. Each requires 2 real numbers.
Total real numbers needed = $(\text{Number of independent components}) \times (\text{Real numbers per component})$
$$= \frac{N}{2} \times 2 = N$$
Since any vector in $\mathbb{H}$ can be uniquely specified by exactly $N$ real numbers, the space $\mathbb{H}$ is isomorphic to $\mathbb{R}^N$.
The Formal Proof: The Isomorphism Matrix
This isomorphism can be formally constructed by a unitary matrix $U$. This matrix provides a map $f: \mathbb{R}^N \to \mathbb{H}$ that takes a real vector $\mathbf{x}$ and constructs a valid complex vector $\mathbf{z} \in \mathbb{H}$ via the operation $\mathbf{z} = U\mathbf{x}$.
Definition: Let $I$ be the $(N/2) \times (N/2)$ identity matrix and $J$ be the reversal matrix ($J^2=I$). The isomorphism matrix $U$ is defined as:
$$U = \frac{1}{\sqrt{2}}\begin{pmatrix} I & iJ \\ J & -iI \end{pmatrix}$$
Proof: We must show that for any real vector $\mathbf{x} \in \mathbb{R}^N$, the output $\mathbf{z} = U\mathbf{x}$ satisfies the symmetry condition for being in $\mathbb{H}$.
Let’s partition the real vector $\mathbf{x}$ into two halves, $\mathbf{x} = \begin{pmatrix} \mathbf{x}_1 \\ \mathbf{x}_2 \end{pmatrix}$. The resulting complex vector $\mathbf{z}$ is also partitioned as $\mathbf{z} = \begin{pmatrix} \mathbf{z}_1 \\ \mathbf{z}_2 \end{pmatrix}$. The symmetry condition in this block form is $\mathbf{z}_2 = J\bar{\mathbf{z}}_1$.
Compute z:
$$\mathbf{z} = U\mathbf{x} = \frac{1}{\sqrt{2}}\begin{pmatrix} I & iJ \\ J & -iI \end{pmatrix} \begin{pmatrix} \mathbf{x}_1 \\ \mathbf{x}_2 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} \mathbf{x}_1 + iJ\mathbf{x}_2 \\ J\mathbf{x}_1 - i\mathbf{x}_2 \end{pmatrix}$$
This gives us the two halves of our resulting complex vector:- $\mathbf{z}_1 = \frac{1}{\sqrt{2}}(\mathbf{x}_1 + iJ\mathbf{x}_2)$
- $\mathbf{z}_2 = \frac{1}{\sqrt{2}}(J\mathbf{x}_1 - i\mathbf{x}_2)$
Verify the Symmetry: Now, we compute $J\bar{\mathbf{z}}_1$ and check if it equals $\mathbf{z}_2$.
- First, take the complex conjugate of $\mathbf{z}_1$. Since $\mathbf{x}_1$, $\mathbf{x}_2$, and $J$ are all real, we just flip the sign on $i$:
$$\bar{\mathbf{z}}_1 = \frac{1}{\sqrt{2}}(\mathbf{x}_1 - iJ\mathbf{x}_2)$$ - Next, multiply by $J$ from the left:
$$J\bar{\mathbf{z}}_1 = J \left( \frac{1}{\sqrt{2}}(\mathbf{x}_1 - iJ\mathbf{x}_2) \right) = \frac{1}{\sqrt{2}}(J\mathbf{x}_1 - iJ^2\mathbf{x}_2)$$ - Since $J^2 = I$, this simplifies to:
$$J\bar{\mathbf{z}}_1 = \frac{1}{\sqrt{2}}(J\mathbf{x}_1 - i\mathbf{x}_2)$$
- First, take the complex conjugate of $\mathbf{z}_1$. Since $\mathbf{x}_1$, $\mathbf{x}_2$, and $J$ are all real, we just flip the sign on $i$:
Comparing our results, we see that $\mathbf{z}_2 = J\bar{\mathbf{z}}_1$, so the symmetry condition holds. Therefore, the matrix $U$ correctly maps any vector in $\mathbb{R}^N$ to a corresponding vector in $\mathbb{H}$, proving the isomorphism.
This isomorphism is the crucial first step in CKKS, allowing real-valued vectors (plaintext) to be encoded into the algebraic structure required for homomorphic encryption.