2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.