CSC507/609-H: Cryptography
Prof. B. Rosenberg
Spring Semester, 2016 (162)
MW 3:35 PM – 4:50 PM
Whitten LC 120
News!
- Midterm: Wednesday, March 16.
- Final: Monday, May 2, 2:00-4:30pm.
Assignments
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:
- 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
- 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
- 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
- Differential Cryptanalysis (3 round)
- Multiple encipherment: 3DES and DESX
- 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
- Pohlig-Hellman and disclosures about small subgroups
- Background on RSA and integer factorization
- 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.
- 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
Other resources
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.)