There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
$\begingroup$
$\endgroup$
4
-
9$\begingroup$ It's not NP-hard problems what people are looking for to begin with $\endgroup$– DanielMar 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 NanMar 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 ♦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$– EliasApr 6, 2017 at 12:10
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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$ 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$– ckamathMar 31, 2017 at 11:35
-
3$\begingroup$ "Moreover, no quantum algorithms are known against these problems." - No polynomial time quantum algorithms... $\endgroup$– TMMApr 3, 2017 at 0:45
$\begingroup$
$\endgroup$
See
- 1:stackoverflow
- 2:cs.stackexchange,
- 3:On the possibility of basing Cryptography on the assumption that P!=NP and
- (before Ajtai) 4:A Personal View of Average-Case Complexity (Impagliazzo 1995).
- 5:Average case complexity (Trevisan,Bogdanov)
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).
$\begingroup$
$\endgroup$
1
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$– MarkSep 18, 2020 at 17:19