3
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.