Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question
3  
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. – Chris Peikert Mar 13 at 21:58
1  
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... – poncho Mar 13 at 22:46
    
@ChrisPeikert It would be nice if you turn your comment into an answer. Related: meta.crypto.stackexchange.com/questions/404/… – cygnusv Mar 17 at 8:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.