D-2.7 Ciphertext-to-Ciphertext Multiplication

- Reference 1: Introduction to the BFV encryption scheme [12]

- Reference 2: Somewhat Partially Fully Homomorphic Encryption [13]

Given two ciphertexts ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨1⟩})$ and ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨2⟩})$, the goal of ciphertext-to-ciphertext multiplication is to derive a new ciphertext whose decryption is $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$. Ciphertext-to-ciphertext multiplication is more complex than ciphertext-to-plaintext multiplication. It comprises four steps: (1) ModRaise; (2) polynomial multiplication; (3) relinearization; and (4) rescaling.

For better understanding, we will explain BFV’s ciphertext-to-ciphertext multiplication based on the alternate version of RLWE (Theorem B-4.4 in §B-4.4), where the sign of the $\mathit{𝐴𝑆}$ term is flipped in the encryption and decryption formulas.

D-2.7.1 ModRaise

We learned from Summary D-2.3 (in §D-2.3) that a BFV ciphertext whose ciphertext modulus is $q$ has the (decryption) relation: $\mathrm{\Delta }M+E=A\cdot S+B-K\cdot q$, where $K\cdot q$ stands for modulo reduction by $q$. ModRaise is a process of forcibly modifying the modulus of a ciphertext from $q\to Q$, where $q\ll Q$. Suppose we modify the modulus of ciphertext $(A,B)$ from $q$ to $Q$, where $Q=q\cdot \mathrm{\Delta }$ (remember $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$). Then, the decryption of the mod-raised ciphertext will output $A\cdot S+BmodQ$. However, since each polynomial coefficient of $A$ and $B$ is less than $q$ and each polynomial coefficient of $S$ is either $\{-1,0,1\}$, the resulting polynomial of $A\cdot S+B$ is guaranteed to have each coefficient strictly less than $Q$ even without modulo reduction by $Q$– this is because $(q-1)\cdot n+(q-1)<Q$, where $(q-1)\cdot n$ is the maximum possible coefficient of $A\cdot S$ and $(q-1)$ is the maximum possible coefficient of $B$. And as mentioned before, we know the relation: $A\cdot S+B=\mathrm{\Delta }M+E+\mathit{𝐾𝑞}$. Therefore, the decryption of the mod-raised ciphertext $(A,B)modQ$ is as follows:

$\mathrm{\Delta }M+E+\mathit{𝐾𝑞}modQ=\mathrm{\Delta }M+E+\mathit{𝐾𝑞}$ # since $\mathrm{\Delta }M+E+\mathit{𝐾𝑞}<Q$

The first step of BFV’s ciphertext-to-ciphertext multiplication is to mod-raise the two input ciphertexts $(A^{⟨1⟩},B^{⟨1⟩})modq$ and $(A^{⟨2⟩},B^{⟨2⟩})modq$ from $q\to Q$ (where $Q=q\cdot \mathrm{\Delta }$) as follows:

$(A^{⟨1⟩},B^{⟨1⟩})modQ$

$(A^{⟨2⟩},B^{⟨2⟩})modQ$

After ModRaise, the decryption of these two ciphertexts would be the following:

$A^{⟨1⟩}\cdot S+B^{⟨1⟩}=\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q<Q$

$A^{⟨2⟩}\cdot S+B^{⟨2⟩}=\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q<Q$

Therefore, the mod-raised ciphertexts have the following form:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨1⟩}+K_{1}q)=(A^{⟨1⟩},B^{⟨1⟩})modQ$

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨2⟩}+K_{2}q)=(A^{⟨2⟩},B^{⟨2⟩})modQ$

D-2.7.2 Polynomial Multiplication

Our next goal is to derive a new ciphertext which encrypts $(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)$.

First, we can derive the following relation:

$(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)$

$=(A^{⟨1⟩}\cdot S+B^{⟨1⟩})\cdot (A^{⟨2⟩}\cdot S+B^{⟨2⟩})$

$=\underset{D_0}{\underbrace{B^{⟨1⟩}{B}^{⟨2⟩}}}+\underset{D_1}{\underbrace{(B^{⟨2⟩}{A}^{⟨1⟩}+B^{⟨1⟩}{A}^{⟨2⟩})}}\cdot S+\underset{D_2}{\underbrace{(A^{⟨1⟩}\cdot A^{⟨2⟩})}}\cdot S\cdot S$

$=D_0+D_1\cdot S+D_2\cdot S^2$

Meanwhile, we also have the following relations:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨1⟩}+K_{1}q)=\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q$

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨2⟩}+K_{2}q)=\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q$

Combining all these, we reach the following relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨1⟩}+K_{1}q)\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨2⟩}+K_{2}q)=D_0+D_1\cdot S+D_2\cdot S^2$

Notice that $D_0,D_1,$ and $D_2$ are known values as ciphertext components, whereas $S$ is only known to the private key owner. Therefore, we can view $D_0+D_1\cdot S+D_2\cdot S^2$ as a decryption formula such that given the ciphertext components $D_0,D_1,D_2$ and the private key $S$, one can derive $(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)$. In other words, we can let $(D_0,D_1,D_2)$ be a new form of ciphertext which can be decrypted by $S$ into $(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)$.

However, $(D_0,D_1,D_2)$ is not in the RLWE ciphertext format, because it has 3 components instead of 2. Having 3 ciphertext components is computationally inefficient, as its decryption involves a square root of $S$ (i.e., $S^2$). Over consequent ciphertext-to-ciphertext multiplications, this $S$ term will double its exponents as $S^4,S^8,\cdots$ as well as the number of ciphertext components, which would exponentially increase the computational overhead of decryption. Therefore, we want to convert the intermediate ciphertext format $(D_0,D_1,D_2)$ into a regular BFV ciphertext format that has two polynomials as ciphertext components. This conversion process is called a relinearization process (which will be explained in the next subsection).

D-2.7.3 Relinearization

Relinearization is a process of converting the polynomial triplet $(D_0,D_1,D_2)\in R_{⟨n,Q⟩}^3$ into two RLWE ciphertexts ${\mathsf{\text{𝖼𝗍}}}_{\alpha }$ and ${\mathsf{\text{𝖼𝗍}}}_{\beta }$ which hold the relation: $D_0+D_{1}S+D_2{S}^2={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\alpha }+{\mathsf{\text{𝖼𝗍}}}_{\beta })$.

In the formula $D_0+D_{1}S+D_2{S}^2$, we can re-write $D_0+D_{1}S$ as a synthetic RLWE ciphertext ${\mathsf{\text{𝖼𝗍}}}_{\alpha }=(D_1,D_0)$, which can be decrypted by $S$ into $D_{1}S+D_0$. Similarly, our next task is to derive a synthetic RLWE ciphertext ${\mathsf{\text{𝖼𝗍}}}_{\beta }$ whose decryption is $D_2\cdot S^2$ (i.e., ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\beta })=D_2\cdot S^2$).

A naive way of creating a ciphertext that encrypts $D_2\cdot S^2$ is as follows: we encrypt $S^2$ into an RLWE ciphertext as ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2)=(A^{⟨s⟩},B^{⟨s⟩})$ such that $A^{⟨s⟩}\cdot S+B^{⟨s⟩}=S^2+E^{⟨s⟩}modQ$ (where the ciphertext modulus is $Q$ and the plaintext scaling factor $\mathrm{\Delta }=1$). Then, we perform a ciphertext-to-plaintext multiplication (§C-3) with $D_2$, treating $D_2$ as a plaintext polynomial in modulo $Q$. However, this approach does not work in practice, because computing $D_2\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2)$ generates a huge noise as follows:

$D_2\cdot (A^{⟨s⟩},B^{⟨s⟩})=(D_2\cdot A^{⟨s⟩},D_2\cdot B^{⟨s⟩})$

, whose decryption is:

$D_2\cdot A^{⟨s⟩}\cdot S+D_2\cdot B^{⟨s⟩}=D_2\cdot S^2+D_2\cdot E^{⟨s⟩}(\mathit{𝑚𝑜𝑑}Q)$

. In the above decrypted expression $D_2{S}^2+D_2{E}^{⟨s⟩}modQ$, the term $D_2{S}^2$ is okay to be reduced modulo $Q$, because this term is originally allowed to be reduced modulo $Q$ in the final decryption formula $D_0+D_{1}S+D_2{S}^{2}modQ$ as well. However, the problematic term is the noise $D_2\cdot E^{⟨s⟩}$, because its coefficients can be any value in $[0,Q-1]$ (since each coefficient of polynomial $D_2=A^{⟨1⟩}{A}^{⟨2⟩}$ can be any value in $[0,Q-1]$). Such a huge noise is not allowed for correct final decryption.

To avoid this noise issue, an improved solution is to express the RLWE ciphertext that encrypts $D_2{S}^2$ as additions of multiple RLWE ciphertexts with small noises by using the gadget decomposition technique (§A-6.4). For this, we use an RLev ciphertext (§B-5) that encrypts $S^2$. Suppose our gadget vector is $\overrightarrow{g}=({\displaystyle \frac{Q}{\beta }},{\displaystyle \frac{Q}{{\beta }^2}},{\displaystyle \frac{Q}{{\beta }^3}},\cdots ,{\displaystyle \frac{Q}{{\beta }^l}})$. Remember that our goal is to find ${\mathsf{\text{𝖼𝗍}}}_{\beta }={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2\cdot D_2)$ given known $D_2$, unknown $S$, and known ${\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)={\left\{{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{Q}{{\beta }^i}}\cdot S\right)\right\}}_{i=1}^l$. Then, we can derive ${\mathsf{\text{𝖼𝗍}}}_{\beta }$ as follows:

${\mathsf{\text{𝖼𝗍}}}_{\beta }={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2\cdot D_2)$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot \left(D_{2,1}{\displaystyle \frac{Q}{\beta }}+D_{2,2}{\displaystyle \frac{Q}{{\beta }^2}}+\cdots D_{2,l}{\displaystyle \frac{Q}{{\beta }^l}}\right)\right)$ # by decomposing $D_2$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot D_{2,1}\cdot {\displaystyle \frac{Q}{\beta }}\right)+{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot D_{2,2}\cdot {\displaystyle \frac{Q}{{\beta }^2}}\right)+\cdots +{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot D_{2,l}\cdot {\displaystyle \frac{Q}{{\beta }^l}}\right)$

$=D_{2,1}\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{Q}{\beta }}\right)+D_{2,2}\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{Q}{{\beta }^2}}\right)+\cdots +D_{2,l}\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{Q}{{\beta }^l}}\right)$ # where each RLWE ciphertext is an encryption of $S^2{\displaystyle \frac{Q}{\beta }},S^2{\displaystyle \frac{Q}{{\beta }^2}},\cdots ,S^2{\displaystyle \frac{Q}{{\beta }^l}}$ as plaintext with the plaintext scaling factor $\mathrm{\Delta }=1$

$=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩$ # inner product of Decomp and RLev treating them as vectors

If we decrypt the above, we get the following:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\beta }=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩)$ # the scaling factors of ${\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)$ are all 1

$=D_{2,1}\cdot \left(E_1^{\prime }+S^2{\displaystyle \frac{Q}{\beta }}\right)+D_{2,2}\cdot \left(E_2^{\prime }+S^2{\displaystyle \frac{Q}{{\beta }^2}}\right)+\cdots +D_{2,l}\cdot \left(E_l^{\prime }+S^2{\displaystyle \frac{Q}{{\beta }^l}}\right)$ # where each $E_i^{\prime }$ is a noise embedded in ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{Q}{{\beta }^i}}\right)$

$=\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})+S^2\cdot \left(D_{2,1}{\displaystyle \frac{Q}{\beta }}+D_{2,2}{\displaystyle \frac{Q}{{\beta }^2}}+\cdots +D_{2,l}{\displaystyle \frac{Q}{{\beta }^l}}\right)$

$=\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{𝜖}_i+D_2\cdot S^2$ # where each ${𝜖}_i=E_i^{\prime }\cdot D_{2,i}$

$\approx D_2\cdot S^2$ # $\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{𝜖}_i\ll D_2\cdot E^{″}$, where $E^{″}$ is the noise that could’ve been embedded in ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2)$

Therefore, we get the following comprehensive relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨1⟩}+K_{1}q)\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(\mathrm{\Delta }{M}^{⟨2⟩}+K_{2}q)modQ$

$=(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)modQ$

$=(A^{⟨1⟩}\cdot S+B^{⟨1⟩})\cdot (A^{⟨2⟩}\cdot S+B^{⟨2⟩})modQ$

$=D_0+D_1\cdot S+D_2\cdot S^{2}modQ$ # $D_0=B^{⟨1⟩}{B}^{⟨2⟩}$, $D_1=A^{⟨1⟩}{B}^{⟨2⟩}+A^{⟨2⟩}{B}^{⟨1⟩}$, $D_2=A^{⟨1⟩}{A}^{⟨2⟩}$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\alpha })+{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\beta })-\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ$

# ${\mathsf{\text{𝖼𝗍}}}_{\alpha }=(D_1,D_0)=(A_{\alpha },B_{\beta })$, ${\mathsf{\text{𝖼𝗍}}}_{\beta }=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩=(A_{\beta },B_{\beta })$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖼𝗍}}}_{\alpha }+{\mathsf{\text{𝖼𝗍}}}_{\beta })-\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}((A_{\alpha +\beta },B_{\alpha +\beta }))-\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ$ # $A_{\alpha +\beta }=A_{\alpha }+A_{\beta }$, $B_{\alpha +\beta }=B_{\alpha }+B_{\beta }$

From the above, we extract the following relation:

$(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+K_{1}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+K_{2}q)modQ$

$={\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}+\mathrm{\Delta }\cdot (M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (\mathrm{\Delta }{M}^{⟨1⟩}{K}_2+\mathrm{\Delta }{M}^{⟨2⟩}{K}_1+E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}modQ$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}((A_{\alpha +\beta },B_{\alpha +\beta }))-\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ$

We can re-write the above relation as follows:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}((A_{\alpha +\beta },B_{\alpha +\beta }))=A_{\alpha +\beta }\cdot S+B_{\alpha +\beta }modQ$

$={\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}+\mathrm{\Delta }\cdot (M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (\mathrm{\Delta }{M}^{⟨1⟩}{K}_2+\mathrm{\Delta }{M}^{⟨2⟩}{K}_1+E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ$

To verbally interpret the above relation, decrypting the synthetically generated ciphertext $(A_{\alpha +\beta },B_{\alpha +\beta })$ and applying a reduction modulo $Q$ to it gives us ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$ with a lot of noise terms. Meanwhile, as explained in the beginning of this subsection, our goal is to derive a ciphertext whose decryption is $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$, also ensuring that the decrypted ciphertext’s noise is small enough to be fully eliminated by scaling down the plaintext by $\mathrm{\Delta }$ at the end. This goal is accomplished by the final rescaling step to be explained in the next subsection.

D-2.7.4 Rescaling

The rescaling step is equivalent to converting the ciphertext $(A_{\alpha +\beta },B_{\alpha +\beta })modQ$ into $\left(\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor ,\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \right)modq$, where $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor \approx {\displaystyle \frac{q}{t}}$. The decryption of this rescaled ciphertext (and finally scaling down by $\mathrm{\Delta }$) is $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$. This is demonstrated below:

$\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \cdot S+\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor modq$ # decryption of ciphertext $\left(\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor ,\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \right)modq$

$=\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \cdot S+\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor +K_{3}q$ # where $K_{3}q$ stands for modulo reduction by $q$

$=\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \cdot S+\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor +{\displaystyle \frac{K_{3}Q}{\mathrm{\Delta }}}$ # since $Q=\mathrm{\Delta }\cdot q$

$=\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot (A_{\alpha +\beta }\cdot S+B_{\alpha +\beta }+K_{3}Q)\rfloor +E_r$ # $E_r$ is a rounding error

$=\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot (A_{\alpha +\beta }\cdot S+B_{\alpha +\beta }modQ)\rfloor +E_r$

$=\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot ({\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}+\mathrm{\Delta }\cdot (M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+$

$q\cdot (\mathrm{\Delta }{M}^{⟨1⟩}{K}_2+\mathrm{\Delta }{M}^{⟨2⟩}{K}_1+E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})modQ)\rfloor +E_r$

# as we derived at the end of §D-2.7.3

$=\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot ({\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}+\mathrm{\Delta }\cdot (M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+$

$q\cdot (\mathrm{\Delta }{M}^{⟨1⟩}{K}_2+\mathrm{\Delta }{M}^{⟨2⟩}{K}_1+E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})+K_{4}Q)\rfloor +E_r$

# where $K_{4}Q$ stands for modulo reduction by $Q$

$=\lceil \mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+(M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (M^{⟨1⟩}{K}_2+M^{⟨2⟩}{K}_1)$

$+{\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot q\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+{\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot (K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i}))+K_{5}q\rfloor$

# where $K_{5}q=K_{4}q+M^{⟨1⟩}q{K}_2+M^{⟨2⟩}{K}_{1}q$

$=\lceil \mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+(M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (M^{⟨1⟩}{K}_2+M^{⟨2⟩}{K}_1)+(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)$

$+{\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot (K_1{K}_2{q}^2+E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i}))+K_{5}q\rfloor$

# where $𝜖={\displaystyle \frac{q}{\mathrm{\Delta }}}-{\displaystyle \frac{q}{{\displaystyle \frac{q}{t}}}}={\displaystyle \frac{q}{\lfloor {\displaystyle \frac{q}{t}}\rfloor }}-{\displaystyle \frac{q}{{\displaystyle \frac{q}{t}}}}\approx 0$, thus we substituted ${\displaystyle \frac{q}{\mathrm{\Delta }}}=𝜖+t$

$=\lceil \mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+(M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (M^{⟨1⟩}{K}_2+M^{⟨2⟩}{K}_1)+(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)$

$+{\displaystyle \frac{K_1{K}_2{q}^2}{\mathrm{\Delta }}}+{\displaystyle \frac{E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})}{\mathrm{\Delta }}}+K_{5}q\rfloor$

# Now, let ${𝜖}^{\prime }={\displaystyle \frac{K_1{K}_2{q}^2}{\mathrm{\Delta }}}-{\displaystyle \frac{K_1{K}_2{q}^2}{{\displaystyle \frac{q}{t}}}}={\displaystyle \frac{K_1{K}_2{q}^2}{\lfloor {\displaystyle \frac{q}{t}}\rfloor }}-{\displaystyle \frac{K_1{K}_2{q}^2}{{\displaystyle \frac{q}{t}}}}\approx 0$.

Thus, we will substitute ${\displaystyle \frac{K_1{K}_2{q}^2}{\mathrm{\Delta }}}={\displaystyle \frac{K_1{K}_2{q}^2}{{\displaystyle \frac{q}{t}}}}+{𝜖}^{\prime }=K_1{K}_2\mathit{𝑞𝑡}+{𝜖}^{\prime }$

$=\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+(M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩})+q\cdot (M^{⟨1⟩}{K}_2+M^{⟨2⟩}{K}_1)$

$+(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+K_1{K}_2\mathit{𝑞𝑡}+{𝜖}^{\prime }+K_{5}q+\lceil {\displaystyle \frac{E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})}{\mathrm{\Delta }}}\rfloor$

$=\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+{𝜖}^{″}+K_{6}q$

# where $K_{6}q=K_{5}q+q\cdot (M^{⟨1⟩}{K}_2+M^{⟨2⟩}{K}_1)+K_1{K}_2\mathit{𝑞𝑡},$

${𝜖}^{″}=M^{⟨1⟩}{E}^{⟨2⟩}+M^{⟨2⟩}{E}^{⟨1⟩}+(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)+\lceil {\displaystyle \frac{E^{⟨1⟩}{E}^{⟨2⟩}+\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})}{\mathrm{\Delta }}}\rfloor$

$=\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+{𝜖}^{″}modq$

In conclusion, the ciphertext $\left(\lceil {\displaystyle \frac{A_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor ,\lceil {\displaystyle \frac{B_{\alpha +\beta }}{\mathrm{\Delta }}}\rfloor \right)modq$ successfully decrypts to $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$ if ${𝜖}^{″}<{\displaystyle \frac{\mathrm{\Delta }}{2}}\approx {\displaystyle \frac{q}{2t}}$.

Noise Analysis: Among the terms of ${𝜖}^{″}$, let’s analyze the noise growth of the $(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)$ term after ciphertext-to-ciphertext multiplication. Each coefficient of $K_1$ is at most $n$, because $A^{⟨1⟩}\cdot S+B^{⟨1⟩}=\mathrm{\Delta }M+E^{⟨1⟩}+K_{1}q$, where the maximum possible coefficient value of $A^{⟨1⟩}\cdot S+B^{⟨1⟩}$ is $q\cdot n$. And the same is true for the coefficients of $K_2$. Therefore, after scaling down $(t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)$ by $\mathrm{\Delta }$ upon the final decryption stage, this term’s down-scaled noise gets bound by:

${\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot (t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)\approx {\displaystyle \frac{t}{q}}\cdot (t+𝜖)\cdot (E^{⟨1⟩}{K}_2+E^{⟨2⟩}{K}_1)<{\displaystyle \frac{\mathit{𝑛𝑡}\cdot (t+𝜖)}{q}}\cdot (E^{⟨1⟩}+E^{⟨2⟩})$

This implies that for correct decryption, ${\displaystyle \frac{\mathit{𝑛𝑡}\cdot (t+𝜖)}{q}}\cdot (E^{⟨1⟩}+E^{⟨2⟩})$ has to be smaller than $0.5$. In other words, $E^{⟨1⟩}+E^{⟨2⟩}$ has to be smaller than ${\displaystyle \frac{q}{2\mathit{𝑛𝑡}\cdot (t+𝜖)}}$. We can do noise analysis for all other terms for ${𝜖}^{″}$ in a similar manner. Importantly, upon decryption, the aggregation of all these noise terms’ down-scaled values has to be smaller than $0.5$ for correct decryption.

Modulus Switch v.s. Rescaling: Notice in the rescaling process, multiplying ${\displaystyle \frac{1}{\mathrm{\Delta }}}$ to $A_{\alpha +\beta }$ and $B_{\alpha +\beta }$ results in two effects: (1) converts ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$ into $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$; (2) switches the modulus of the mod-raised ciphertexts from $Q\to q$. In fact, modulus switch and rescaling are closely equivalent to each other. Modulus switch is a process of changing a ciphertext’s modulus (e.g., $q\to q^{\prime }$), while preserving the property that the decryption of both ciphertexts results in the same plaintext. On the other hand, rescaling refers to the process of changing the scaling factor of a plaintext within a ciphertext (e.g., $\mathrm{\Delta }\to {\mathrm{\Delta }}^{\prime }$). Modulus switch inevitably changes the scaling factor of the plaintext within the target ciphertext, and rescaling also inevitably changes the modulus of the ciphertext that contains the plaintext (as shown in §D-2.7.4). Therefore, these two terms can be used interchangeably.

D-2.7.5 Summary

To put all things together, BFV’s ciphertext-to-ciphertext multiplication is summarized as follows:

The Purpose of ModRaise: When we multiply polynomials at the second step of ciphertext-to-ciphertext multiplication (§D-2.7.2), the underlying plaintext within the ciphertext temporarily grows to ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$, which exceeds the allowed maximum boundary $q$ for the plaintext (Summary D-2.3 in §D-2.3). After this point, applying modulo-$q$ reduction to the intermediate result will irrevocably corrupt the plaintext. To avoid the corruption of the plaintext when it grows to ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$, we temporarily increase the ciphertext modulus from $q\to Q$, which is sufficiently large to hold ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$ without wrapping around the boundary of the ciphertext modulus.

Swapping the Order of Relinearization and Rescaling: The order of relinearization and rescaling is interchangeable. Running rescaling before relinearization reduces the size of the ciphertext modulus, and therefore the subsequent relinearization can be executed faster.