Regarding LWE schemes where the encryption is performed this way:

for $m \in \mathbb{Z}_t$, compute $c = LWE_{\mathbf{s}}^{t/q}(m) = \{ \mathbf{a}, \mathbf{a \cdot s} + m\cdot q/t + e\} \in \mathbb{Z}_{q}^{n}$

(where $\mathbf{s}$ is the secret vector of length $n$, $\mathbf{a}$ is a random vector and $e$ is some noise generated by a discrete Gaussian sampler)

What happens if for a given plaintext modulus $t$, we use only a small subspace of $Z_t$ for our messages? Does it have any influence on the overall security of the scheme?

  • 1
    $\begingroup$ Notice that in the CPA-security game, an attacker could restrict the set of messages they are working with to any subset. Therefore, if the scheme is proved to be CPA-secure, your scenario is also safe. $\endgroup$ – Hilder Vitor Lima Pereira Mar 13 '19 at 15:55
  • $\begingroup$ Oh yeah true I didn't think about this... Thank you! $\endgroup$ – Binou Mar 14 '19 at 1:08

No, as long as your plaintext space is a subset of $Z_t$, then there is not any negative impact on security.

However, if you use a smaller message space $Z_x\subset Z_t$, you should consider setting the plaintext space to $Z_x$ directly as this could improve the efficiency.

  • $\begingroup$ I am actually doing this for the purpose of homomorphic encryption, where I need to use a tiny subset. But thank you anyway! $\endgroup$ – Binou Mar 13 '19 at 10:10

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.