COMP_SCI 396: Introduction to Cryptography

Quarter Offered

Fall : 9:40-11 TuTh ; Wang


(COMP_SCI 212 and COMP_SCI 214) or Graduate (MS or Ph.D) student standing


This course covers the basic knowledge in understanding and using cryptography. The main focus is on definitions, theoretical foundations, and rigorous proofs of security, with some programming practice. Topics include symmetric and public-key encryption, message integrity, hash functions, block-cipher design and analysis, number theory, and digital signatures.


This course is an undergraduate introduction to cryptography, aiming to present the theoretical foundations of cryptosystems used in the real world. In this class, we will look "under the hood" about common cryptographic objects to get a better understanding of various cryptographic primitives, algorithms, attacks, and protocols. 

RECOMMENDED TEXTBOOK: Introduction to Modern Cryptography, 2nd edition. Students are strongly advised to obtain a physical copy of the book since exams will be "open book" with no electronic devices permitted. Assignments will be picked from this book.

Prerequisites. No advanced mathematics background is assumed, but students are expected to have "mathematical maturity" since many of the concepts will be abstract, rigorous definitions and proofs will be given, and some new mathematics (e.g., group theory, number theory) will be introduced. Basic background in discrete mathematics (probability, modular arithmetic) and a basic background in algorithms (big-O notation and worst-case analysis, reading pseudocode) is assumed.


Symmetric-key Cryptography.
- The syntax of private-key encryption. The classical ciphers. Elementary cryptanalysis and frequency analysis.  
- Perfect secrecy. The one-time pad.
- A computational notion of security. Pseudorandomness and pseudorandom generators. The pseudo-OTP. 
- Proofs by reduction, and a proof of security for the pseudo-OTP. Pseudorandom functions, Pseudorandom permutations and block ciphers.

- Security for multiple encryptions.  CPA-security from pseudorandom functions. 
- Block-cipher and stream-cipher modes of operation.
- Chosen-ciphertext attacks and CCA-security. 
- Defining security for MACs. A fixed-length MAC. MACs for arbitrary-length messages. CBC-MAC and HMAC. 
- Padding-oracle attacks. Authenticated encryption and generic constructions. 
- Hash functions and collision resistance. Birthday attacks on hash functions. The Merkle-Damgard transform. Hash functions as random oracles. Additional applications of hash functions.

Public-key Cryptography.
Group theory.
- The discrete-logarithm assumption and the Diffie-Hellman assumption.
- Diffie-Hellman key-exchange protocol. 
- El-Gamal encryption. 
- Hybrid encryption and the KEM/DEM paradigm. 
- Digital signatures.
- The hash-and-sign paradigm. 
- Certificates and public-key infrastructures.

Prof. Wang