0
$\begingroup$

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?

$\endgroup$
2
  • 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$ Commented Mar 13, 2019 at 15:55
  • $\begingroup$ Oh yeah true I didn't think about this... Thank you! $\endgroup$
    – Binou
    Commented Mar 14, 2019 at 1:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Mar 13, 2019 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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