News!

• Midterm: Wednesday, March 16.
  • histogram
  • Midterm
  • solutions
• Final: Monday, May 2, 2:00-4:30pm.
  • Final

Assignments

• Problem Set 1, Due: Wed Feb 3.
• Problem Set 2, Due: Wed Feb 17.
• Problem Set 3, Due: Wed Mar 2.
• Midterm: Wednesday, March 16.
• Problem Set 4, Due: Wed Apr 6.
• Problem Set 5, Due: Wed Apr 20.
• Final: Monday, May 2.

Syllabus

• Required textbook for both Csc 507 and 609 students:
  Introduction to Modern Cryptography,
  (Chapman & Hall/CRC Cryptography and Network Security Series) 2nd Edition,
  by Jonathan Katz and Yehuda Lindell.
  ((Amazon))
• Twitter (for updates on homework postings): csc609
• class blog
• Additional books of interest:
  • The Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone
  • Introduction to Cryptography with Coding Theory by Trappe and Washington.
  • Codes and Cryptography by Dominic Welsh.
• Homework: Weekly assignments count for 30% of the grade.
• Midterm: The midterm counts for 30% of the grade.
• Final: An in-class final counts for 40% of the grade.
• Grader:

Class Notes

• Encryption, History, and Politics
  • Crypto talk
  • Codes, ciphers and steganography
  • Substitution, transposition, playfair
    • Cracking substitutions
  • Vignere
    • cracking vignere
  • The Enigma
• Perfect Secrecy and Adversarial Indistinguishability.
  • Shannon's theorem for perfect secrecy, probability distribution as "knowledge".
  • One Time Pad and Pseudorandomness
  • Class notes
• Polynomial Time Probabilistic Adversaries and Pseudorandom Generators
  • Review of Models of Computation and Complexity
  • Pseudorandomness
  • Stream Ciphers
• Reductions, and precise security models
  • Eavesdropping Attack Indistinguishability
  • Chosen Plaintest Attack Indistinguishability
  • Multiple message attacks
  • Chosen Ciphertext Attack Indistinguishability
  • Ciphers from PRG, and modes of operation
    • in practice: ECB, CBC, CFB, OFB.
• Integrity and Authenticated Encryption
• Hash functions and signatures
  • cyptographic strength: pre-image, strongly and weakly collision-free
  • Random oracle model
  • Merkle-Damgard construction
  • Merkle trees
  • Commitment Schemes
• Special topic: Bitcoin explained
• Modern Ciphers
  • linear PRNG
  • Trivium, RC4
  • Feistal networks.
  • the Digital Encryption Standard: DES
    • The standard: FIPS 46-3
    • S-Box statistics
  • Differential Cryptanalysis (3 round)
  • Multiple encipherment: 3DES and DESX
    • multiple modes
    • 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.
• Key Agreement
  • Needham Schroeder
  • Introduction to public key: DH key exchange
• Background on Diffie-Hellman and Discrete Logs
  • Euler Phi function, Little Fermat for general n
  • Generators and subgroups
  • Quadratic Residue
    • Bit commitment using Discrete Logs
    • Bit security of discrete logs p-1=2^t s for t>1 (see blog)
    • Legendre Symbol
    • Square roots for primes 3 mod 4 (see blog)
    • Square roots for otherwise (see blog)
  • Pohlig-Hellman and disclosures about small subgroups
• Background on RSA and integer factorization
  • Extended GCD with Python or Ruby
  • The RSA assumption, factoring, and the calculation of Phi(n)
  • RSA and Probabilistic Factoring
  • Fermat test and Carmichael numbers
  • Miller-Rabin test (Kleinberg at Cornell) (cached copy)
• Public Key Systems in practice
  • El Gamal encryption
  • Reduction of El Gamal to DDH
  • KEM/DEM
  • CCA El Gamal KEM in the Random Oracle Model
  • RSA
    • Small message attacks
    • chinese remainder attack on a multiply encrypted message
    • related message attack (m and m + D)
    • root-N trick
  • PKCS #1 v1.5 and the Bleichenbacher attack
  • malleability: self-similarity, average case hardness
  • Chaumian Blind signatures
  • Optimal Asymmetric Encryption Padding (OAEP)
    • M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995. (full version (pdf))
• Eliptic curve cryptography
  • The group law
  • The point at infinity
  • hard problems based on elliptic curves
• Digital Signatures
  • Definition, and adversary
  • Plain RSA signatures and forgeries
  • RSA-FDH (Full Domain Hash) and reduction to the RSA problem
  • Identification schemes, perfect correctness and probabilistic soundness
  • Schnorr identification, and knowledge extraction
  • Fiat-Shamir transformation and Schnorr dig-sig's
  • Sigcryption
• Zero-knowledge Proof Systems
  • Interactive Proof systems
  • Completeness, and soundness
  • Relationship to NP and BPP
  • Graph Non-isomorphism is in IP
  • Zero knowledge, knowledge and information
  • ZK proof for Graph Isomorphism
  • Simulator, role of non-halting for language instances
  • Zero Knowledge proofs of knowledge: modular square root
  • All of NP in Zero Knowledge: 3-colorability
  • References
    • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff.
      • 1985 version (PDF)
      • SIAM J. Comput 1989 version (PDF)
    • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (PDF)
    • How To Play Any Mental Game (PDF)

Writing Credit

• For opt-in writing credit, three 1500 word papers, one at least due by the midterm.
• Suggested topics: books relating to computer security, cryptography, cyperwarfare, cyber-utopianism or cyber-dystopianism;
  • For instance, several books tage Bletchly Park are good historical cryptography books for thie project: The Hut 6 Story, Code Breakers: In inside story of Bletchly Park, Between Silk and Cyanide
  • The American Black Chamber
  • Diamond Age or other cyberpunk, and probably some steampunk, it it is sufficiently focused on the impact of cyberspace and how cryptography is relevant.

Books

• Cryptanalysis by Helen Gaines. Cryptanalysis of classic ciphers.
• Elementary Military Cryptography William F. Friedman.
• Handbook of Applied Cryptography by Oorshot and Vanstone.
• Lecture Notes on Cryptography by Goldwasser and Bellare.
• American Black Chamber, see also Yardley's book
• Enigma, Wladyslaw Kozaczuk. Articles on reconstruction and breaking of Enigma by Polish mathematicians prior to WWII.
• La cryptographie militaire by Auguste Kerckhoffs.
• Steganographia by Johannes Trithemius (1462-1516)

Other resources

• Nova: Decoding Nazi Secrets
• Simon Singh challenge
• Breaking Tunny by Tutte. Article on reconstructing the masking sequence for encryption of German High Command network.
• John Savard's page on machine ciphers.
• Rotonym, what the heck is a rotonym, Will McGugan. A nice Rot-13 implementation in Python.
• Elliptic Curves, John Milne.
• mersenne.org
• Prime network
• Random dot org: a supply of random numbers.
• The NIST Beacon

References

• Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator, Pascal Junod.
• 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.
• Philippe Oechslin, Making a faster cryptanalytic time-memory trade-off, Crypto 03. (cached)
• MIT 6.876, Course in Cryptographic Game Theory.
• Equivalence between two flavours of oblivious transfers (PDF)
• Completeness Theoerms for Fault Tolerant Distributed Computing (PDF)
• Parallel Reducibility for Information-Theoretically Secure Computation (PDF)
• The best known SPRP bases
• Helger Lipmaa Notes
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)