• Instructor(s):

  • Logistics:

  • Class timing: Monday and Wednesday, 8:00 am - 9:30 am
  • Venue: CSA 252

  • Course Description (2nd half) :

The second half of the course aims to cover the following topics in Cryptography: Private Key Encryptions (Semantic Security, Indistinguishability based Security, CPA, CCA Security, PRG and PRF based Constructions, Block Cipher Mode of Operations), Message Authentication Codes (Domain Extension, CBC-MAC, Authenticated Encryptions), Hash Functions (Collision Resistance, Second pre-image Resistance and Pre-image Resistance; Domain Extension: the Merkle-Damgard Transform, Hash-and-MAC), Key Agreement (Diffie-Hellman Key Exchange), Public Key Encryptions (CPA, CCA Security, El-Gamal, Cramer-Shoup Cryptosystem, KEM/DEM Paradigm and Hybrid Encryption), Digital Signatures, Digital Certificates, TLS.

  • Grading:

The course is shared between two instructors and I will be teaching the second half that has 50% weightage which is distributed as follows:

  • Scribe ( 5% ): Every student must scribe at least one lecture. The scribe submission deadline is one week after the class; e.g. a scribe for a lecture on 10th must be submitted by the midnight of 17th.The template tex file for a scribe can be downloaded from here. As you have guessed, the submission must be in Latex. To get first-hand ideas about how to scribe, please have a look at some examples from here.
  • Two Assignment Evaluations (10% each): A small set of problems will be posted below after every class or after the completion of a topic. We will have two assignment evaluations based on these questions: one after three weeks based on the question posted until then and the other at the end of the course based on the questions posted post first assignment evaluation. In an assignment evaluation, you (possibly with a partner) will be asked to explain on the board a randomly chosen question. You are also required to submit the corresponding answer in LateX. The template tex file for assignment can be downloaded from here.
  • "Chalk & Talk" Session (10%): The goal of this session is to cover breadth of the course. The class will be divided into groups of two students. Each group has to make a single presentation overall. We will have two sessions every week (Friday 8:00 am - 9:30 am), each lasting for 45-60 minutes depending on the presetation material. A written report must also be submitted a day before the presentation.The template tex file for chalk/talk can be downloaded from here. You are expected to select your CT partner by 04.03.15 (Wednesday). If no group wants to volunteer a session sponteniously, a rondom group will be selected in the class.
  • Final Exam ( 15% ): Term Papers for final exam.
    1. P1: (Strong) PRP from PRG + Non-trivial Private Key Implies One-way Functions; Ref [KL Chapter 7; find the complete proof for PRG-> strong PRP from other source]-- Monday 8:30 - 10 am
    2. P2: Message Authentication Revisited; Ref. [pdf]-- Monday 10-11:30am
    3. P3: MAC and Authentication Protocols from LPN assumption; Ref. [pdf]-- Tuesday 8:30-10am
    4. P4: Bit CCA secure PKE implies existence of many-bit CCA secure PKE; Ref. [pdf]-- Tuesday 10 - 11:30am
    5. P5: Selective Opening Attack Secure Encryption Schemes; Ref. [pdf] -- Tuesday 2:00 - 3:30pm
    6. P6: Security analysis of Diffie-Hellman Integrated Encryption Scheme in Standard Model; Ref. [pdf]-- Wednesday 8:30 - 10 am
    7. P7: Paillier Encryption Scheme ; Ref. [KL Chapter 13]-- Wednesady 10 - 11:30 am

  • Reading Material and References (2nd half):

Reference Books:

  • Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, second edition 2014, CRC Press. You should definitely have a copy of this book. We will mostly follow this book.
  • Cryptography: Theory and Practice by Douglas Stinson, Third edition, CRC Press.
  • Handbook of Applied Cryptography by Alfred Menezes, Paul Oorschot and Scott Vanstone. Available Online .
  • Foundations of Cryptography by Oded Goldreich. Available Online .
  • Cryptography, An Introduction by Nigel Smart. Available Online .
Some useful Course Notes/Lectures:

  • 1st Half of the course:

  • Taught by Dr. Bhavana Kanukurthi. Link to the first half of the course is here

  • Other Info:

  • Office Hours: Monday Wednsday 9:30 am - 10:00 am or by appointment
  • First Assignment Evaluation: Part I: 8:40 - 11:40 am; 20th March (Friday)
  • First Assignment Evaluation: Part II 3:30 - 4:30 pm; 25th March (Wednesday @ 117)
  • First Assignment Evaluation: All the written reports must be submitted on or before 5th April
  • Second Assignment Evaluation 8:00 - 10:30 am; 10th April
  • All the written reports (assignments/ChalkTalk Reports/Scribes) must be submitted on or before 15th April
  • Final Evaluation: Each group of three people has to make a one and half hour presentation on the assigned paper. Monday (13th; 8:30-10 (P1) / 10-11:30 (P2)) - Three presentations, Tuesday (14th; 8:30-10 (P3) / 10-11:30 (P4) / 2 - 3:30 (P5))- three presentations, Wednesday (15th; 8:30-10 (P6) / 10-11:30 (P7)) - two presentations.

Lecture Details

Will be updated as and when the course progresses.

Lecture # and Date
Lecture contents
Slides / Reading material (KL: Katz-Lindell 2nd Edition)
Scribe (unedited)
Problem Set (KL: Katz-Lindell 2nd Edition)
Lecture 1 (02-03-2015) Introduction, How to define security of SKE: Threat & Break modeling. Computational Security (asymptotic & concrete approach), Ciphertext-only (co) attack, Semantic Security, Indistinguishability based definition. Slides [ppt, pdf] /KL pp. 16-23, 43-63 Arshed [pdf,Sample tex]
Lecture 2 (04-03-2015) Proof by Reduction, PRG-based Construction, Security Proof, Extension to Multi-message security, Non-equivalence of Single-message and multi-message security; Slides [ppt, pdf] /KL pp. 65-72/ Sabareesh [pdf] KL 3.2, 3.4
(Extra) Lecture 3 (06-03-2015) CPA Security, PRF based scheme, Proof of Security of PRF-based construction, Multi Message CPA security, Modes of operations (ECB, CBC, OFB,CTR) Slides [ppt, pdf] /KL pp. 73-95 Mayank [pdf], Ajith [pdf] KL 3.11, 3.18(CPA security part), 3.20, 3.26(c), 3.26(d), 3.29
Lecture 4 (09-03-2015) CCA Security, Padding Oracle Attack, Introduction to MAC Slides [ppt,pdf] /KL pp. 96-100, 107-116 Cressida [pdf], Marilyn [pdf]
Lecture 5 (11-03-2015) Domain Extension (Goldreich Construction), Proof of Security, Authenticated Encryption. Slides [ppt, pdf] /KL pp. 116-123, 131-132 Pankaj [Due], Abdullah [pdf] KL 4.2, 4.6, 4.7, 4.11, 4.12, Construct a CMA-secure MAC from Weak PRF.
Lecture 6 (16-03-2015) Various Definitions of AE, AE implies CCA-security Proof. Paradigms for building AE: (Encrypt-and-Authenticate, Authenticate-then-encrypt, Encrypt-then-authenticate) Slides [ppt, pdf] /KL pp. 131-141 (notice that we had considered a stronger definition for AE than the one given in KL) Shreyas [pdf] KL 4.25 (Note: the def of AE is according to KL (and weaker than what we pursued in the class)), 4.26
Lecture 7 (18-03-2015) Hash Functions, Various Notions of Security & Relation among them, Merkle-Damgaard Transform, Hash from Ideal Cipher, Hash-and-Mac Paradigm, Intro to Key Agreement, Intro to Modular Arithmetic Slides [ppt, pdf] / KL 153-161,182, For the relations among the security notions and advanced reading refer to [this] Rohit [pdf], Madhusudan 5.1 part 2 for a hash function that maps 2n bits string to n bit string, 5.5
Lecture 8 (23-03-2015) Finite cyclic Groups of prime orders, DL, CDH, DDH Assumptions, Diffie-Hellman Key Exchange, Security of Key Exchange. Intro to PKE. Slides [ppt, pdf] / KL 287-297,316-323, 359-373. Kuljeet [pdf], Pradeep KL 13.15
Lecture 9 (25-03-2015) CPA Security, El-Gamal PKE, Single-Message CPA implies Multi-message CPA- Proof using Hybrid arguments, Slides [ppt, pdf] / KL 389-399,405-404, 387-89 Bharath [pdf], Sudhir KL 11.4, 11.6, 11.7, 11.8
Lecture 10 (30-03-2015) Key Encapsulation Mechanism (KEM), Data encapsulation Mechanism (DEM), CPA-secure KEM + COA-secure SKE => CPA-secure PKE (this result implies we can construct PKE almost with the same overhead of COA-secure SKE); CPA KEM from HDH assumption, CCA Security. CCA simple message security implies CCA multi-message security; CCA KEM,CCA KEM + CCA SKE => CCA (Hybrid) PKE. Slides [ppt, pdf] / KL 375-386,400-404. Divya [pdf], Pradeep [pdf] KL 11.10
Lecture 11 (06-04-2015) CCA KEM from ODH Assumption, Diffe-Hellman Integrated Encryption Scheme (DHIES); Cramer-Shoup Cryptosystem Slides [ppt, pdf] / Original Paper: pdf Dheeraj [pdf], Nithin [pdf] Quesions: [here]
Lecture 12 (08-04-2015) Digital Signature, Certificates, TLS, Concluding Remarks Slides [ppt, pdf] Niranjan [pdf]

"Chalk & Talk" Session

Group #: members
Date and Time
Reading material
Submitted Reports
Group 1: Arshed 13.03.15; 08:00 - 8:45 am Equivalence of Semantic Security and IND Security [pdf]
Group 2: Sabareesh & Divya 13.03.15; 08:45 - 9:30 am CPA-security of CTR Mode of Operation KL pp. 92-94 [pdf]
Group 3: Bharath & Kuljeet 20.03.15; 08:00 - 8:50 am CBC-MAC KL pp. 123-130 [pdf]
Group 4: Madhusudan & Pradeep 28.03.15; 02:00 - 2:45 pm Information-theoretic MACs KL pp. 142-146 [pdf]
Group 5: Shreyas & Sudhir 28.03.15; 02:50 - 3:35 pm Davies-Meyer Proof for Ideal Cipher + Time/Space Trade-off Attack on Hash Functions KL pp. 168-173, 233 [pdf], [pdf]
Group 6: Pradeep & Rohit 28.03.15; 03:40 - 4:25 pm Algorithms for Computing Discrete Log (Pohlig-Hellman + Baby-step Giant-step + Hash function based Discrete log computation) KL 348-356 [pdf]
Group 7: Nithin & Dheeraj 01.04.15; 08:50 - 9:35 am Goldwasser-Micali Cryptosystem KL pp. 507-518 [pdf]
Group 8: Mayank & Ajith 01.04.15; 08:00 - 8:45 am Miller-Rabin Primality Testing KL pp. 304-311 [pdf]
Group 9: Niranjan & Jay 09.04.15; 09:15 - 10:00 am Algorithms for Factoring (Pollard's p-1 algorithm, Pollard's Rho Algorithm, Quadratic Sieve Algorithm) KL 342-348 [pdf]
Group 10: Abdullah & Pankaj 09.04.15; 10:00 - 010:45 am RSA Cryptosystem (Plain RSA, Attacks on Plain RSA, CPA-secure RSA based RSA hard-core predicate) KL 312, 410-414, 417-419 [pdf]
Group 11: Cressida & Marylin 09.04.15; 8:30 - 09:15 am Rabin Cryptosystem KL 518-528 [pdf]