# CKKS Rescale - mod_down ## Motivation After multiplication we would like to reduce ciphertext noise and adjust the scale of the encrypted message. The idea is to divide the message and HE noise by scale. Required after HE multiplication (of two ciphertexts or ciphertext and plaintext). Multiplication of $m_1$ and $m_2$ the error increases by $\Delta\cdot m_1e_2+\Delta\cdot m_2e_1$. by rescaling we reduce this error to $m_1e_2+m_2e_1$. This error is small enough and is much smaller than the plaintext $\Delta m_1m_2$. Before rescale the plaintext is $\Delta^2m_1m_2$. `Rescale` is computed by dividing ciphertext polynomial's by the scheme scale $\Delta$ followed by rounding and dividing the modulo by $q_L$ where $|q_L|\approx\Delta$ and $Q=\prod_{i=0}^L q_i$ i.e., we want to divide by the top prime in the modulo-chain of $Q$. $\begin{align} ct &= (ct_0,ct_1)\bmod Q\\ ct_{rescaled}&= (\lceil ct_0/q \rfloor , \lceil ct_1/q\rfloor) \bmod Q/q \end{align}$ `mod_down` operation is extension of rescale to $P=\prod_{i=k}^L q_i$ i.e., there is no relation to the plaintext scale $\Delta$. The motivation is the same - to reduce plaintext noise in the ciphertext and it is used during [[CKKS Key switching|key switch]]. ## Why rescale's output encrypts $m/q$? It is not clear that dividing the polynomials of a ciphertext and modulo by $q$ will end up to be 1) a valid ciphertext 2) encrypting the plaintext $m/q$. Here is the proof. let $ct=(c_0,c_1)\bmod Q$ i.e., $c_0-c_1\cdot s\approx m+Q I$ . Dividing both sides of the equation by $q$ results in $\lceil c_0/q\rfloor - \lceil c_1/q\rfloor \cdot s\approx m/q+(Q/q)I$ which is equivalent to a ciphertext $c^\prime=\lceil(c_0/q,c_1/q)\rfloor \bmod Q/q$ that encrypts $m/q$. ## `mod_down` in RNS CKKS scheme [^2] Let's focus first on one integer coefficient $a\bmod Q$ , $Q=\prod_{i=0}^L q_i$ and $P=\prod_{i=k}^L q_i$ . we would like to compute `mod_down` of $a$ by $P$. Division by $P$ in RNS (which it's limbs are [[Finite fields]]) is different than division in the integer ring. But, if all limbs are divisible by $P$ without reminder - then $a=bP$ and its RNS limbs are $[a]_{q_i}=[b]_{q_i}[P]_{q_i}$. If we multiply each limb by $([P]_{q_i})^{-1}$ (the inverse is computed in the limb as finite-fields inverse) then we get $[a]_{q_i}([P]_{q_i})^{-1}=[b]_{q_i}$. This means we can RNS representation $[b]_{q_i}$ which is equivalent to the integer $b$. Therefore, this computation is equivalent to dividing $a$ by $P$ in integers. Now we see how to convert $a$ to be divisible by $P$ in RNS. note that the RNS limbs of $P$ represent the integer $a\bmod P$ i.e., the reminder of integer $a$ after dividing by $P$ as integers. If we subtract the reminder from $a$, we get an integer that is divisible by $P$ without reminder. This can be computed by first convert the integer $a\bmod P$ to RNS representation w.r.t $\{q_0,...,q_{k-1}\}$ and then subtract each RNS limb. This conversion is done in RNS representation using [[Fast Base Conversion - (Mod-up, BConv, FBC)|fast-base-conversion]] . To summarize `mod_down` steps 1. `fast_base_conversion` of $[a]_{q_k},...,[a]_{q_L}$ w.r.t $\{q_0,...,q_{k-1}\}$ . result is $[b]_{q_0},...,[b]_{q_{k-1}}$ 2. subtraction of $([a]_{q_0}- [b]_{q_0}),...,([a]_{q_{k-1}}-[b]_{q_{k-1}})$ 3. multiply the i-th limb by $\big([P]_{q_i}\big)^{-1}$ which can precomputed for speedup. Recall, the inverse is computed as finite-field inverse. Here is the algorithm from [^2] ![[Pasted image 20250930155650.png|396]] ![[Pasted image 20250605184024.png|398]] ## Rescale in original CKKS In the [[@original ckks paper - Homomorphic Encryption for Arithmetic of Approximate Numbers|original CKKS scheme]] , the modulo of the $\ell$ level $q_\ell:=p^\ell q_0$ where $p$ are integers and $0\le \ell \le L$ for some $L$. $\text{RS}_{\ell\to\ell^\prime}(ct):=\bigg\lfloor ct\frac{q_{\ell-1}}{q_\ell} \bigg\rceil \bmod p_{\ell-1}$ The rescaled ciphertext decrypts to the plaintext $m\frac{q_{\ell-1}}{q_\ell}$ plus some small noise where $\text{Decrypt}(ct)\approx m$ Correctness: let $ct=(c_0,c_1)\bmod q_\ell$ i.e., $c_0-c_1\cdot s\approx m+q_\ell I$ . Dividing both $c_0$ and $c_1$ by $q=q_\ell/q_{\ell-1}$ leads to the rescaled ciphertext $c^\prime=\lceil(c_0/q,c_/q)\rfloor \bmod q_\ell/q$ s.t., $c^\prime_0-c^\prime_1\cdot s\approx m/q + q\ell/q I$ . ## Rescaling ciphertext with more than 2 polynomials Similar to the correctness proof above: let $ct=(d_0,d_1,d_2)\bmod Q$ be a non-linear ciphertext that encrypts message $m$ i.e., $\langle ct, (1,-s,-s^2)\rangle = d_0-d_1s-d_2s^2= m +QI$. Dividing the right equation by $q$ and round, we get: $\lceil d_0/q \rfloor - \lceil d_1/q \rfloor\cdot s-\lceil d_2/q \rfloor\cdot s^2 = m/q+(Q/q)I$ i.e., $ct^\prime:=(\lceil d_0/q \rfloor , \lceil d_1/q \rfloor,\lceil d_2/q \rfloor)\bmod Q/q$ is a non-linear ciphertext that encrypts message $m/q$. Related: [[Rescale of integer]] ## Created 2024-05-01 11:15 [^1]: https://eprint.iacr.org/2019/688.pdf, page 4. [^2]: [RNS ckks paper](https://eprint.iacr.org/2018/931.pdf), page 9