3
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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