$\underline{\bf Background}$
In 2005, Regev [1] introduced the Learning with Errors (LWE) problem, a generalization of the Learning Parity with Error problem. The assumption of this problem's hardness for certain parameter choices now underlies the security proofs for a host of post-quantum cryptosystems in the field of lattice-based cryptography. The "canonical" versions of LWE are described below.
Preliminaries:
Let $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ be the additive group of reals modulo 1, i.e. taking values in $[0, 1)$. For positive integers $n$ and $2 \le q \le poly(n)$, a "secret" vector ${\bf s} \in \mathbb{Z}_q^n$, a probability distribution $\phi$ on $\mathbb{R}$, let $A_{{\bf s}, \phi}$ be the distribution on $\mathbb{Z}_q^n \times \mathbb{T}$ obtained by choosing ${\bf a} \in \mathbb{Z}_q^n$ uniformly at random, drawing an error term $x \leftarrow \phi$, and outputting $({\bf a}, b' = \langle{\bf a}, s\rangle/q + x) \in \mathbb{Z}_q^n \times \mathbb{T}$.
Let $A_{{\bf s}, \overline{\phi}}$ be the "discretization" of $A_{{\bf s}, \phi}$. That is, we first draw a sample $({\bf a}, b')$ from $A_{{\bf s}, \phi}$ and then output $({\bf a}, b) = ({\bf a}, \lfloor b'\cdot q\rceil) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$. Here $\lfloor\circ\rceil$ denotes rounding $\circ$ to the nearest integral value, so we can view $({\bf a}, b)$ as $({\bf a}, b= \langle {\bf a}, {\bf s} \rangle + \lfloor q\cdot x\rceil)$.
In the canonical setting, we take the error distribution $\phi$ to be a Gaussian. For any $\alpha > 0$, the density function of a 1-dimensional Gaussian probability distribution over $\mathbb{R}$ is given by $D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$. We write $A_{{\bf s}, \alpha}$ as shorthand for the discretization of $A_{{\bf s}, D_\alpha}$
LWE Definition:
In the search version $LWE_{n, q, \alpha}$ we are given $N = poly(n)$ samples from $A_{{\bf s}, \alpha}$, which we can view as "noisy" linear equations (Note: ${\bf a}_i, {\bf s} \in \mathbb{Z}_q^n, b_i \in \mathbb{Z}_q$):
$$\langle{\bf a}_1, {\bf s}\rangle \approx_\chi b_1\mod q$$ $$\vdots$$ $$\langle{\bf a}_N, {\bf s}\rangle \approx_\chi b_N\mod q$$
where the error in each equation is independently drawn from a (centered) discrete Gaussian of width $\alpha q$. Our goal is to recover ${\bf s}$. (Observe that, with no error, we can solve this with Gaussian elimination, but in the presence of this error, Gaussian elimination fails dramatically.)
In the decision version $DLWE_{n, q, \alpha}$, we are given access to an oracle $\mathcal{O}_{\bf s}$ that returns samples $({\bf a}, b)$ when queried. We are promised that the samples either all come from $A_{{\bf s}, \alpha}$ or from the uniform distribution $U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)$. Our goal is to distinguish which is the case.
Both problems are believed to be $hard$ when $\alpha q > 2\sqrt n$.
Connection to Complexity Theory:
It is known (see [1], [2] for details) that LWE corresponds to solving a Bounded Distance Decoding (BDD) problem on the dual lattice of a GapSVP instance. A polynomial time algorithm for LWE would imply a polynomial time algorithm to approximate certain lattice problems such as SIVP and SVP within $\tilde O(n/\alpha)$ where $1/\alpha$ is a small polynomial factor (say, $n^2$).
Current Algorithmic Limits
When $\alpha q \le n^\epsilon$ for $\epsilon$ strictly less than 1/2, Arora and Ge [3] give a subexponential-time algorithm for LWE. The idea is that, from well-known properties of the Gaussian, drawing error terms this small fits into a "structured noise" setting except with exponentially low probability. Intuitively in this setting, every time we would have received 1 sample, we receive a block of $m$ samples with a promise that no more than some constant fraction contain error. They use this observation to "linearize" the problem, and enumerate over the error space.
$\underline{\bf Question}$
Suppose we are, instead, given access to an oracle $\mathcal{O}_{\bf s}^+$. When queried, $\mathcal{O}_{\bf s}^+$ first queries $\mathcal{O}_{\bf s}$ to obtain a sample $({\bf a}, b)$. If $({\bf a}, b)$ was drawn from $A_{{\bf s}, \alpha}$, then $\mathcal{O}_{\bf s}^+$ returns a sample $({\bf a}, b, d) \in \mathbb{Z}_q^n \times \mathbb{Z}_q \times \mathbb{Z}_2$ where $d$ represents the "direction" (or $\pm$-valued "sign") of the error term. If $({\bf a}, b)$ was drawn at random, then $\mathcal{O}_{\bf s}^+$ returns $({\bf a}, b, d) \leftarrow U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)\times U(\mathbb{Z}_2)$. (Alternatively, we could consider the case when the bit $d$ is chosen adversarially when $b$ is drawn uniformly at random.)
Let $n, q, \alpha$ be as before, except that now $\alpha q > c\sqrt n$ for a sufficiently large constant $c$, say. (This is to ensure that the absolute error in each equation remains unaffected.) Define the Learning with Signed Error (LWSE) problems $LWSE_{n, q, \alpha}$ and $DLWSE_{n, q, \alpha}$ as before, except that now we have the additional bit of advice for each error term's sign.
Are either version of LWSE significantly easier than their LWE counterparts?
E.g.
1. Is there a subexponential-time algorithm for LWSE?
2. What about a polynomial-time algorithm based on, say, linear programming?
In addition to the above discussion, my motivation is an interest in exploring algorithmic options for LWE (of which we currently have relatively few to choose from). In particular, the only restriction known to provide good algorithms for the problem is related to the magnitude of the error terms. Here, the magnitude remains the same, but the range of error in each equation is now "monotone" in a certain way. (A final comment: I'm unaware of this formulation of the problem appearing in the literature; it appears to be original.)
References:
[1] Regev, Oded. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," in JACM 2009 (originally at STOC 2005) (PDF)
[2] Regev, Oded. "The Learning with Errors Problem," invited survey at CCC 2010 (PDF)
[3] Arora, Sanjeev and Ge, Rong. "New Algorithms for Learning in Presence of Errors," at ICALP 2011 (PDF)
