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 '16 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 '16 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 '16 at 8:22

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, privacy policy and cookie policy

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