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.
you know nothing
Differential fault-analysis of unknown ciphers using asymmetric bit
- 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,
- 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
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).
Zero-knowledge explained via an "Ali Baba and a magical cave" metaphor:
- Moni Naor, Yael Naor and Omer Reingold, Applied kid cryptography, Journal of Craptology, vol. 0 no. 1, 1999. [ps] [web]
- 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
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,
- 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
- 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.
poker, The Mathematical
Gardner, 37-43, Prindle, Weber,
and Schmidt, 1981. [pdf]
- Playing card games against yourself
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]
without leaking it
(Continuing the above theme of
- 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
- 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]
- 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
proc. International Workshop on Fast Software Encryption, LNCS 1636,
Springer-Verlag, 1999. [ps]
Other educational resources in cryptography:
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.
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.