# Learning with (Signed) Errors

$\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)

(wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel)

This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three years ago), trivially reduces from the Extended Learning with Errors (eLWE) problem first introduced in the work Bi-Deniable Public-Key Encryption by O'Neill, Peikert, and Waters at CRYPTO 2011.

The eLWE problem is defined analogously to the "standard" LWE (i.e. [Regev2005]), except the distributions' (efficient) distinguisher is additionally given "hints" on the LWE sample's error vector $\vec{x}$, in the form of (possibly noisy) inner products with an arbitrary vector $\vec{z}$. (In applications $\vec{z}$ is often the decryption-key vector of some cryptosystem.)

Formally, the $\mathsf{eLWE}_{n,m,q,\chi,\beta}$ problem is described as follows:

For an integer $q = q(n) \ge 2$, and an error distribution $\chi = \chi(n)$ over $\mathbb{Z}_q$, the extended learning with errors problem is to distinguish between the following pairs of distributions: $$\{\mathbf{A}, \vec{b} = \mathbf{A}^T\vec{s}+\vec{x}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ $$\{\mathbf{A}, \vec{u}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ where $\mathbf{A}\leftarrow \mathbb{Z}_q^{n\times m}, \vec{s}\leftarrow\mathbb{Z}_q^n, \vec{u}\leftarrow\mathbb{Z}_q^m, \vec{x}, \vec{z}\leftarrow\chi^m,$ and $x'\leftarrow\mathcal{D}_{\beta q}$, and where $\mathcal{D}_\alpha$ is the (1-dimensional) Discrete Gaussian distribution with width $\alpha$.

It is easy to see that eLWE captures "the spirit" of LWSE, though a formal reduction can be shown with not too much additional effort.

Major follow-up ideas toward understanding the Extended-LWE problem are developed in the works:

Depending on whether your secret key lives in $\mathbb{Z}_q$ or is binary (and the nature of various other parameter choices), you can use the first or second paper's reductions to ultimately quantumly/classically reduce from $\mathsf{GapSVP}_\alpha$ with approximation factor $\alpha \ge \Omega(n^{1.5})$ to LWSE.