# CKKS multiplication Let $c_1=(b_1,a_1)$ and $c_2=(b_2,a_2)$ be 2 CKKS ciphertexts of plaintexts $m_1, m_2$. By homomorphic multiplication we mean a method that generated a ciphertext that encrypts $m_1m_2$ from the ciphertexts $c_1$ and $c_2$ i.e., using the elements $a_i$,$b_i$ and an encryption of the secret key (relinearization key). Note: we do not have the secret key $s$ for this computation - it is done in the server side. We have $b_1=a_1\cdot s+ m_1+e_1 \bmod Q$ and $b_2=a_2\cdot s + m_2 +e_2\bmod Q$. First, let's compute (1): $\begin{align} b_1\cdot b_2 &= (a_1\cdot s+ m_1+e_1)(a_2\cdot s+ m_2+e_2) \\ &= a_1\cdot a_2\cdot s^2 +a_1sm_2+a_1se_2+m_1a_2s+ m_1m_2+ m_1e_2\\ &\ \ + e_1a_2s+e_1 m_2+e_1e_2 \\ &= a_1 a_2s^2 + (a_1 m_2+a_2 m_1+a_1e_2+a_2e_1)s \\ &\ \ + m_1m_2+ m_1e_2+e_1 m_2+e_1e_2 \end{align}$ and (2): $\begin{align}a_1b_2+a_2b_1&=a_1\cdot a_2\cdot s + a_1\cdot m_2+ a_1\cdot e_2+a_2a_1s+a_2 m_1+a_2e_1 \\ &= 2a_1a_2s+a_1m_2+a_2 m_1+a_1e_2+a_2e_1 \end{align} $ replacing the middle term in (1) that is multiplied by $s$ with $s\cdot$(2) we get (3): $ b_1b_2=-a_1a_2s^2+(a_1b_2+a_2b_1)s+ m_1m_2+ m_1e_2+ m_2e_1+e_1e_2 \bmod Q $ Note that if we can get rid of the term $a_1a_2s^2$ from the right hand (1) and consider the term $(a_1b_2+a_2b_1)$ as a random element $a^\prime$ then we get a new ciphertext $(a^\prime s+ m_1m_2+e^\prime,a^\prime)$ where $e^\prime = m_1e_2+e_1m_2+e_1e_2$ which is a ciphertext that encrypts $m_1m_2$ w.r.t secret key $s$ as required. #### First try for removing the $s^2$ term Let's assume we have a ciphertext of the message $s^2$ w.r.t secret key $s$ i.e., $(b_3=a_3s+s^2+e_3,a_3)$. Then $(a_1a_2)b_3=a_1a_2a_3s+a_1a_2s^2+e_3a_1a_2\bmod (X^n+1, Q)$ and $b_1b_2+a_1a_2b_3=(a_1b_2+a_2b_1+a_1a_2a_3)s+m_1m_2+(e^\prime+a_1a_2e_3)$ . Concluding that $(b_1b_2+a_1a_2b_3, \ a_1b_2+a_2b_1 +a_1a_2a_3)$ is a ciphertext of $m_1m_2$ w.r.t secret key $s$ as required. BUT there are 2 problems: 1) $s$ is a polynomial of coefficients $\pm1,0$ and so adding the error term $e_3$ will corrupt it as it has coefficient larger than the message $s$. 2) The noise $e^\prime+a_1a_2e_3\bmod Q$ is too large for any message because $a_1,a_2$ are sampled from $Q$ and so this error has magnitude of $Q$. #### Fixing the two problems We will define instead a ciphertext of the message $Ps^2$ where $P$ is a prime of magnitude of $Q$ i.e., $(\hat{b}_4=\hat{a}_4s+Ps^2+\hat{e}_4,\hat{a}_4) \bmod PQ$. First, we need to extend the modulo $Q$ of the original ciphertext polynomials $a_1,a_2,b_1,b_2$ to polynomials $\widehat{a_1 a_2},\hat{b}_1,\hat{b}_2$ modulo $PQ$ such that if we reduce the modulo back to $Q$ we get the original polynomial: $\hat{a}_i \bmod Q=a_i$ and $\hat{b}_i \bmod Q=b_i$ for $i=1,2$ Next we compute $ P\hat{b}_1\hat{b}_2+\widehat{a_1a_2}\cdot \hat{b}_4 = \big(P(\hat{a}_1\hat{b}_2+\hat{a}_2\hat{b}_1)+\widehat{a_1a_2}\hat{a}_4\big)s+P\cdot m_1m_2+(Pe^\prime + \widehat{a_1a_2}\cdot \hat{e}_4) \bmod PQ$ Divide by $P$ , round and change modulo to $PQ/P=Q$: $b_1b_2+\lceil P^{-1}a_1a_2b_4 \rfloor=s(a_1b_2+a_2b_1+\lceil P^{-1}a_1a_2a_4\rfloor)+ m_1m_2 +e^\prime+\lceil P^{-1}a_1a_2e_4\rfloor\bmod Q$where $e^\prime = m_1e_2+e_1m_2+e_1e_2$ . Define the ciphertext $(b_1b_2+\lceil P^{-1}a_1a_2b_4\rfloor , a_1b_2+a_2b_1+\lceil P^{-1}a_1a_2a_4\rfloor) \bmod Q$which encrypts the message $m_1m_2$ w.r.t secret key $s$. In the [[@original ckks paper - Homomorphic Encryption for Arithmetic of Approximate Numbers|ckks original paper]] this is expressed as $ (b_1b_2, a_1b_2+a_2b_1) + \lceil P^{-1}a_1a_2(b4,a4)\rfloor = (d_0,d_1)+\lceil P^{-1}d_2\cdot evk \rfloor\bmod Q$ where $(d_0,d_1,d_2):=(b_1b_2,a_1b_2+a_2a_1,a_1a_2) \bmod Q$ and $evk:=(a_4s+Ps^2+e_4,a_4)\bmod PQ$. The error term $e^\prime$ can have the magnitude of $q$ , so we need to compute rescale operation to reduce it. note that the ciphertext result contains large error of $m_1e_2+m_2e_1$ which is handled by rescale operation. this is equivalent for dividing the plaintext (just the plaintext) by $q_i$ satisfying $|q_i|\approx|m_i|$ and $Q=\prod_i q_i$ related: [HE scalar multiplication](app://obsidian.md/HE%20scalar%20multiplication), [ciphertext & plaintext multiplication](app://obsidian.md/ciphertext%20&%20plaintext%20multiplication) Reference: [[@original ckks paper - Homomorphic Encryption for Arithmetic of Approximate Numbers]] ## Created 2023-01-04 17:48