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

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?

## 1 Answer

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$$.