There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?

  • 9
    $\begingroup$ It's not NP-hard problems what people are looking for to begin with $\endgroup$
    – Daniel
    Commented Mar 30, 2017 at 3:57
  • 1
    $\begingroup$ Thanks for your answer.But now it's called "post-quantum age".I think the base of the cryptographic primitives should be built on NP-hard problems.Whether it's hard to find some useful property like average-case hardness on other NP-hard problems? $\endgroup$
    – Little Nan
    Commented Mar 31, 2017 at 1:26
  • $\begingroup$ I've rephrased the question title, it looked that lattice problems were only used for cryptography, not for other math related problems. That's of course not what was asked. $\endgroup$
    – Maarten Bodewes
    Commented Apr 3, 2017 at 22:44
  • $\begingroup$ "Why have only lattice problems been applied to cryptograhpy?" What happened to MQ-based, code-based and hash-based? $\endgroup$
    – Elias
    Commented Apr 6, 2017 at 12:10

3 Answers 3


What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard.

What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high probability.

Lattices are interesting as some of its average-case hard problems (ex. Shortest Integer Solution, SIS) allow a reduction to worst-case hard problems (ex. Shortest Independent Vector Problem, SIVP) --- i.e. solving a random instance of one problem is as hard as solving worst-case instance of another. No efficient quantum algorithms are known against these problems either.

Moreover, lattices have enough underlying algebraic structure which allows building cryptographic primitives (OWFs, Trapdoors, FHEs...) based on these hard problems --- see the survey by Peikert.

  • $\begingroup$ Thanks for your answer.I know that there are many useful properties on Lattices like average-case hardness .But just like decoding of random linear code,it has average-case hardness naturally.And I don't know whether some other problems maybe with some good algebraic structure have those good property which are needed in cryptography? $\endgroup$
    – Little Nan
    Commented Mar 31, 2017 at 1:40
  • $\begingroup$ Cryptography based on multivariate polynomials is another example --- their worst-case--average-case relationship is not known though. $\endgroup$
    – ckamath
    Commented Mar 31, 2017 at 11:35
  • 3
    $\begingroup$ "Moreover, no quantum algorithms are known against these problems." - No polynomial time quantum algorithms... $\endgroup$
    – TMM
    Commented Apr 3, 2017 at 0:45


It seems that this is an open problem : "if we can base cryptography in $P\not= NP$". Also as the previous poster wrote there are some other problems except lattices as : multivariate crypto (J.Patarin scheme) and problems based on codes (McEliece cryptosystem).


You might want to take a look at the Post-quantum Cryptography book by Bernstain, Dahmen, and Buchmann. There are more problems used in post-quantum crypto than just lattice problems:

  • Security of symmetric primitives,
  • problems from coding theory,
  • the MQ problem, and quite recently
  • problems of isogenies.

Some of the problems are NP-hard (which only refers to the worst-case as mentioned in the other answer), some are not. In any case, even for lattice-based cryptography we actually do not make use of the worst-case hardness in practice. Parameters in practice are never chosen such that the related worst-case instance is actually hard (at least I am not aware of any case).

  • $\begingroup$ While this is an old post, you're right. Parameters are chosen such that that the underlying worst-case hard problem is $\mathsf{SVP}_\gamma$ or $\mathsf{SIVP}_\gamma$ (approximate shortest vector problem/shortest independent vector problem). The approximation factor $\gamma$ (that we can get worst-case to average case reductions for) is $>\sqrt{n}$ (where $n$ is the dimension of the lattice), but SVP is known to be in coNP for that approximation factor, so cannot be NP-hard unless NP = coNP. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 18, 2020 at 17:19

Your Answer

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

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