The golden standard of difficulty for a computational problem is NP
hardness. The security of most cryptographic tasks, on the other hand,
is based on assumptions that are seemingly stronger than P =/= NP.
Intuitively, we expect solving satisfiability to be harder than
breaking encryption because a solver for satisfiability must work on
all formulas, while an adversary for encryption need only succeed on a
random ciphertext. The hardness of satisfiability is based on a
worst-case hardness assumption (namely P =/= NP), while most of
cryptography appears to require average-case hardness assumptions.

However, the intriguing possibility that cryptography and much of
average-case complexity can be based on NP hardness remains open.
Certain constructions in cryptography and coding theory suggest that
such a connection may be possible. In this talk I will present
contrasting evidence that partially explains why a connection between
worst-case and average-case hardness for NP is difficult to establish.
It turns out that worst-case and average-case complexity are different
for much the same reason that an individual feels anonymous when part
of a large crowd.