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

Question

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?

Explanation / Answer

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 eq NP$, so you can imagine that we don't know if they exist. The reverse implication (does $P eq 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.