5
$\begingroup$

I was just reading something about NP-hard problems and cryptosystems.

I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) optimisation problem. A successful attack on one such NP-hard cryptosystem $A$ would mean that every other NP-hard cryptosystem $B$ would be vulnerable to that same attack; just reduce $B$ to $A$ and use the available attack.

That would actually mean that we would be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?

Improve this question
$\endgroup$
5

4 Answers 4

Reset to default
7
$\begingroup$

As Yuval points out, contemporary crypto systems are not based on NP-complete problems.

NP-hardness is a worst-case notion of hardness. A problem might be NP-hard but easy to solve in many cases, or on average, or even in most cases. A crypto systems that was easy to crack on average would not be useful. We want crypto systems that are hard to crack in almost all cases (we cannot ask for all cases because the adversary can -- in principle -- just guess the secret used).

This seemingly stronger notion of hardness is formalised by one-way functions.

Incidentally, the existence of one-way functions implies $P \neq NP$, so you can imagine that we don't know if they exist. The reverse implication (does $P \neq NP$ imply the existence of one-way functions) is also an open problem.

There is an interesting theory of physical unclonable function which can be seen as the physical analogue of a one-way function.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That does not answer the question at all. Assume you used an NP-hard problem for crypto, would an efficient solution for another NP-hard problem automatically invalidate the crypto system? (The question you are answering we already have.) $\endgroup$
    – Raphael
    Commented Mar 24, 2014 at 21:34
  • $\begingroup$ I must admit I don't fully understand the original question. Anyway, all NP-complete problems are translatable into each other at the cost of a polynomial slowdown. In (theoretical) cryptography, adversaries are always assumed to have polynomial computational power (attackers are probabilistic Turing machines in BPP to be precise). Hence, if you can crack even one NP-hard problem, all encryption based on NP-hardness falls. $\endgroup$
    – Martin Berger
    Commented Mar 24, 2014 at 22:46
  • $\begingroup$ I think that's the answer we are looking for here. $\endgroup$
    – Raphael
    Commented Mar 24, 2014 at 22:47
3
$\begingroup$

Cryptosystems are not based on NP-hard problems. There are several standard hardness assumptions in cryptography on which cryptographic primitives are based, and cryptosystems are constructed based on cryptographic primitives, whose existence is thus assumed.

An example of a hardness assumption is DDH (Decisional Diffie–Hellman): given a prime $p$ and a generator $g$ of $\mathbb{Z}_p^\times$, it is hard to distinguish triples $(g,g^x,g^y,g^{xy})$ (for random $g$ generating $\mathbb{Z}_p^*$ and random $x,y \in \mathbb{Z}_{p-1}$) from triples $(g,g^x,g^y,g^z)$ (for random $g$ generating $\mathbb{Z}_p^*$ and random $x,y,z \in \mathbb{Z}_p$).

An example of a cryptographic primitive is a one-way function. While the various definitions of one-way functions are somewhat intricate, informally a one-way function is a function that is easy to compute but hard to invert. One such example is $x \mapsto g^x \pmod{p}$, and assuming DDH, you can construct a secure one-way function based on this idea.

Cryptosystems, in turn, are composed out of cryptographic primitives satisfying some security assumptions, such as the one just mentioned: a one-way function is hard to invert. The primitives, in turn, are based on their own security assumptions, like DDH. The latter are different from NP-hardness in an important way: what is needed is average-case hardness rather than worst-case hardness.

Real-world cryptosystems are not usually based on this theory, their security being based on their designers (and then other cryptologists) not being able to break them. This seems to work rather well in practice.

Improve this answer
$\endgroup$
8
  • $\begingroup$ That does not answer the question at all. Assume you used an NP-hard problem for crypto, would an efficient solution for another NP-hard problem automatically invalidate the crypto system? (The question you are answering we already have.) $\endgroup$
    – Raphael
    Commented Mar 24, 2014 at 21:34
  • $\begingroup$ @Yuval : $\;\;\;$ Your formulation of DDH is false. $\:$ See this answer. $\;\;\;\;\;\;$ $\endgroup$
    – user12859
    Commented Mar 27, 2014 at 11:17
  • $\begingroup$ Right, I'm assuming that $g$ is known and fixed whereas in some formulations $g$ varies and is given. $\endgroup$
    – Yuval Filmus
    Commented Mar 27, 2014 at 11:55
  • $\begingroup$ Even if "$g$ is known and fixed", if it generates $\mathbb{Z}_p^{\times}$ then, as described in the answer my previous $\hspace{.25 in}$ comment links to, one can easily distinguish, by almost 1/2, random tuples vs. DDH tuples. $\hspace{.9 in}$ $\endgroup$
    – user12859
    Commented Apr 1, 2014 at 15:47
  • $\begingroup$ Ok, you win. Corrected the formulation of DDH. $\endgroup$
    – Yuval Filmus
    Commented Apr 1, 2014 at 17:36
0
$\begingroup$

as other answers point out crypto systems are generally not built out of proven NP complete problems although modern crypto is basically built out of assumptions equivalent or similar to P≠NP. following is a rare crypto system proposal that is based on an NP complete problem & has some analysis wrt NP completeness on cryptographic security. it seems not to be used. havent heard of later/followup analysis of its security. note that crypto hardness depends a lot on average case complexity which has many open problems associated with it. another useful ref in this area is Impagliazzo's worlds that describes the possible worlds we may be living in wrt cryptographic security.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think much "modern crypto" is build on "assumptions equivalent [...] to P≠NP". $\endgroup$
    – Martin Berger
    Commented Mar 24, 2014 at 15:58
  • $\begingroup$ existence of cryptographic trapdoor/one-way functions are roughly connected to the P=?NP conjecture. you omitted "or similar". the Impaggliazo ref shows the interconnections in more detail. direct connections have not been proven but havent been ruled out either. $\endgroup$
    – vzn
    Commented Mar 24, 2014 at 16:05
  • $\begingroup$ I suggest to be more precise and replace " equivalent or similar" by something like "similar to, but (probably) harder than". $\endgroup$
    – Martin Berger
    Commented Mar 24, 2014 at 16:08
  • $\begingroup$ feel free to edit to your satisfaction. ... but, not sure exactly what you meant; who conjectures that modern crypto is built out of assumptions stronger than P≠NP? $\endgroup$
    – vzn
    Commented Mar 24, 2014 at 17:03
0
$\begingroup$

No, if you created two NP-complete cryptographic systems, the solution to one would not fundamentally provide a fast solution to the other. This is because NP-Hard is an exceptionally loose concept.

I think we'd all be pretty happy if it took someone $n^{10}$ milliseconds to crack an $n$-bit key. If $n=2048$, that's $10^{12}$ times the age of the universe. And yet, if there's an $n^{10}$ overhead in converting NP-Complete problem $A$ into an instance of NP-Complete problem $B$, that's totally "fast" by NP-Hard's standards. If that's the best reduction we know of, that's how much it's going to cost you to use your solution to $B$. Heck, make that $10$ a $4$, and it's still 500 years!

High level asymptotic analysis can really lose sight of reality sometimes.

I should emphasize that this of course assumes that you have found two NP-Complete problems for which you can generate many genuinely difficult instances. It could also be the case that there does in fact exist a genuinely fast reduction of $A$ into $B$. It's simply not guaranteed in any way by the definition of NP-hardness.

Improve this answer
$\endgroup$
3
  • $\begingroup$ And yet, typical reductions among NP-complete problems (or their optimisation versions) are fast. (Also, you insert a new worst-case where we want "all case" in cryptography, namely the runtime of the reduction.) I agree with your basic sentiment about asymptotic analysis, by the way, but I think you don't make a good case for that position in this post. $\endgroup$
    – Raphael
    Commented Mar 25, 2014 at 0:34
  • $\begingroup$ @Raphael: This is why I prefixed my statement with "if you created two NP-complete cryptographic systems". I assume that this is the case for sake of argument. I also assume that they are actually useful (slow to solve in all cases). You are correct that reductions only emphasize the worst-case, but that's besides the point: the notion of NP-hardness is too vague to guarantee that a practical fast solution to one class of problems would permit a practical fast solution to another. It is of course always possible that there exists a fast reduction between the two problems. $\endgroup$
    – Alexis Beingessner
    Commented Mar 25, 2014 at 0:47
  • $\begingroup$ @AlexisBeingessner I'd say that if one wanted to base one's crypto system of the hardness of an NP-complete problem then one has already committed to asymptotic analysis (and the probabilistic polynomial time adversaries of theoretical cryptography). $\endgroup$
    – Martin Berger
    Commented Mar 25, 2014 at 11:57

Your Answer

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