D-4.6 ModDrop

BGV’s ModDrop works similarly to that of CKKS’s ModDrop (Summary D-3.7 in §D-3.7). Remember that CKKS’s ciphertext decryption relation is as follows:

M + ΔE = A S + B mod ql

M + ΔE = A S + B K ql # where K ql represents a modulo reduction by ql

BGV’s ModDrop operation decreases its modulus from ql ql1 is performed by updating the ciphertext (A,B) to a new one: (A = A mod ql1, B = B mod ql1). After the ModDrop, the ciphertext’s modulus decreases from ql ql1, yet its decryption relation still holds the same as follows:

AS + BK ql

= (A mod ql1) S + (B mod ql1) K ql

= (A KA ql1) S + (B KB ql1) K ql

= A S + B (KA + KB + K q ql1) ql1 # where q ql1 is an integer (the l-th prime element of qL)

= A S + B Kql1 # where K = KA + KB + K q ql1 is an integer

= A S + B mod ql1

= M + ΔE # since ΔM + E < q0 < ql1

As shown above, (A,B) mod ql1 decrypts to the same M + ΔE, a plaintext with a scaled error. However, the noise budget (i.e., allowed threshold of the noise) decreases because the ciphertext modulus-to-noise ratio decreases.

CKKS’s ModDrop is summarized as follows:

Summary D-4.5 BGV’s ModDrop

Given a BGV ciphertext with the l-th multiplicative level 𝖱𝖫𝖶𝖤S,σ(ΔM) = (A,B) mod ql, a ModDrop operation is as follows:

(A,B) mod ql1 = (A mod ql1,B mod ql1)

After this, the ciphertext’s multiplicative level decreases by 1, the noise’s scaling factor Δ and the plaintext are unaffected, and the noise budget (i.e., allowed noise threshold) decreases.