D-2.4 Ciphertext-to-Ciphertext Addition

BFV’s ciphertext-to-ciphertext addition uses RLWE’s ciphertext-to-ciphertext addition scheme with the sign of the $A\cdot S$ term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative GLWE version’s (§B-4.4) ciphertext-to-ciphertext addition scheme with $k=1$.

D-2.4.1 Noise Bound Analysis

In the last part of Summary D-2.3 (in §D-2.3), we learned the noise bound conditions for BFV’s correct decryption. In this subsection, we will explain how this condition holds in more detail by walking through BFV’s ciphertext-to-ciphertext addition.

Let’s denote the homomorphically added ciphertext as follows:

$(A^{⟨3⟩},B^{⟨3⟩})=(A^{⟨1⟩}+A^{⟨2⟩},B^{⟨1⟩}+B^{⟨2⟩})modq$

Applying the first step of decryption to it yields the following intermediate result:

$B^{⟨3⟩}+A^{⟨3⟩}\cdot Smodq$

$B^{⟨1⟩}+B^{⟨2⟩}+A^{⟨1⟩}\cdot S+A^{⟨2⟩}\cdot Smodq$

$=(-A^{⟨1⟩}\cdot S+\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩})+(-A^{⟨2⟩}\cdot S+\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩})+A^{⟨1⟩}\cdot S+A^{⟨2⟩}\cdot Smodq$

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

The second step of decryption is to divide each coefficient of the above intermediate polynomial by $\mathrm{\Delta }$, round it, and reduce it modulo $t$ as follows:

$\lceil {\displaystyle \frac{\mathrm{\Delta }(M^{⟨1⟩}+M^{⟨2⟩})+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

Correct decryption requires the above result to match the value $M^{⟨1+2⟩}=M^{⟨1⟩}+M^{⟨2⟩}modt$, where $M^{⟨1+2⟩}$ is the modulo $t$-reduced final polynomial. Let’s define $𝜖={\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor ={\displaystyle \frac{q}{t}}-\mathrm{\Delta }$. Given $q\gg t$, $𝜖$ is a fractional value between $[0,1)$. Now, we can re-write the above decryption term as follows:

$\lceil {\displaystyle \frac{\mathrm{\Delta }(M^{⟨1⟩}+M^{⟨2⟩})+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$\lceil {\displaystyle \frac{(\frac{q}{t}-𝜖)\cdot (M^{⟨1⟩}+M^{⟨2⟩})+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$ $▹$ applying $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor ={\displaystyle \frac{q}{t}}-𝜖$

$=\lceil {\displaystyle \frac{(\frac{q}{t}-𝜖)\cdot (M^{⟨1+2⟩}+t\cdot K)+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$▹$where $t\cdot K$ represents the $t$-multiple overflows generated by the modulo addition of $M^{⟨1⟩}+M^{⟨2⟩}$

$=\lceil {\displaystyle \frac{\frac{q}{t}\cdot M^{⟨1+2⟩}-𝜖\cdot M^{⟨1+2⟩}+\frac{q}{t}\cdot t\cdot K-𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$=\lceil {\displaystyle \frac{\frac{q}{t}\cdot M^{⟨1+2⟩}-𝜖\cdot M^{⟨1+2⟩}-𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$▹$ since $\frac{q}{t}\cdot t=q$, and $q\cdot Kmodq=0$

$=\lceil {\displaystyle \frac{\lfloor \frac{q}{t}\rfloor \cdot M^{⟨1+2⟩}+𝜖\cdot M^{⟨1+2⟩}-𝜖\cdot M^{⟨1+2⟩}-𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$▹$ applying ${\displaystyle \frac{q}{t}}=\lfloor {\displaystyle \frac{q}{t}}\rfloor +𝜖$

$=\lceil {\displaystyle \frac{\lfloor \frac{q}{t}\rfloor \cdot M^{⟨1+2⟩}-𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}modq}{\mathrm{\Delta }}}\rfloor modt$

$=\lceil {\displaystyle \frac{\lfloor \frac{q}{t}\rfloor \cdot M^{⟨1+2⟩}-𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}}{\mathrm{\Delta }}}\rfloor modt$

$▹$applying the special assumption $|𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}|<{\displaystyle \frac{\mathrm{\Delta }}{2}}$ to all $n$ coefficients (see §B-2.3.1)

$=M^{⟨1+2⟩}+\lceil {\displaystyle \frac{E^{⟨1⟩}+E^{⟨2⟩}-𝜖\cdot t\cdot K}{\mathrm{\Delta }}}\rfloor modt$ $▹$ since $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$, and $\lceil M^{⟨1+2⟩}\rfloor =M^{⟨1+2⟩}$

$=M^{⟨1+2⟩}modt$ $▹$ applying the special assumption $𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}<{\displaystyle \frac{\mathrm{\Delta }}{2}}$ to all $n$ coefficients

The above final expression implies that correct decryption (i.e., $M^{⟨1+2⟩}$) is preserved if the special assumption $𝜖\cdot t\cdot K+E^{⟨1⟩}+E^{⟨2⟩}<{\displaystyle \frac{\mathrm{\Delta }}{2}}$ holds (for all $n$ coefficients of the polynomial). At a high level, the greater the ciphertext modulus $q$ becomes compared to the plaintext modulus $t$, the greater the scaling factor $\mathrm{\Delta }$ becomes, which can sustain a greater noise budget ($E^{⟨1⟩}+E^{⟨2⟩}$) and greater wrapping around $t$-multiple overflows of the plaintext ($𝜖\cdot t\cdot K$).

This noise bound principle not only applies to homomorphic addition but also to homomorphic multiplication and rotation, which will be explained in later subsections. The term $E^{⟨1⟩}+E^{⟨2⟩}$ can be generalized as the cumulative noise across all homomorphic operations (e.g., additions, multiplications, rotations), and the term $𝜖\cdot t\cdot K$ can be generalized as the amount of $t$-multiple overflows of each coefficient of the plaintext polynomial computed across homomorphic operations.