debugMinor
Can all NP-complete cryptosystems be broken if one is broken?
Viewed 0 times
canallbrokencryptosystemscompleteone
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#23000, answer score: 7
Revisions (0)
No revisions yet.