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 ?
$\begingroup$
$\endgroup$
3
-
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$– Chris PeikertMar 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$– ponchoMar 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$– cygnusvMar 17, 2016 at 8:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
