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 Mar 30 '17 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 Mar 31 '17 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 Apr 3 '17 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 Apr 6 '17 at 12:10

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.

| improve this answer | |
  • $\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 Mar 31 '17 at 1:40
  • $\begingroup$ Cryptography based on multivariate polynomials is another example --- their worst-case--average-case relationship is not known though. $\endgroup$ – Occams_Trimmer Mar 31 '17 at 11:35
  • 3
    $\begingroup$ "Moreover, no quantum algorithms are known against these problems." - No polynomial time quantum algorithms... $\endgroup$ – TMM Apr 3 '17 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).

| improve this answer | |

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).

| improve this answer | |
  • $\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 Sep 18 at 17:19

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.