9
$\begingroup$

Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}$-CVP is shown to be NP-hard, then the polynomial hierarchy collapses.

This seems to imply that, if the polynomial hierarchy does not collapse, we could not hope to show that $n/\alpha$-CVP is NP-hard, meaning that Regev's reduction cannot show that a poly-time LWE algorithm implies $NP\subseteq BQP$. Is that true?

If so, is there some sort of no-go theorem the other way? That is, maybe we want to come up with a better reduction. But if $\sqrt{n/\log n}$-CVP could solve LWE, then we can't hope to reduce LWE to $O(1)$-CVP or else we would show that $\sqrt{n/\log n}$-CVP is NP-hard, again collapsing the polynomial hierarchy. Is this also true? What is the maximum approximation factor of CVP that can still solve LWE?

(and of course, similar questions apply to the classical reduction).

Improve this question
$\endgroup$
4
  • $\begingroup$ It's possible for something to be NP-hard for some parameters and not NP-hard for others. Just a guess here... $\endgroup$
    – Yehuda Lindell
    Apr 23, 2020 at 15:53
  • $\begingroup$ Right, so the parameters of LWE are the prime, the noise distribution, and number of samples? Regev's reduction works for basically any of them within a certain range I thought. $\endgroup$
    – Sam Jaques
    Apr 24, 2020 at 12:05
  • $\begingroup$ I don't mean those parameters. I mean the approximation factor. $\endgroup$
    – Yehuda Lindell
    Apr 25, 2020 at 20:35
  • $\begingroup$ Right, by $\gamma$-CVP I meant an approximation factor of $\gamma$. It seems like the transition between NP-hard approximation factors and not NP-hard is between $O(1)$ and $\sqrt{n/\log n}$, from the results mentioned above. But it seems like this excludes LWE from being NP-hard. $\endgroup$
    – Sam Jaques
    Apr 27, 2020 at 8:21

0

Reset to default

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.