Serious Cryptography

9HARD PROBLEMS

Hard computational problems are the cornerstone of modern cryptography. They’re problems that are simple to describe yet practically impossible to solve. These are problems for which even the best algorithm wouldn’t find a solution before the sun burns out.

In the 1970s, the rigorous study of hard problems gave rise to a new field of science called computational complexity theory, which would dramatically impact cryptography and many other fields, including economics, physics, and biology. In this chapter, I’ll give you the conceptual tools from complexity theory necessary to understand the foundations of cryptographic security, ...