Introduction To Cryptography (M) [Fall 2024]

Instructor: Sruthi Sekar (sruthi [at] cse [dot] iitb [dot] ac [dot] in)

Course Timing and Location (CS 409M): 9:30-10:55 AM Wed/Fri, CC101

Teaching Assistants: Giriraj Singh, Nilabha Saha, Gyara Pragathi (TA hours in CC101)

Contact Hours: After class, or fix appointment by emailing

Important Dates:

• QUIZ 1 – 21st August 2024, 8:30 AM-9:30 AM, Venue (KR 225, KR 229 (second floor Kresit building (old CSE building)).
• QUIZ 2 – 4th September 2024, 8:30 AM-9:30 AM, Venue (CC103).
• MIDSEM EXAM – 20th September 2024, 4 PM – 6 PM, Venue (CC103).
• QUIZ 3– 18th October 2024, 8:30 AM-9:30 AM, Venue (CC101).
• CHALK AND TALK – 6th September, 11th September, 13th September, 30th Oct-8th Nov during lectures (all remaining reports due on 27th Nov, 11:59 PM)

Course Description (CS 409M)

This course is intended to provide a theoretical foundation in Cryptography. We shall learn about basic cryptographic tools like encryption and message authentication, in the “private-key” and “public-key” settings, with a focus on mathematical definitions of security, “provably secure” constructions based on fundamental cryptographic primitives, and how they are used. The topics that will be covered include the following. We will mainly refer to two books: Katz-Lindell and Boneh-Shoup.

• Perfectly secret encryption: one time pad, limitations of perfect security
• Private key encryption: defining encryption CPA security, constructing CPA secure scheme- pseudorandom functions and block ciphers, pseudorandom generators, stream ciphers, one-way functions, hardcore predicates, CCA security – motivates message authentication codes, some practical constructions.
• Hash Functions and applications: definition of hash functions, message authentication using hash functions, attacks, some additional applications
• Public key encryption: CPA security, introduction to some related modular arithmetic, El Gamal, RSA and Rabin constructions, some attacks on RSA.
• Zero Knowledge Proofs: introduction with motivation, definition of honest verifier zero knowledge, one protocol (graph coloring or some other NP complete problem)

Background

Mathematical maturity is the only pre-requisite. Knowledge of elementary probability, elementary algebra and elementary number theory will be a bonus, but we will recap the basics needed during the course.

Grading

• 35% -Final Exam

• 25% -Mid Sem Exam

• 20% -Best 2 out of 3 quizzes (will happen in 1 hour quiz slots Wed/Fri)

• 15% -Chalk and talk
  -presentations on topics given in class, email me to fix your topic.
  -submit written report by given deadline.

• 5% -Class Participation

References

• Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell

• A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup

• The Joy of Cryptography, Mike Rosulek

• A Course in Cryptography, Rafael Pass and Abhi Shelat

• Lecture notes for fundamentals of cryptography, Leonid Reyzin

• Foundations of Cryptography, Volume I-II, Oded Goldreich

• Comutational Number Theory (Basics)

Assignments

• Assignment 1 (2nd August 2024)
• Assignment 2 (12th August 2024)
• Assignment 3 (23rd August 2024) (Problem2c solution sketch.pdf)
• Assignment 4 (7th September 2024)
• Assignment 5 (29th September 2024)
• Assignment 6 (12th October 2024)
• Assignment 7 (30th October 2024)
• Quiz 1 (21st August 2024) (Quiz 1 solution sketch.pdf)
• Quiz 2 (4th September 2024) (Quiz 2 solution sketch.pdf)
• Quiz 3 (18th October 2024) (Quiz 3 solution sketch.pdf)
• MidSem Exam (20th September 2024) (MidSem solution sketch.pdf)

Lectures

Number/Date	Topics	Slide
Lecture 1 (31st July)	Introduction/Course policy, Classical Cryptography	Lecture 1.pdf
Lecture 2 (2nd Aug)	Basic Probability	Lecture 2.pdf
Lecture 3 (7th Aug)	One time pad, Perfect security, Drawbacks, Attacks	Lecture 3.pdf
Lecture 4 (9th Aug)	Tools for defining weaker security notions: modeling computation, negligible functions, semantic security	Lecture 4.pdf
Lecture 5 (14th Aug)	Pseudorandom Generators, Stream Ciphers, Computational Secure scheme, Proof by Reduction	Lecture 5.pdf
Lecture 6 (16th Aug)	Hybrid Arguments, More about PRGs -> Length Extension, Equivalence of unpredictability and pseduorandomness.	Lecture 6.pdf (Extra notes)
Lecture 7 (21st Aug)	Pseudorandom Functions, Security for Multiple Encryptions	Lecture 7.pdf
Lecture 8 (23rd Aug)	CPA Secure Encryption, Modes of Operation	Lecture 8.pdf
Lecture 9 (28th Aug)	CCA Secure Encryption, Message Authentication Codes	Lecture 9.pdf
Lecture 10 (30th Aug)	Authenticated Encryption, Domain extension of MACs, Motivating Hash functions	Lecture 10.pdf
Lecture 11 (4th Sep)	Cryptographic Hash functions, Hash-and-MAC, HMAC, Merkle-Damgård Transform, Journey so far in the course, bidding the symmetric world a farewell for now…	Lecture 11.pdf
6th, 11th, 13th Sep	CHALK AND TALK
14th – 22nd Sep	MID SEM WEEK
Lecture 12 (25th Sep)	Basic Number Theory, Cryptographic Hardness Assumptions- Discrete Log Assumption, Diffie-Hellman Assumptions, QR, PRG from DDH	Lecture 12.pdf
Lecture 13 (27th Sep)	One-way Functions (OWFs), OWPs from cryptographic hardness, Hard Core Predicates (HCP), Goldreich Levin HCP, PRGs from OWPs	Lecture 13.pdf
Lecture 14 (4th Oct)	Key Exchange Protocol (Diffie-Hellman), Public-key Encryption, IND-CPA Security, ElGamal Encryption, RSA Encryption	Lecture14.pdf
Lecture 15 (9th Oct)	Trapdoor Permutations (TDPs), TDPs to PKE, IND-CCA Security, DHIES Encryption	Lecture 15.pdf
Lecture 16 (11th Oct)	Digital Signatures, Lamport’s one-time signature, Extend to many-time signatures, Domain Extension using CRHF	Lecture 16.pdf (Lamport proof.pdf)
Lecture 17 (16th Oct)	Digital Signatures from RSA and Dlog, Schnorr Identification Protocol, Fiat Shamir transform	Lecture 17.pdf
Lecture 18 (18th Oct)	Interactive Proofs, Zero-knowledge (ZK) proofs: definition, Honest Verifier ZK proof for Graph Non-isomorphism	Lecture 18.pdf
Lecture 19 (23rd Oct)	Malicious-Verifier ZK proof, Commitment Scheme, ZK proof for NP	Lecture 19.pdf
Lecture 20 (25th Oct)	Proofs of Knowledge, Non-interactive ZK, Sigma Protocols	Lecture 20.pdf (feedback link)
30th Oct-8th Nov	Chalk and Talk Presentations

Chalk and Talk

Chalk and Talk Topic	Group	Report
#1 Equivalence of Perfect Security Notions	Asifahmad Asfaqahmad Shaikh, Aadya Pipersenia	Present on 6th Sept [Report.pdf]
#2 Venona Project	Mradul Kaushal, Avaneesh Vinayak Khadye	Present on 6th Sept [Report.pdf]
#3 Equivalence of Semantic Security and Computational Indistinguishability	Rohan Arrvind, Ashok Nayak	Present on 11th Sept [Report.pdf]
#4 RC4 (Explain + one attack)	Advay Bapat, Pranav Malpani	Present on 11th Sept [Report.pdf]
#5 LCG (Linear Congruential Generators) (Explain + one attack)	Shravya Suresh, Shubhhi Singh	Present on 11th Sept [Report.pdf]
#6 PRFs imply PRPs (Feistel Networks)	Parth Pundalik Pai, Parijat Mudras	Present on 13th Sept [Report.pdf]
#7 Padding Oracle Attack on CBC Mode [link]	Harsh Roniyar, Swarup Patil	Present on 13th Sept [Report.pdf]
#8 Knapsack Public Key Encryption Scheme + Attack	Pranav Singla, Rahul Patel	Present on 30th Oct [Report.pdf]
#9 Davies-Meyer Construction for compression function &Time-Space Tradeoff Attacks on Hash functions	Ishan Pandit, Kshitij Vaidya	Present on 30th Oct [Report.pdf][slides]
#10 Pohlig-Hellman Attack on Dlog problem	Aviral Vishesh Goel, Arnav Akshaya	Present on 6th Nov [Report.pdf]
#11 Bleichenbacher’s RSA Attack on PKCS#1 [link (section 4,5)]	Tanmay Patil, Mandavyapuram Jaswin Reddy	Present on 6th Nov [Report.pdf]
#12 TLS 1.3 [link]	Karrthik Radhakrishnan, Pinak Mahapatra	Present on 6th Nov [Report.pdf]
#13 DSA/ECDSA and biased-nonce attack [link and paper (section 4) for the biased-nonce attack]	K Ashvanth, Yashaswini	Present on 6th Nov [Report.pdf]
#14 Pailier Encryption, DCR Assumption, IND-CPA security	Pratham Agarwal, Anusha Dhakras	Present on 6th Nov [Report.pdf]
#15 One-time passwords: security against eavesdropping	Rishabh Ravi, Nawkar Parth Shailesh	Present on 8th Nov [Report.pdf]
#16 KZG Polynomial Commitment (only protocol and intuition for binding and hiding, skip detailed proof)	Arnav Jain, Arjun	Present on 8th Nov [Report.pdf]
#17 Combining Sigma Protocols: AND and OR proofs (only protocol and intuitions for soundness and HVZK; bonus marks if you give full proofs in report!)	Jay Mehta, Tanay Bhat	Present on 8th Nov [Report][slides]