CSA E0 235 : Cryptography (October 2020 - January 2021)

Instructors: Arpita Patra (Email: arpita AT iisc DOT ac DOT in) and Chaya Ganesh (Email: chaya AT iisc DOT ac DOT in)
Timings: 3:30 pm - 5:00 pm on Tuesday and Thursday.
Venue: Microsoft Teams

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), Hard-core Predicates, Pseudo-random Generators, (Strong) Pseudo-random 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, CBC-MAC.
  • Advanced Encryption Schemes: Authenticated Encryptions.
  • Introduction to Secure Computation (Yao's 2PC protocol and Circuit Garbling).
  • Course Description (2nd Half)
  • Number Theory: Preliminaries, Modular arithmetic, elementary group theory, CRT, hardness assumptions.
  • Trapdoor permutations: definitions, construction based on factoring, CR Hash functions based on number-theoretic assumptions.
  • Public-key encryption: Implications of Semantic Security, Textbook RSA, Padded RSA, ElGamal, CCA secure public key encryption.
  • Digital signatures: definitions, hash-and-sign paradigm, Lamport’s scheme, RSA signatures.
  • Protocols: Identification protocols, proving properties in zero knowledge, non-interactive proof systems and applications.
  • Grading (1st Half)
  • Bi weekly test (5*4 = 20 Credits)
  • Assignment (15*2 = 30 Credits)
  • Announcements
  • The fourth quiz will be held on Thursday, 26th November 2020, 4:00 pm - 5:00 pm via Microsoft Forms.
  • Webpage for the second half of the course can be found here: [Link]
  • Latex template for assignments can be found here: [Template]
  • Tutorial sessions will be held on every Friday, 2:00 pm - 3:00 pm on Microsoft Teams. [Meeting Link]
  • Online doubt clearing sessions will be held on every Tuesday and Thursday, 3:30 pm - 5:00 pm on Microsoft Teams. [Meeting Link]
  • Academic Integrity

  • Improper academic behaviour: Copying during exams, copying of homework assignments, term papers or manuscripts, verbatim or paraphrased. Allowing or facilitating copying, or writing a report or exam for someone else. Using unauthorized material and collaborating when not authorized. [Details]
  • Action: In the case of a violation of the academic integrity, the student's ID will be reported to the Office of Career Counselling and Placement (OCCaP).

    • Lecture 0 :  Introductory Lecture.
    • References : [Slides]
    • Date : 06-10-2020
    • 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 : [Slides], [Video], Chapter 1 of KL
    • Date : 08-10-2020
    • Lecture 2 :  Perfect Security: Definition, Construction (Vernam Cipher), Proof; Drawbacks of OTP
    • References : [Slides], [Video], Chapter 2 of KL and BS
    • Date : 13-10-2020
    • Lecture 3 :  More definitions of Perfect Security and their equivalence with Shannon's perfect security definition. Shannon's Theorem. Perfect Indistinguishability-- game-based definition. Proof of limitations on key space/length and key reusability. Relaxing perfect security. Introduction to Computational Security.
    • References : [Slides], [Video], Chapter 2 of KL and BS
    • Date : 15-10-2020
    • Errata : The slide on "inherent limitation of key reusability" has the posteriori probability written wrongly in the video. It has been corrected in the slides later and the slides posted here contain the correct version.
    • 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 Reduction-based proofs and the proof of 'ind-security implies parity-prediction security'. Necessity of the relaxations in threat and break models to overcome the hurdles of perfect secrecy.
    • References : [Slides], [Video], Chapter 2 of KL
    • Date : 20-10-2020
    • Lecture 5 :   Pseudorandomness and Pseudo-random Generators (PRG), Indistinguishability Security, Next-bit Prediction Security, Statistical Tests, Impossibility of PRG against unbounded adversary, ind-secure SKE from PRG, Proof of security, Applications of ind-secure SKE-- Roulette and Anonymous Message Transfer/Onion Routing
    • References : [Slides], [Video], Chapter 3 of KL and BS
    • Date : 22-10-2020
    • Supplementary Lecture 1 :   Stream ciphers. Linear feedback shift registers (LFSR), Reconstruction attack, Non-linear FSR, Trivium
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 24-10-2020
    • Lecture 6 :   Hybrid Arguments, PRG with one-bit expansion implies PRG with many-bit expansion, Applications of PRG-- Coin-tossing and Commitment Schemes
    • References : [Slides], [Video], Chapter 3 of KL and BS
    • Date : 27-10-2020
    • Lecture 7 :   Chosen Plaintext Attack (CPA), CPA-security, Pseudo-random Functions (PRF), PRP
    • References : [Slides], [Video], Chapter 3 of KL and 4 of BS
    • Date : 29-10-2020
    • Supplementary Lecture 2 :   Block ciphers 1. Confusion-diffusion paradigm, Implementation of Confusion-Diffusion paradigm via substitution-permutation network (SPN), Avalanche effect, Attacking reduced round SPNs, Feistel network
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 29-10-2020
    • Supplementary Lecture 3 :   Block ciphers 2. Design of Data Encryption Standard (DES), DES round function, Strengthening the security of DES using a larger key - internal modifications v/s black-box constructions, Advanced Encryption Standard (AES), Overview of AES construction.
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 29-10-2020
    • Lectures 8-9 :   SKE based on PRF, Proof for CPA-security, PRG implies PRF-- GGM/tree construction
    • References : [Slides], [Video], Chapter 7 of KL and 4 of BS
    • Date : 03-11-2020
    • Lecture 10 :   Yao's 2PC, Circuit Garbling as an application of CPA-secure SKE
    • References : [Slides], [Video], 'A Proof of Yao's Protocol for Secure Two-Party Computation' by Yehuda Lindell and Benny Pinkas (available online)
    • Date : 10-11-2020
    • Lecture 11 :   CCA-security, Practical break of CBC-mode CPA-secure SKE, Break of CPA-secure SKE based on PRF, Authenticated Encryption (AE), AE implies CCA-security.
    • References : [Slides], [Video], Chapter 2 and 4 of KL and 9 of BS
    • Date : 12-11-2020
    • Lecture 12 :   MAC- cma and strong cma security, PRF based construction, domain extension; One-time Information-theoretic MAC- Definition, Pairwise Indepedent Functions, Carter-Wegman MAC
    • References : [Slides], [Video], Chapter 3 of KL and 7 of BS
    • Date : 17-11-2020
    • Lecture 13 :   Autheticated Encryption from cpa-secure SKE and strong cma-secure MAC; Encrypt and Autheticate, Autheticate then Encrypt, Encrypt then Autheticate Paradigms, Proof of security for Encrypt then Autheticate Paradigm; Looking back and Ahead; One-way Functions.
    • References : [Slides], [Video], Chapter 7 of KL
    • Date : 19-11-2020
    • Lecture 14 :   OWF, OWP, Hard-core Predicates, Partial proof of Goldreich-Levin, OWP + Hardcore predicates imply PRG with one bit expansion.
    • References : [Slides], [Video], Chapter 7 KL
    • Date : 24-11-2020
    • Lecture 15 :   (Partial) proof of Goldreich-Levin, Hash Functions, Collision Resistance, Applications, Merkle Tree .
    • References : [Slides], [Video], Chapter 7 and 5 KL
    • Date : 26-11-2020
    • Lecture 0 :  Introductory Lecture.
    • References : [Slides]
    • Date : 06-10-2020
    • 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 : [Slides], [Video], Chapter 1 of KL
    • Date : 08-10-2020
    • Lecture 2 :  Perfect Security: Definition, Construction (Vernam Cipher), Proof; Drawbacks of OTP
    • References : [Slides], [Video], Chapter 2 of KL and BS
    • Date : 13-10-2020
    • Lecture 3 :  More definitions of Perfect Security and their equivalence with Shannon's perfect security definition. Shannon's Theorem. Perfect Indistinguishability-- game-based definition. Proof of limitations on key space/length and key reusability. Relaxing perfect security. Introduction to Computational Security.
    • References : [Slides], [Video], Chapter 2 of KL and BS
    • Date : 15-10-2020
    • Errata : The slide on "inherent limitation of key reusability" has the posteriori probability written wrongly. It has been corrected in the slides latter and the slides posted here contain the correct version.
    • 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 Reduction-based proofs and the proof of 'ind-security implies parity-prediction security'. Necessity of the relaxations in threat and break models to overcome the hurdles of perfect secrecy.
    • References : [Slides], [Video], Chapter 2 of KL
    • Date : 20-10-2020
    • Lecture 5 :   Pseudorandomness and Pseudo-random Generators (PRG), Indistinguishability Security, Next-bit Prediction Security, Statistical Tests, Impossibility of PRG against unbounded adversary, ind-secure SKE from PRG, Proof of security, Applications of ind-secure SKE-- Roulette and Anonymous Message Transfer/Onion Routing
    • References : [Slides], [Video], Chapter 3 of KL and BS
    • Date : 22-10-2020
    • Supplementary Lecture 1 :   Stream ciphers. Linear feedback shift registers (LFSR), Reconstruction attack, Non-linear FSR, Trivium
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 24-10-2020
    • Lecture 6 :   Hybrid Arguments, PRG with one-bit expansion implies PRG with many-bit expansion, Applications of PRG-- Coin-tossing and Commitment Schemes
    • References : [Slides], [Video], Chapter 3 of KL and BS
    • Date : 27-10-2020
    • Lecture 7 :   Chosen Plaintext Attack (CPA), CPA-security, Pseudo-random Functions (PRF), PRP
    • References : [Slides], [Video], Chapter 3 of KL and 4 of BS
    • Date : 29-10-2020
    • Supplementary Lecture 2 :   Block ciphers 1. Confusion-diffusion paradigm, Implementation of Confusion-Diffusion paradigm via substitution-permutation network (SPN), Avalanche effect, Attacking reduced round SPNs, Feistel network
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 29-10-2020
    • Supplementary Lecture 3 :   Block ciphers 2. Design of Data Encryption Standard (DES), DES round function, Strengthening the security of DES using a larger key - internal modifications v/s black-box constructions, Advanced Encryption Standard (AES), Overview of AES construction.
    • References : [Slides], [Video], [NPTEL-FOC], Chapter 6 of KL
    • Date : 29-10-2020
    • Lectures 8-9 :   SKE based on PRF, Proof for CPA-security, PRG implies PRF-- GGM/tree construction
    • References : [Slides], [Video], Chapter 7 of KL and 4 of BS
    • Date : 03-11-2020
    • Lecture 10 :   Yao's 2PC, Circuit Garbling as an application of CPA-secure SKE
    • References : [Slides], [Video], 'A Proof of Yao's Protocol for Secure Two-Party Computation' by Yehuda Lindell and Benny Pinkas (available online)
    • Date : 10-11-2020
    • Lecture 11 :   CCA-security, Practical break of CBC-mode CPA-secure SKE, Break of CPA-secure SKE based on PRF, Authenticated Encryption (AE), AE implies CCA-security.
    • References : [Slides], [Video], Chapter 2 and 4 of KL and 9 of BS
    • Date : 12-11-2020
    • Lecture 12 :   MAC- cma and strong cma security, PRF based construction, domain extension; One-time Information-theoretic MAC- Definition, Pairwise Indepedent Functions, Carter-Wegman MAC
    • References : [Slides], [Video], Chapter 3 of KL and 7 of BS
    • Date : 17-11-2020
    • Lecture 13 :   Autheticated Encryption from cpa-secure SKE and strong cma-secure MAC; Encrypt and Autheticate, Autheticate then Encrypt, Encrypt then Autheticate Paradigms, Proof of security for Encrypt then Autheticate Paradigm; Looking back and Ahead; One-way Functions.
    • References : [Slides], [Video], Chapter 7 of KL
    • Date : 19-11-2020
    • Lecture 14 :   OWF, OWP, Hard-core Predicates, Partial proof of Goldreich-Levin, OWP + Hardcore predicates imply PRG with one bit expansion.
    • References : [Slides], [Video], Chapter 7 KL
    • Date : 24-11-2020
    • Lecture 15 :   (Partial) proof of Goldreich-Levin, Hash Functions, Collision Resistance, Applications, Merkle Tree .
    • References : [Slides], [Video], Chapter 7 and 5 KL
    • Date : 26-11-2020