Skip to main content
added 108 characters in body; edited title
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Can all NP-hardcomplete cryptosystems be broken if one is broken?

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 NPan equivalent (NP-hard) optimisation problem. AttackA successful attack on the one such NP-hard cryptosystem will$A$ would mean that every other NP-hard cryptosystem will$B$ would be vulnerable to that same attack; just reduce $B$ to $A$ and use the available attack after reducing it. 

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

Is this consideration correct?

NP-hard cryptosystems

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 NP-hard problem. Attack on the one NP-hard cryptosystem will mean that every NP-hard cryptosystem will be vulnerable to that attack after reducing it. That would actually mean that we will be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?

Can all NP-complete cryptosystems be broken if one is broken?

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?

edited tags; edited tags; edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Tweeted twitter.com/#!/StackCompSci/status/448142213160398848
Post Migrated Here from stackoverflow.com (revisions)
Source Link
user3313119
user3313119

NP-hard cryptosystems

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 NP-hard problem. Attack on the one NP-hard cryptosystem will mean that every NP-hard cryptosystem will be vulnerable to that attack after reducing it. That would actually mean that we will be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?