Does the relationship between plaintext and ciphertext moduli affect the security of BGV/BV SwHE?

Question

The SwHE schemes due to Brakerski and Vaikuntanathan (BV) and Brakerski-Gentry-Vaikuntanathan (BGV) have common concept in which the message bit is put in the least significant bit of the ciphertext. Let $t, q\in \mathbb{Z}$ be moduli that determine the plaintext and ciphertext space, respectively. The BV and BGV scheme require $t$ and $q$ to be co-prime.

Let

• $\mathbf{s} \in \mathbb{Z}_q^n $: a secret key sampled from a key distribution

• $\mathbf{e} \in \mathbb{Z}_q $: an error sampled from an error distribution

• $\mathbf{a} \in \mathbb{Z}_q^n $: a random vector sampled from $\mathbb{Z}_q^n$ uniformly at random.

• $m \in \mathbb{Z}_t $: a message.

Then, $$ (\mathbf{a}, b):=(\mathbf{a}, \langle \mathbf{a},\mathbf{s} \rangle + t\cdot e + m) \in \mathbb{Z}^n \times \mathbb{Z} $$ is a symmetric encryption of $m$. Decryption works by computing $((b - \langle \mathbf{a}, \mathbf{s} \rangle) \mod q )\mod t$.

Is this plaintext and ciphertext space relationship ($t$ and $q$ are co-prime) needed for the security? What happens if $q$ is divisible by $t$? I understand that modulus switching does not work, so it affects the correctness at least. What about the security?

Answer 1

This is necessary for security. Consider if $q$ was a multiple of $t$, so $q = v\cdot t$. Take your ciphertext $(a, \langle a, s \rangle + t\cdot e + m)$ and multiply through by $v$. You now have $$(v\cdot a, \langle v\cdot a, s \rangle + v\cdot t\cdot e + v \cdot m) = (v\cdot a, \ \langle v \cdot a, s \rangle + v\cdot m) \mod q$$ Suppose you're playing the CPA game, so there are only two possible values for $m$, which you know, so just try subtracting $v\cdot m$ from the second element and solve the "learning without errors" problem using your favorite algorithm to solve a linear system of equations (Gaussian elimination will work for BV & BGV).

For a more general answer, if $t$ is a zero-divisor in the ring $\mathbb{Z}_q$, the above attack will work, since you can kill the error by multiplying through by a non-zero value. By mandating that $t$ and $q$ be coprime, the only way to kill the error is to multiply by a multiple of $q$, which is 0 in the ring $\mathbb{Z}_q$.