Revisiting the Hardness of Binary Error LWE
説明
Binary error LWE is the particular case of the learning with errors (LWE) problem in which errors are chosen in \(\{0,1\}\). It has various cryptographic applications, and in particular, has been used to construct efficient encryption schemes for use in constrained devices. Arora and Ge showed that the problem can be solved in polynomial time given a number of samples quadratic in the dimension n. On the other hand, the problem is known to be as hard as standard LWE given only slightly more than n samples.
