In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE problem, it would weaken the problem significantly or the security insured would remain the same ?

  • 5
    $\begingroup$ Security would remain the same if $q$ is odd, and would be compromised if $q$ is even. The reason for the former is that you can multiply LWE samples by 2, which doubles the underlying error and retains the uniform distribution of the $a_i$. If $q$ is even this is not the case, and the $b_i$ are always even so they are easily distinguished from uniform. $\endgroup$ Mar 13, 2016 at 21:58
  • 1
    $\begingroup$ Actually, doubling the error vectors would increase the size of the errors that are introduced, vastly increasing the probability of an overflow (resulting in, say, a decryption failure). In Lattice terms, by doubling the error vector, you're increasing the probability that the original point isn't actually the nearest one. You can half $e$ to compensate, but that would make it easier on the attacker... $\endgroup$
    – poncho
    Mar 13, 2016 at 22:46
  • $\begingroup$ @ChrisPeikert It would be nice if you turn your comment into an answer. Related: meta.crypto.stackexchange.com/questions/404/… $\endgroup$
    – cygnusv
    Mar 17, 2016 at 8:22

1 Answer 1


It will remain same. Here it will not effect the security because 2 is invertible in the prime q field. In case q is not prime then security will be compromised.


Your Answer

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

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