Exams:

Announcements

• See older courses an idea about this course.
• Required textbook: Introduction to Cryptography with Coding Theory, Trappe and Washington.
• Suggested textbook: Lecture Notes onf Cryptography, Goldwasser and Bellare.

Class Notes

• Introduction
• Classical ciphers
  • Substitution
    • Nova program challenge
    • Borodkin link and others
    • Borodkin breaker
  • Vignere (example programs)
  • Playfair
    • Nova Program Challenge (notes and experiments on machine reconstruction)
    • Stumpel program to machine break cipher. (cached)
  • Transposition
  • Enigma
    • Enigma description
    • Breaking Enigma
    • Cycle structure of P_iP_i+1 for a simple 6 letter enigma.
  • Tunny and Fish
  • Reference: Helen Gaines
  • Simon Singh Cipher Challenge
• Modern Block and Stream ciphers:
  • Vernum cipher and perfect secrecy.
  • Linear Feedback Shift Register, notes.
  • RC4
  • Attacks on RC4, in Cryptobytes, the RSA newsletter.
  • DES
  • Differential Cryptoanalysis
  • mini-DES (3 round with suppressed permutations)
  • Rijndael
• Modes of operation
  • ECB, CBC, CFB, OFB.
  • Multiple modes, multiple encipherment (3DES and DESX)
  • Authentication codes
• Public Key Cryptography: RSA
  • Randomized computations
  • RSA encryption
  • RSA is as hard as factoring by an RP reduction
  • OAEP
• Public Key Cryptography: Discrete Logs
  • Generators, Discrete Log
  • DL assumption
  • Diffie-Hellman Protocol
  • El Gamal encryption
  • Pohlig-Hellman Algorithm
  • Second-bit security
• Hash functions
  • Definitions
  • Merkel-Damgard construction
  • Chaum-vanHeijst-Pfitzmann
  • SHA-1
• Signatures
  • RSA
  • Elgamal
  • DSA
• Secret Sharing
• Bit commitment/games
• Zero-Knowledge
  • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff. 1985. Original version (PDF)
  • The Knowledge Complexity of Interactive Proof Systems, Goldwasser, Micali and Rackoff. SIAM J. Comput 1989. (PDF)
  • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (PDF)

Homework

• See NOVA program Decoding Nazi Secrets. Solve the Cipher (note: Shockwave plugin required.)
  Send me the signer's name as proof of success.
• Assigned problems from book, chapter 2. Due Monday, 27 Feb.
• Assigned problems from book, chapter 3. All even numbered Exercises, all odd numbered Computer Problems, in first edition.

References

• Enigma, Wladyslaw Kozaczuk. Articles on reconstruction and breaking of Enigma by Polish mathematicians prior to WWII.
• Breaking Tunny by Tutte. Article on reconstructing the masking sequence for encryption of German High Command network.
• John Savard's page on machine ciphers.
• Biham, Eli, Cryptanalysis of multiple modes of operation , J. Cryptology 11:1 (1998) 45-58.
• Biham, Eli, Cryptanalysis of triple modes of operation, J. Cryptology 12:3 (1999) 161-184.
• Cramer, Gennaro, Schoenmakers, A secure and optimally efficient mutli-authority election scheme, Eurocrypt 97.
• Jens Groth, Extracting witnesses from proofs of knowledge in the random oracle model
• Cramer, Damgard, Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocosl, Crypto 94
• Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proc. 20-th ACM Symposium on Theory of Computing, 1988. pp 1-10.
• Pascal Junod, Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator.
• John Milne, Elliptic Curves

Cryptographic Games

• MIT 6.876, Course in Cryptographic Game Theory.
• The Knowledge Complexity of Interactive Proof-Systems (PDF)
• Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems (PDF)
• How To Play Any Mental Game (PDF)
• Equivalence between two flavours of oblivious transfers (PDF)
• Completeness Theoerms for Fault Tolerant Distributed Computing (PDF)
• Parallel Reducibility for Information-Theoretically Secure Computation (PDF)

SliceOfLife

• Helger Lipmaa Notes
• mersenne.org, and Prime network
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)