2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP.

$\endgroup$
  • $\begingroup$ But the GapSVP is the decisional version of SVP, right? So it is not a "Gap problem" in the sense described in my question $\endgroup$ – cygnusv Nov 26 '14 at 9:10
  • 2
    $\begingroup$ @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. $\endgroup$ – Guut Boy Dec 25 '14 at 12:18
  • $\begingroup$ @GuutBoy: Thanks for the clarification. Still, GapSVP is a decisional problem (the goal is to return YES or NO), so it is not a "Gap problem" as understood in my question (i.e., solving the computational 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. I am looking for a computational problem (related to LWE) that is still hard using a decisional oracle for said problem. $\endgroup$ – cygnusv Dec 25 '14 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.