CSA E0 235 : Cryptography (August  December 2019)
Instructor : Arpita Patra (Email: arpita AT iisc DOT ac DOT in )
Timings : 3:30 pm  5:00 pm on Monday and Wednesday.
Venue: CSA 252
Study Material
(KL) "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, second edition 2014, CRC Press.
"Foundations of Cryptography" by Oded Goldreich.
"A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup. [Link]
Course Description (1st Half)
One way Functions (Permutations), Hardcore Predicates, Pseudorandom Generators, (Strong) Pseudorandom Functions (Permutations).
Secret Key Encryptions (SKE): Various security notions such as Perfect Security, Semantic Security, Indistinguishability based Security, CPA Security, CCA Security, Constructions, Block Cipher Mode of Operations.
Message Authentication Codes (MAC): Various Security notions such as CMA Security, (weak/strong) CMVA security, Domain Extension, CBCMAC.
Advanced Encryption Schemes: Authenticated Encryptions.
Introduction to Secure Computation (Yao's 2PC protocol and Circuit Garbling).
Grading
Scribe (5 Credits) : Every student must scribe at least one lecture. The scribe submission deadline is one week after the corresponding lecture. The template tex file for a scribe can be downloaded from here [Link] . The submission must be in Latex.
Bi weekly test (5*3 = 15 Credits)
Midterm Exam (30 Credits)
Announcements
Midterm Exam (30 Credits) : 06102019, 09:00  12:00, CSA 254
 Lecture 1 : Introduction, Classical Crypto vs. Modern Crypto, Three Pillars of Modern crypto (definition + assumption + proof), Classical ciphers and pitfalls. Inroad towards Modern Crypto.
 References : [PDF], Chapter 1 of KL
 Problem Set : KL Chapter 1 Questions
 Date : 05082019

 Lecture 2 : Perfect Security: Definition, Construction (Vernam Cipher), Proof; Drawbacks of OTP
 References : [PDF], Chapter 2 of KL and BS, [Scribe]
 Problem Set : 
 Date : 07082019

 Lecture 3 : More definitions of Perfect Security and their equivalence with Shannon's perfect security definition. Shannon's Theorem. Perfect Indistinguishability gamebased definition. Proof of limitations on key space/length and key reusability. Relaxing perfect security. Introduction to Computational Security.
 References : [PDF], Chapter 2 of KL and BS, [Scribe]
 Problem Set : Chapter 2 Questions from KL
 Date : 14082019

 Lecture 4 : Introduction to Computational Security. Definitions of PPT and negligible functions, Security Parameter. Asymptotic Approach. Ind(istinguishability) Security and its relation to weaker security notions of Parity Prediction (pr) and Message Recovery (mr). Introduction to Reductionbased proofs and the proof of 'indsecurity implies parityprediction security'. Necessity of the relaxations in threat and break models to overcome the hurdles of perfect secrecy.
 References : [PDF], Chapter 2 of KL and BS, [Scribe]
 Problem Set : Chapter 2 Questions from KL
 Date : 19082019

 Lecture 5 : Pseudorandomness and Pseudorandom Generators (PRG), Indistinguishability Security, Nextbit Prediction Security, Statistical Tests, Impossibility of PRG against unbounded adversary, indsecure SKE from PRG, Proof of security, Applications of indsecure SKE Roulette and Anonymous Message Transfer/Onion Routing
 References : [PDF], Chapter 3 of KL and BS, [Scribe]
 Problem Set : Chapter 3 Questions from KL
 Date : 21082019

 Lecture 6 : Hybrid Arguments, PRG with onebit expansion implies PRG with manybit expansion, Applications of PRG Cointossing and Commitment Schemes
 References : [PDF], Chapter 3 of KL and BS, [Scribe]
 Problem Set : Chapter 3 Questions from KL
 Date : 26082019

 Lecture 7 : Chosen Plaintext Attack (CPA), CPAsecurity, Pseudorandom Functions (PRF), PRP
 References : [PDF], Chapter 3 of KL and 4 of BS, [Scribe]
 Problem Set : Questions from Chapter 3 of KL and 4 of BS
 Date : 28082019

 Lecture 8 : SKE based on PRF, Proof for CPAsecurity, PRG implies PRF GGM/tree construction
 References : [PDF], Chapter 7 of KL and 4 of BS, [Scribe]
 Problem Set : Chapter 7 Questions from KL and 4 from BS
 Date : 04092019

 Lecture 9 : Yao's 2PC, Circuit Garbling as an application of CPAsecure SKE
 References : [PDF], 'A Proof of Yao's Protocol for Secure TwoParty Computation' by Yehuda Lindell and Benny Pinkas, available online, [Scribe]
 Problem Set :
 Date : 09092019

 Lecture 10 : CCAsecurity, Practical break of CBCmode CPAsecure SKE, Break of CPAsecure SKE based on PRF, Authenticated Encryption (AE), AE implies CCAsecurity.
 References : [PDF], Chapter 2 and 4 of KL and 9 of BS, [Scribe]
 Problem Set : Questions from Chapter 2 and 4 of KL and 9 of BS
 Date : 11092019

 Lecture 11 : MAC cma and strong cma security, PRF based construction, domain extension; Onetime Informationtheoretic MAC Definition, Pairwise Indepedent Functions, CarterWegman MAC
 References : [PDF], Chapter 3 of KL and 7 of BS, [Scribe]
 Problem Set : Chapter 3 of KL and 7 of BS
 Date : 16092019

 Lecture 12 : Autheticated Encryption from cpasecure SKE and strong cmasecure MAC; Encrypt and Autheticate, Autheticate then Encrypt, Encrypt then Autheticate Paradigms, Proof of security for Encrypt then Autheticate Paradigm; Looking back and Ahead; Oneway Functions.
 References : [PDF], Chapter 7 of KL, [Scribe]
 Problem Set : Chapter 7 of KL
 Date : 18092019

 Lecture 13 : OWF, OWP, Hardcore Predicates, Partial proof of GoldreichLevin, OWP + Hardcore predicates imply PRG with one bit expansion.
 References : [PDF], Chapter 7 KL, [Scribe]
 Problem Set : Chapter 7 Questions from KL
 Date : 23092019

 Lecture 14 : (Partial) proof of GoldreichLevin, Hash Functions, Collision Resistance, Applications, Merkle Tree .
 References : [PDF], Chapter 7 and 5 KL, [Scribe]
 Problem Set : Chapter 7 and 5 KL
 Date : 25092019

 Lecture 15 : Zeroknowledge Proof System, ZK protocol for Graph Isomorphism, ZK protocol for all NP (3COL).
 References : Chapter 7 of [PDF], [Scribe]
 Problem Set :
 Date : 30092019


 Lecture 1 : Introduction, Classical Crypto vs. Modern Crypto, Three Pillars of Modern crypto (definition + assumption + proof), Classical ciphers and pitfalls. Inroad towards Modern Crypto.
 References : [PDF], Chapter 1 of KL
 Problem Set : KL Chapter 1 Questions
 Date : 05082019

 Lecture 2 : Perfect Security: Definition, Construction (Vernam Cipher), Proof; Drawbacks of OTP
 References : [PDF], Chapter 2 of KL and BS, [Scribe]
 Problem Set : 
 Date : 07082019

 Lecture 3 : More definitions of Perfect Security and their equivalence with Shannon's perfect security definition. Shannon's Theorem. Perfect Indistinguishability gamebased definition. Proof of limitations on key space/length and key reusability. Relaxing perfect security. Introduction to Computational Security.
 References : [PDF], Chapter 2 of KL and BS, [Scribe]
 Problem Set : Chapter 2 Questions from KL
 Date : 14082019

 Lecture 4 : Introduction to Computational Security. Definitions of PPT and negligible functions, Security Parameter. Asymptotic Approach. Ind(istinguishability) Security and its relation to weaker security notions of Parity Prediction (pr) and Message Recovery (mr). Introduction to Reductionbased proofs and the proof of 'indsecurity implies parityprediction security'. Necessity of the relaxations in threat and break models to overcome the hurdles of perfect secrecy.
 References : [PDF], Chapter 2 of KL, [Scribe]
 Problem Set : Chapter 2 Questions from KL
 Date : 19082019

 Lecture 5 : Pseudorandomness and Pseudorandom Generators (PRG), Indistinguishability Security, Nextbit Prediction Security, Statistical Tests, Impossibility of PRG against unbounded adversary, indsecure SKE from PRG, Proof of security, Applications of indsecure SKE Roulette and Anonymous Message Transfer/Onion Routing
 References : [PDF], Chapter 3 of KL and BS, [Scribe]
 Problem Set : Chapter 3 Questions from KL
 Date : 21082019

 Lecture 6 : Hybrid Arguments, PRG with onebit expansion implies PRG with manybit expansion, Applications of PRG Cointossing and Commitment Schemes
 References : [PDF], Chapter 3 of KL and BS, [Scribe]
 Problem Set : Chapter 3 Questions from KL
 Date : 26082019

 Lecture 7 : Chosen Plaintext Attack (CPA), CPAsecurity, Pseudorandom Functions (PRF), PRP
 References : [PDF], Chapter 3 of KL and 4 of BS, [Scribe]
 Problem Set : Questions from Chapter 3 of KL and 4 of BS
 Date : 28082019

 Lecture 8 : SKE based on PRF, Proof for CPAsecurity, PRG implies PRF GGM/tree construction
 References : [PDF], Chapter 7 of KL and 4 of BS, [Scribe]
 Problem Set : Chapter 7 Questions from KL and 4 from BS
 Date : 04092019

 Lecture 9 : Yao's 2PC, Circuit Garbling as an application of CPAsecure SKE
 References : [PDF], 'A Proof of Yao's Protocol for Secure TwoParty Computation' by Yehuda Lindell and Benny Pinkas, available online, [Scribe]
 Problem Set :
 Date : 09092019

 Lecture 10 : CCAsecurity, Practical break of CBCmode CPAsecure SKE, Break of CPAsecure SKE based on PRF, Authenticated Encryption (AE), AE implies CCAsecurity
 References : [PDF], Chapter 2 and 4 of KL and 9 of BS, [Scribe]
 Problem Set : Questions from Chapter 2 and 4 of KL and 9 of BS
 Date : 11092019

 Lecture 11 : MAC cma and strong cma security, PRF based construction, domain extension; Onetime Informationtheoretic MAC Definition, Pairwise Indepedent Functions, CarterWegman MAC
 References : [PDF], Chapter 3 of KL and 7 of BS, [Scribe]
 Problem Set : Chapter 3 of KL and 7 of BS
 Date : 16092019

 Lecture 12 : Autheticated Encryption from cpasecure SKE and strong cmasecure MAC; Encrypt and Autheticate, Autheticate then Encrypt, Encrypt then Autheticate Paradigms, Proof of security for Encrypt then Autheticate Paradigm; Looking back and Ahead; Oneway Functions.
 References : [PDF], Chapter 7 of KL, [Scribe]
 Problem Set : Chapter 7 of KL
 Date : 18092019

 Lecture 13 : OWF, OWP, Hardcore Predicates, Partial proof of GoldreichLevin, OWP + Hardcore predicates imply PRG with one bit expansion
 References : [PDF], Chapter 7 KL, [Scribe]
 Problem Set : Chapter 7 Questions from KL
 Date : 23092019

 Lecture 14 : (Partial) proof of GoldreichLevin, Hash Functions, Collision Resistance, Applications, Merkle Tree
 References : [PDF], Chapter 7 and 5 KL, [Scribe]
 Problem Set : Chapter 7 and 5 KL
 Date : 25092019

 Lecture 15 : Zeroknowledge Proof System, ZK protocol for Graph Isomorphism, ZK protocol for all NP (3COL)
 References : Chapter 7 of [PDF], [Scribe]
 Problem Set :
 Date : 30092019


Tutorial Details
Tutorial 1: 09082019, 18:00  19:00, CSA 252 [PDF]
Tutorial 2: 16082019, 18:00  19:00, CSA 252 [PDF]
Tutorial 3: 27082019, 19:00  20:00, CSA 254 [PDF]
Tutorial 4: 30082019, 09:30  10:30, CSA 252 [PDF]
Tutorial 5: 06092019, 09:30  10:30, CSA 252 [PDF]
Tutorial 6: 13092019, 09:00  10:00, CSA 252 [PDF]
Tutorial 7: 28092019, 09:30  11:00, CSA 252