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.

If you have any suggestions for additions or corrections, please contact me.

  • Breaking a cipher you know nothing about
    Differential fault-analysis of unknown ciphers using asymmetric bit flip faults.
    • Eli Biham, Adi Shamir 1997, Differential fault analysis of secret key cryptosystems, proc. CRYPTO 1997, 513-525, LNCS 1294, Springer-Verlag, 1997. [ps]
  • Breaking ciphers using a microphone
    Survey of side-channel attacks (faults, EM, power, timing, diffuse visible light, acoustic, cache). Examples from diffuse CRT reflections, acoustic cryptanalysis and CRT TEMPEST.
    • Markus G. Kuhn, Compromising emanations: eavesdropping risks of computer displays, technical report UCAM-CL-TR-577, Cambridge, 2003 [web]
    • Erik Thiele, Tempest for Eliza, 2001 [web]
    • Daniel Genkin, Adi Shamir, Eran Tromer, RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis, proc. CRYPTO 2014, part I, LNCS 8616, 444-461, 2014. [pdf] [web]
  • ... or bicycle chains
    Special-purpose factoring devices: Carissan's, Lehmer's, TWINKLE.
    • Special-purpose cryptanalytic devices — an annotated taxonomy [web]
  • How to leak a secret
    Digital signature, ring signatures and ring authentication (sans implementation).
    • Ronald L. Rivest, Adi Shamir, and Yael Tauman, How to Leak A Secret, proc. Asiacrypt 2001, 552-565, LNCS 2248, Springer-Verlag, 2001. [pdf]
    • Moni Naor, Deniable ring authentication, proc. CRYPTO 2002, 481-498, LNCS 2442, Springer-Verlag, 2002. [web]
  • How to sign your mail without really meaning it
    Deniable signatures, as special case of ring signatures. The problem with deniability when the recipient can plausibly deny knowledge of his own secret key leads to:
  • How to prove things without revealing your sources
    The concept of zero-knowledge, exemplified by Kid Cryptography and graph 3-colorability (or Hamiltonicity).
    • Moni Naor, Yael Naor and Omer Reingold, Applied kid cryptography, Journal of Craptology, vol. 0 no. 1, 1999. [ps] [web]
    Zero-knowledge explained via an "Ali Baba and a magical cave" metaphor:
    • Jean-Jacques Quisquater, Louis Guillou, Marie Annick, Tom Berson, How to explain zero-knowledge protocols to your children, proc. CRYPTO 1989, 628-631, Springer-Verlag, 1989. [pdf]
  • Romantic applications of playing cards
    The concept of secure multiparty computation, exemplified by the 5-card protocol for secure evaluation of AND (consider using a lazy suzie instead of oblivious cuts). Any function can be securely computed with a sufficiently large deck of cards.
    • Bert den Boer, More efficient match-making and satisfiability — the five card trick, proc. Eurocrypt '89, LNCS 434, 208, 2000. [springer](non-free)
    • Anton Stiglic, Computations with a deck of cards, Theoretical Computer Science, vol. 259 no. 1–2, 671–678, 2001. [pdf]
  • Voting using PEZ candy
    More secure computation, using a PEZ dispenser: the 3-candy protocol for AND and the 13-candy protocol for 3-party voting. Any function can be securely computed given enough candy!
    • Jozsef Balogh, Janos Csirik, Yuval Ishai, Eyal Kushilevitz, Private computation using a PEZ dispenser, Theoretical Computer Science , vol. 306 no. 1-3, 69-84, 2003. [ps]

I haven't personally presented the following yet, but I believe they can also work well:
  • The DVD that breaks your cipher
    Time/memory tradeoffs.
  • Visual cryptography 
    • Moni Naor, Adi Shamir, Visual cryptography, proc. Crypto ’94, LNCS 950, 1–12, Springer-Verlag, 1995. [ps]
    • In Moni Naor's puzzles web site [web]
  • Playing poker over the phone
    Mental poker (continuing the above theme of multiparty computation).
    • Adi Shamir, Ronald L. Rivest, Leonard M. Adleman, Mental poker, The Mathematical Gardner, 37-43, Prindle, Weber, and Schmidt, 1981. [pdf]
  • Playing card games against yourself
    Discreet solitary games (continuing the above theme of computation using cards).
    • Claude Crépeau, Joe Kilian, Discreet solitary games, proc. Crypto ’93, LNCS 773, 319–330, Springer-Verlag, 1994. [springer](non-free)
  • Comparing information without leaking it
    (Continuing the above theme of multiparty computation.)
    • Ronald Fagin, Moni Naor, Peter Wrinkler, Comparing information without leaking it, Communications of the ACM, vol. 39 no. 5, 77–85, 1996 [ps]
    • In Moni Naor's puzzles web site [web]
  • Computing with scrambled circuits
    Secure two-party computation using Yao's scrambled circuits (continuing the above theme of multiparty computation).
    • Yehuda Lindell, Benny Pinkas, A proof of Yao's protocol for secure two-party computation, ECCC TR04-063, 2004. [web]
  • Are code hiding and digital right management fundamentally possible?
    The (im)possibility of program obfuscation.
    • Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang, On the (im)possibility of program obfuscation, proc. Crypto '01, LNCS 2139, 1–18, Springer-Verlag, 2001. [ps] [ppt] [web]
  • How to make spammers pay
    Fighting spam using hash-cash and memory-bound proofs of work.
    • Cynthia Dwork, Moni Naor, Pricing via processing or combatting junk mail, proc. Crypto '92, LNCS 740, 139–147, Springer, 1992 [ps] [web]
    • Martín Abadi, Mike Burrows, Mark Manasse, Ted Wobber, Moderately hard, memory bound functions. proc. Annual Network and Distributed System Security Symposium, 2003 [pdf]
  • Breaking repeated encryption
    Slide attacks on block ciphers with arbitrary number of rounds.
    • Alex Biryukov, David Wagner, Slide attacks, proc. International Workshop on Fast Software Encryption, LNCS 1636, 245-259, Springer-Verlag, 1999. [ps]

Other educational resources in cryptography:

  • CrypTool
    CrypTool is an interactive "cryptographic laboratory", developed as an open-source project initiated by Deutsche Bank. It offers visualization of concepts and data in many fundamental cryptographic objects and methods, including: popular encryption algorithms and protocols, several cryptanalysis methods (from breaking Vigenère ciphers to lattice attacks on RSA), side-channel attacks and random-number generators. See its screenshots for some examples.
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.