CPSC 601.48 - Foundations of Modern Cryptography

Winter 2010

Time and place Tue and Thu, 9:30-10:45am, SS 115
Instructor
Payman Mohassel
Email: pmohasse at ucalgary dot ca      Office: ICT 642
Office hours: Tue and Wed 11-12pm
Grading Homeworks: 40%
Course Project: 60%
References Books, lecture notes, and reading list




Course Description

Studying the fundamental concepts and primitives in modern cryptography, and the relations and reductions among them. The course is focused on general concepts with great emphasis on rigorous definitions and proofs of security. Examples of topics to be covered include one-way and trapdoor functions, pseudorandom generators/functions/permutations, private, public, and identity-based encryption schemes, signature schemes, hash functions, random oracle model, commitment schemes, zero-knowledge proofs, and secure multiparty computation.



Course schedule


Jan 12. Introduction. Course information and some background. HW1 is available!
Lecture 1
Jan 14-19. Private key encryption. Security definitions for encryption schemes; block-ciphers as PRFs; PRF/PRP switching lemma; security of modes of encryption e.g. CTR, CBC, OFB, ... Lecture 2
Lecture 3
Jan 21. Message Authentication Codes. Security definitions for MACs; CBC-MAC, XCBC, CMAC modes of operations Lecture 4
Jan 26. IND-CCA encryption, Authenticated encryption.Unpredictable permutations and MACs; IND-CCA encryption, security definitions for authenticated encryption, security of "Encrypt and Mac", "Encrypt then Mac", "Mac then Encrypt"; OCB and CCM modesLecture 5
Jan 28. Hash functions. Collision resistance; MACs based on CRHFs (e.g. HMAC and NMAC); other notions for hash functions, number theoretic constructions. Lecture 6
Feb 2-4. General assumptions. One-way functions/permutations, PRGs from OWPs, PRFs from PRGs; number theoretic constructions. HW2 is available!
Project Proposal due Feb 4
HW1 due Feb 4
Lecture 7
Lecture 8
Feb 9-11. IND-CPA public-key encryption. RSA, DLog, CDH, DDH assumptions, El Gamal, construction based on trapdoor functions. Lecture 9
Lecture 10
Feb 16-18. No lecture (Reading Week!)
Feb 23-25. IND-CPA PKE and Digital signature schemes Quadratic Residuosity Assumption, Goldwasser-Micali encryption, Rabin's trapdoor function. Unforgeability against CMA, Lamport's on-time signatures, signatures based on collision-resistant hash functions.HW2 due Feb 25.
Lecture 11
Lecture 12
Mar 2-4. Random oracle model Guest lectures by Martin Gagne
Definitions, CCA-secure encryption in the RO model; Full Domain Hash and tighter bounds via random self-reducibility; Shortcomings of the RO model.		Lecture 13
HW3 is available!
Lecture 14
Mar 9-11. Identity-based encryption Guest Lectures by Kris Narayan
Bilinear Pairing, hardness assumption in bilinear groups; Security definitions for IBE schemes; Boneh-Franklin IBE scheme, and its security.		Lecture 15,16
Mar 16-18. More on Encryption Schemes Hybrid Encryption; KEM/DEM paradigm and proofs of security; IND-CCA PKE, and PK signatures from IBE; IB signatures from PK signaturesLecture 17
Lecture 18
Mar 23. Commitment Schemes. Security definitions for commitments schemes. Commitments from Encryption, PRGs, OWPs, hash functions, and number-theoretic assumptions. Lecture 19
Mar 25 Private Information Retrieval HW3 due Mar 21.
Lecture 20
Mar 30-Apr8. In Class Presentations. Final report due Apr 16