I'm trying to understand CKKS (non bootstrappable) and I'm struggling with the encoding part.
I'm using the original paper , "Homomorphic Encryption for Arithmetic of Approximate Numbers
", also this notes "Lattices, Homomorphic Encryption, and CKKS"
and this blog.
I have four questions (will have sense after):
- If Im right of the projection.
- The final steps are trivials?
- Why when we round the coefficients we get the coefficients of the polynomial.
- Why they use a "special" algorithm for rounding that is random.
Context:
So, 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)$.
Basically $\sigma^{-1}:z\to\mathcal{R}$.
First they expand z mirroring it with the complex conjugates so $\pi^{-1}(z)\in\mathbb{H}\subset \mathbb{C}^{N}$. With $\mathbb{H}$ the set of all complex vector with this conjugate mirror property.
Because this $\pi^{-1}(z)$ may not live in the space of $\sigma(\mathcal{R})$, they discretize it by projecting this the base of $\sigma(\mathcal{R})$.
Up to here, all good.
For this they take the basis vectors $\alpha_i$, and project z to it.
First question, this is correct?:
\begin{equation}
z_{proj} = \sum_{i=0}^{N-1} \frac{<z,\alpha_i>}{<\alpha_i,\alpha_i>}\alpha_i
\end{equation}
Where <a,b> is the Hermitian inner product.
However they perform an rounding algorithm ("coordinate-wise random rounding") for each $\frac{<z,\alpha_i>}{<\alpha_i,\alpha_i>}$.
And finally, if we call $A$ to the matrix that has as columns the basis vectors $\alpha_i$, $\lfloor x \rceil$ as x rounded with the algorithm and consider the vector $z' = (\lfloor<z, \alpha_1>/<\alpha_1,\alpha_1>\rceil,..., \lfloor<z, \alpha_n>/<\alpha_n,\alpha_n>\rceil)$.
We can rewrite the projection as:
\begin{equation}
z_{roundProj} = Az'
\end{equation}
So if then we want to apply $\sigma^{-1}(z')$ (get the coefficients of the polynomial $\gamma_i$), is basically to solve the system of linear equations:
\begin{equation}
A\gamma=z_{roundProj} \rightarrow \gamma=A^{-1}z_{roundProj} = A^{-1}Az'=z' \rightarrow \gamma=z
\end{equation}
So, the steps that involves to multiply A with $z'$ to "complete" the projection to then solve the system of linear equations is not necessary. Second question, this is correct?
Third question, if this is correct, why when we round up each $\frac{<z,\alpha_i>}{<\alpha_i,\alpha_i>}$ we get each coefficient of the polynomial.
Fourth question why we need a special algorithm for rounding and not the usual ones (to the nearest integer) if in this stage there is not issue with security?