ModDrop

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 \cdot S + B mod q_{l}$

$M + Δ E = A \cdot S + B - K \cdot q_{l}$ $▹$ where $K \cdot q_{l}$ represents a modulo reduction by $q_{l}$

BGV’s ModDrop operation decreases its modulus from $q_{l} \to q_{l - 1}$ is performed by updating the ciphertext $(A, B)$ to a new one: $(A^{'} = A mod q_{l - 1}$ , $B^{'} = B mod q_{l - 1})$ . After the ModDrop, the ciphertext’s modulus decreases from $q_{l} \to q_{l - 1}$ , yet its decryption relation still holds the same as follows:

$A^{'} \cdot S + B^{'} - K \cdot q_{l}$

$= (A mod q_{l - 1}) \cdot S + (B mod q_{l - 1}) - K \cdot q_{l}$

$= (A - K_{A} \cdot q_{l - 1}) \cdot S + (B - K_{B} \cdot q_{l - 1}) - K \cdot q_{l}$

$= A \cdot S + B - (K_{A} \cdot S + K_{B} + K \frac{q}{q_{l - 1}}) \cdot q_{l - 1}$ $▹$ where $\frac{q}{q_{l - 1}} = w_{l}$ (i.e., the $l$ -th prime element of $q_{L}$ )

$= A \cdot S + B - K^{'} \cdot q_{l - 1}$ $▹$ where $K^{'} = K_{A} \cdot S + K_{B} + K \frac{q}{q_{l - 1}}$ , $\frac{q}{q_{l - 1}} = w_{l}$

$= A \cdot S + B mod q_{l - 1}$

$= M + Δ E$ $▹$ since $M + Δ E < q_{0} < q_{l - 1}$

As shown above, $(A^{'}, B^{'}) mod q_{l - 1}$ 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.

BGV’s ModDrop is summarized as follows:

$⟨$ Summary D-4.6 $⟩$ BGV’s ModDrop

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

$(A^{'}, B^{'}) mod q_{l - 1} = (A mod q_{l - 1}, B mod q_{l - 1})$

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.

[prev][parent][next]