# Gap problem for Learning With Errors

Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and Pointcheval in this paper, originally related to Diffie-Hellman problems.

For example, the Gap Diffie-Hellman Problem (GDH) is to solve the Computational Diffie-Hellman (CDH) problem with the help of a Decisional Diffie-Hellman (DDH) Oracle (which answers whether a given triple is a Diffie-Hellman triple or not).

In the Learning With Errors (LWE) setting, is there any "gap" problem (or similar) that can be assumed to be hard? That is, which computational problem can be defined that is still hard when using an oracle for the Decision LWE? I know that there are some results (see papers from Regev and @chris-peikert) that prove the equivalence of the decision and search versions of the LWE problems. I guess that this means that a "strict" gap problem cannot be defined, since there is a reduction from the Decision LWE to the Search LWE, but maybe some other variant of LWE or related problem still applies.

• @cygnusv GapSVP is not simply decisional SVP it is an approximation version of the decisional SVP. I.e., in the decisional SVP you must, given a lattice $L$ and a length $d$, decide if the shortest vector of $L$ is shorter than $d$ or not. In GapSVP you must decide if the shortest vector is shorter than $d$ or if it is longer than $\gamma \cdot d$ where $\gamma$ is an approximation factor. For lattices with shortests vectors in the gap between $d$ and $\gamma \cdot d$ results is undefined. This is a standard way to define approximation problems also known as Gap Problems. Dec 25, 2014 at 12:18