Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The book Foundations of Cryptography states:
It was understood that problems related to breaking a 1-1 cryptographic mapping could not be NP-complete and, more important, that NP-hardness of the breaking task was poor evidence for cryptographic security.
But I thought the whole point of complexity theory was to determine which problems were NP so that we might be able to use the infeasibility of their solutions to produce security?
NP is about worst case hardness. An NP-hard problem can in fact be very easy to solve for the majority of cases. This would obviously be a poor cryptographic system. Further, some NP-hard problems may even be quite easy to approximate. This could also be bad for cryptography.
