# Canonical mapping - CKKS encoding and decoding ## The canonical map A linear transformation that maps vectors of $n/2$ complex numbers into integer coefficients of polynomials degree $n$ s.t. arithmetic operation on them are equivalent to the same operation component wise on the vectors slots. half of the slots are conjugate to the other half. > Note: we do not use modulo-arithmetics on the plaintext part which is included in the ciphertext and we make sure all homomorphic operation will act on the plaintext in $\mathbb{Z}[X]/\langle X^n+1\rangle$ and not in $\mathbb{Z}_q[X]/\langle X^n+1\rangle$ by having coefficients which are much smaller than the modulo and so after modulo done for the cryptography stuff - they are not changed and the multiplication and addition results are as if done in $\mathbb{Z}[X]/\langle X^n+1\rangle$ ### why are we using the primitive roots of unity in DFT and not simple roots of unity? By the Chinese reminder theorem for quotient ring of polynomials we have : $ \begin{align} \mathbb{Z}[X]/\langle X^n+1\rangle \subset \mathbb{Q}[X]/\langle X^n+1\rangle &\cong\\ &\cong \mathbb{Q}[X]/(\prod^n (X-\zeta_i))\cong \prod^n \big( \mathbb{Q}[X]/(X-\zeta_i)\big) \\ & \cong \prod^n\mathbb{Q}(\zeta_i)\cong \prod^n\mathbb{C} \end{align}$ where the root of $X^n+1$ are the n-th roots of $-1$ which is the same to say that they are the [[primitive roots of unity|2n-th primitive roots]] of unity. because $\zeta^n=-1$ means that $\zeta^{2n}=1$ and smaller powers than $n$ can't be 1 otherwise we would not get -1 for power $n$. This means that those roots have order $2n$ and so are $2n$-th primitive roots. ## order of primitive roots of unity The 2n-th roots of unity construct the cyclic group $\mathbb{Z}_{2n}$ . It has a generator $\zeta:=e^\frac{2\pi i}{2n}$ of order $2n$. The other generators(the 2n-th primitive roots of unity) generates the subgroup $\mathbb{Z}^\times_{2n}$ . they can be constructed by odds power of $\zeta$. As $n$ a power of 2, we have $\mathbb{Z}_n^\times\cong C_2\times C_{n/2}$ see this [[Multiplicative group of integers modulo n|note]] i.e., $\mathbb{Z}_{2n}^\times$ is generated by the elements $(-1,5)$. Let $\zeta_j:=\zeta^{5^j}$, then the set $\{\zeta_j, \overline{\zeta_j}: 0\le j< N/2\}$ is the set of all primitive $2n$-th root of unity. Define $CRT_n:=\begin{bmatrix} 1 & \zeta_0 & \zeta_0^2 & \ldots & \zeta_0^{n-1} \\\vdots & \vdots& \vdots & & \vdots \\1& \zeta_{n-1} & \zeta_{n-1}^2 & \ldots & \zeta_{n-1}^{n-1}\end{bmatrix}$ - decoding $z:= (m(\zeta_j))_{j=0}^{n/2}$. the rest $n/2$ primitive roots decodes $\bar{z}$. Let $U=\begin{bmatrix} 1 & \zeta_0 & \zeta_0^2 & \ldots & \zeta_0^{n-1} \\ \vdots & \vdots& \vdots & & \vdots \\ 1& \zeta_{n/2-1} & \zeta_{n/2-1}^2 & \ldots & \zeta_{n/2-1}^{n-1} \end{bmatrix}$ $U$ has dimensions of $n\times \frac{n}{2}$ and satisfy, $z = U\cdot \textbf{m}$ were $\textbf{m} = (m_0,\ldots,m_{n-1})$ and $m_i$ is the i-th coefficient of $m(x)$. - $\text{CRT}_n$ is Vandermonde matrix of all 2n-primitive roots of unity, $\text{CRT}_n=\begin{bmatrix}& U &\\ \hdashline &\overline{U}& \end{bmatrix}$ and it is a square invertible matrix size $n\times n$. $\text{CRT}_n^{-1} = \frac{1}{n}\overline{\text{CRT}}_n^T=\frac{1}{n} \begin{bmatrix}\overline{U}^T & | & U^T\end{bmatrix}$ - We have $(z;\overline{z}) = \text{CRT}_n\cdot \textbf{m}$ - We have $\textbf{m}=\text{CRT}_n^{-1}(z;\overline{z})=\frac{1}{n}\overline{\text{CRT}}_n^T(z;\overline{z})=\frac{1}{n}(\overline{U}^T;U^T)(z;\overline{z})=\frac{1}{n}(\overline{U}^T\cdot z + U^T\cdot \overline{z})$ - note that the last equality is true because the transpose change the vertical "gluing" of 2 matrices to horizontal "gluing" and so it is equivalent for adding the 2 half of the vector which the matrix is multiply by. - The canonical map is used in CKKS encoding where complex vectors are mapped to vector of integer (coefficients of the plaintext polynomial). For decoding its inverse is used followed ny rounding (so real vectors are transformed to integer vectors) - There might be other ways to linearly 1-1 map complex vector to integer vector. - One advantage of the canonical map is that it preserves $L_\infty$ norm of input and output linear spaces i.e., $|a|_\infty \le |CRT_n^{-1} |_\infty\cdot |\sigma(a)|_\infty$. This is useful as it help to prove upper bounds on HE noise. - [[Canonical embedding computation with FFT decomposition]]. ## Why only half of the potential slots can be used? The primitive n-th root conjugate is also a primitive n-th root and so half of the primitive roots are conjugate of the others. ## Why the image of the canonical map has real and not complex coefficients? The complex slots are chosen so they are conjugate in pairs i.e., if $p(\zeta_i)=z_i$ then $p(\overline{\zeta_i})=\overline{z_i}$ and so $\overline{p(\zeta_i)}=\overline{z_i}=p(\overline{\zeta_i})$ . Then according to the following lemma $p(X)$ has real coefficients. Lemma: let $p(X)$ a polynomial of degree $n$ and there are $n$ different values $x_j$ s.t $\overline{p(x_j)}=p(\overline{x_j})$ then $p$ has real coefficients. Proof: Let $p(X)=\sum a_iX^i$ that satisfies $\overline{\sum a_ix_j^i}=\sum a_i\overline{x_j}^i$ for all $j$. We have $\overline{\sum a_ix_j^i}=\sum \overline{a_i}\cdot \overline{x_j}^i$ and therefore, $\sum (a_i-\overline{a}_i)\overline{x}_j^i=0$ or equivalently, $\begin{pmatrix} 1 & \overline{x}_1 &\ldots& \overline{x}_1^n \\ \vdots & &\ddots & \vdots \\ 1 & \overline{x}_n &\ldots& \overline{x}_n^n \\ \end{pmatrix} \begin{pmatrix} a_1-\overline{a}_1 \\ \vdots \\ a_n-\overline{a}_n \\ \end{pmatrix} = \begin{pmatrix} 0\\ \vdots \\ 0 \\ \end{pmatrix} $ The matrix is Vandermonde as $\overline{x}_j\ne\overline{x}_k$ and therefore is invertible. We get $a_i=\overline{a}_i$ as required. QED. ## A useful optimization for encoding and decoding When we choose the primitive roots to be $\zeta_j:=\zeta^{5^j}$ , then canonical map has a symmetric structure as: $CRT_n= \begin{bmatrix} \begin{array}{c:c:c} U_0 & U_1=U_0\cdot i \\ \hdashline \overline{U_0} & \overline{U_0}\cdot (-i) \end{array} \end{bmatrix} $ $ CRT_n^{-1} = \begin{bmatrix} \begin{array}{c:c:c} \overline{U_0^T} & U_0^T \\ \hdashline \overline{U_0^T}\cdot (-i) & U_0^T\cdot i \end{array} \end{bmatrix} $ where $U_0$ is the upper left quarter of $CRT_n$ with $\frac{n}{2}\times\frac{n}{2}$ dimension: $U_0=\begin{bmatrix} 1 & \zeta_0 & \zeta_0^2 & \ldots & \zeta_0^{\frac{n}{2}-1} \\ 1 & \zeta_1 & \zeta_1^2 & \cdots & \zeta_1^{\frac{n}{2}-1}\\ \vdots & \vdots& \vdots & & \vdots \\ 1& \zeta_{\frac{n}{2}-1} & \zeta_{\frac{n}{2}-1}^2 & \ldots & \zeta_{\frac{n}{2}-1}^{\frac{n}{2}-1} \end{bmatrix} $ Decoding the coefficients $(a_0,\ldots,a_{n-1})$ is computed by $ (x_0,\ldots,x_{\frac{n}{2}-1}) = CRT_n(a_0,\ldots,a_n) =U_0\cdot (a_0,\ldots,a_{\frac{n}{2}-1}) + U_1\cdot (a_\frac{n}{2},\ldots,a_{n-1})$ > Note there is no need to compute the multiplication of the lower half of $CRT_n$ with $(a_0,\ldots,a_{n-1})$ as the result is the conjugate of $(x_0,\ldots,x_{\frac{n}{2}-1})$. Encoding the slots i.e., $(a_0,\ldots,a_{n-1})=CRT_n^{-1}(x_0,\ldots,x_{\frac{n}{2}-1},\overline{x_0},\ldots,\overline{x}_{\frac{n}{2}-1})$ is computed by $ \begin{align} (a_0,\ldots,a_{\frac{n}{2}-1}) & = \frac{1}{n}\big(\overline{U^T_0}\cdot(x_0,\ldots,x_{\frac{n}{2}-1}) + U_0^T \cdot(\overline{x}_0,\ldots,\overline{x}_{\frac{n}{2}-1})\big) \\ & = \frac{1}{n}\big(\overline{U^T_0}\cdot(x_0,\ldots,x_{\frac{n}{2}-1}) + \overline{\overline{U_0^T} \cdot(x_0,\ldots,x_{\frac{n}{2}-1}})\big) \end{align} $ ``` Algoritm coef_left_0 = matrix_mul(U0_trans_conj, x[:n//2]) coef_left_1 = conj(coef_left_0) coef_left = coef_left_0 + coef_left_1 coef_right_0 = coef_left_0*(-i) coef_right_1 = conj(coef_right_0) coef_right = coef_right_0 + coef_right_1 output = (1/n)(scale*( a_tmp + conj(a_tmp) ) ) ``` > Note: This method reduce the number of matrix multiplication from 2 down to 1 (this is also true for coef-to-slot method) #### Further optimizations for homomorphic encoding (coef_to_slot) the following reduce 2 conjugations and one multiplication by `i` down to one conjugation and one multiplication by `i` $ \begin{align} coef\_left\_0 &=\overline{U_0^T}\cdot w \\ coef\_left\_1 &=\overline{\overline{U_0^T}\cdot w}=U_0^T\cdot\bar{w} \\ coef\_left &= \overline{U_0^T}\cdot w+U_0^T\cdot\bar{w} \overline{U_0^T}\cdot w + \overline{\overline{U_0^T\cdot\bar{w}}} =\\ &=\overline{U_0^T}\cdot w + \overline{\overline{U_0^T\cdot\bar{w}}} =\overline{U_0^T}\cdot w + \overline{\overline{U_0^T}\cdot w} = 2\cdot\text{Re}(\overline{U_0^T}\cdot w ) \\ \\ coef\_right\_0 &= -i\cdot \overline{U_0^T}\cdot w\\ coef\_right\_1 &= i\cdot U_0^T\cdot \bar{w} \\ coef\_right &= -i\cdot \overline{U_0^T}\cdot w + i\cdot U_0^T\cdot \bar{w} = -i\cdot \overline{U_0^T}\cdot w + \overline{\overline{i\cdot U_0^T\cdot \bar{w}}} \\ &= -i\cdot \overline{U_0^T}\cdot w + \overline{-i\cdot \overline{U_0^T}\cdot w} = 2\text{Re}(-i\cdot \overline{U_0^T}\cdot w )=2\cdot\text{Im}(\overline{U_0^T}\cdot w)\\ \end{align} $ ## DFT decomposition $U_0$ can be [[DFT decomposition|decomposed]] into $\log(n)$ matrices with 2-3 non-zero diagonals. ## References [[@Bootstrapping for Approximate Homomorphic Encryption]], section 4.1 [[@original ckks paper - Homomorphic Encryption for Arithmetic of Approximate Numbers]] ## Created 2022-02-13 11:23