Wonderful Cryptography

Topics for a motivational "introduction to cryptography" lecture

The following are some suggested topics for a motivational "introduction to cryptography" lecture for a non-specialized audience. The choice criteria are as follows: convey ideas of some technical or theoretical depth; provide a feeling for the scope of cryptographic research; maximize novelty and intellectual stimulus; motivate things by relating them to common objects and tasks. Of course, the specific choice of topics and pace would depend on the target audience.
I haven't personally presented the following yet, but I believe they can also work well:
Other educational resources in cryptography:
Note: the bibliographic references are by no means exhaustive; in most cases I cited only a survey paper or the first relevant works.

Suggestions and comments are welcome!
Acknowledgments. I am indebted to Boaz Barak, Alex Biryukov, Moni Naor, Tal Rabin and Adi Shamir for valuable suggestions, and to Yossi Vardi and the rest of the KinnerNet 2005 participants for providing the perfect motivation for preparing my first such talk.

-- Eran Tromer