C-1.1 Discussion

Noise Elimination: If we decrypt 𝖦𝖫𝖢𝖀S,Οƒ(Ξ”(M⟨1⟩+ M⟨2⟩)) by using the secret key S, then we get the plaintext M⟨1⟩+ M⟨2⟩. Meanwhile, A1⟨3⟩,A2⟨3⟩,...Β Akβˆ’1⟨3⟩,E⟨3⟩ get eliminated by rounding after decryption, regardless of whatever their randomly sampled values were during encryption.

Noise Growth: Note that after decryption, the original ciphertext C’s noise has increased from E⟨1⟩ and E⟨2⟩ to E⟨3⟩ = E⟨2⟩+ E⟨2⟩. However, if the noise is sampled from a Gaussian distribution with the mean ΞΌ = 0, then the addition of multiple noises will converge to 0. Therefore, there is not much issue of noise growth in the homomorphic addition of two ciphertexts.

Hard Threshold on the Plaintext’s Value Without Modulo Reduction t: During homomorphic operations (e.g., addition or multiplication) and decryption, the 𝐴𝑆 and B terms in the B = 𝐴𝑆 + Ξ”M + E + π‘˜π‘ž relation are allowed to wrap around modulo q indefinitely, because regardless of whatever their wrapping count is, the final decryption step will always subtract B by 𝐴𝑆, outputting Ξ”M + E + kβ€²q = Ξ”M + E(π‘šπ‘œπ‘‘q), and the kβ€²q term is always exactly eliminated by modulo reduction by q. After that, we can correctly recover M by computing βŒˆΞ”M + E mod q Ξ” βŒ‹, eliminating the noise E. However, as we explained in SummaryΒ B-2.3.1 in Β§B-2.3.1), if the error bound π‘˜π‘‘ + e ⌊q t βŒ‹ < 1 2 breaks (where e can be any coefficient of E), then modulo reduction by q starts to contaminate the scaled plaintext bits. This violation of the error bound occurs when the noise e grows too much over homomorphic operations, or the ciphertext modulus q is not sufficiently larger than the plaintext modulus t. If q ≫t, the scheme can take on a big π‘˜π‘‘ value (i.e., the plaintext value can wrap around the plaintext modulus t many times across its homomorphic operations). The error bound constraint π‘˜π‘‘ + e ⌊q t βŒ‹ < 1 2 is used in the BFV scheme.