Paper 2020/666
Revisiting the Hardness of Binary Error LWE
Chao Sun, Mehdi Tibouchi, and Masayuki Abe
Abstract
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. In this paper, we first examine more generally how the hardness of the problem varies with the number of available samples. Under standard heuristics on the AroraGe polynomial system, we show that, for any $\epsilon >0$, binary error LWE can be solved in polynomial time $n^{O(1/\epsilon)}$ given $\epsilon\cdot n^{2}$ samples. Similarly, it can be solved in subexponential time $2^{\tilde O(n^{1\alpha})}$ given $n^{1+\alpha}$ samples, for $0<\alpha<1$. As a second contribution, we also generalize the binary error LWE to problem the case of a nonuniform error probability, and analyze the hardness of the nonuniform binary error LWE with respect to the error rate and the number of available samples. We show that, for any error rate $0 < p < 1$, nonuniform binary error LWE is also as hard as worstcase lattice problems provided that the number of samples is suitably restricted. This is a generalization of Micciancio and Peikert's hardness proof for uniform binary error LWE. Furthermore, we also discuss attacks on the problem when the number of available samples is linear but significantly larger than $n$, and show that for sufficiently low error rates, subexponential or even polynomial time attacks are possible.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. ACISP 2020
 Keywords
 Binary Error LWEAlgebraic AttacksMacaulay MatrixComplexity Tradeoffs
 Contact author(s)
 sun chao 46s @ st kyotou ac jp
 History
 20200605: received
 Short URL
 https://ia.cr/2020/666
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/666, author = {Chao Sun and Mehdi Tibouchi and Masayuki Abe}, title = {Revisiting the Hardness of Binary Error LWE}, howpublished = {Cryptology ePrint Archive, Paper 2020/666}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/666}}, url = {https://eprint.iacr.org/2020/666} }