**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 Arora--Ge 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 non-uniform error probability, and analyze the hardness of the non-uniform 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$, non-uniform binary error LWE is also as hard as worst-case 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.

**Category / Keywords: **Binary Error LWE, Algebraic Attacks, Macaulay Matrix, Complexity Tradeoffs

**Original Publication**** (in the same form): **ACISP 2020

**Date: **received 3 Jun 2020

**Contact author: **sun chao 46s at st kyoto-u ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20200605:195105 (All versions of this report)

**Short URL: **ia.cr/2020/666

[ Cryptology ePrint archive ]