Instructor: Arpita Patra (Email: arpita AT iisc DOT ac DOT in) and Chaya Ganesh (Email: chaya AT iisc DOT ac DOT in)

Timings: 11:30 am - 1:00 pm on Tuesday and Thursday.

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.
(BS) “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, Pseudo-random Functions (Permutations), One-way Trapdoor Permutations.
Secret Key Encryptions (SKE): Various security notions such as Perfect Security, Semantic Security, Indistinguishability based Security, CPA Security.
Introduction to Secure Computation (Yao’s 2PC protocol and Circuit Garbling, GMW Protocol), Oblivious Transfer.

Grading

Announcements

The mid-term will be held on Saturday, 7th October 2023, 2:00 pm - 5:30 pm in CSA 252.
Assignment 3 has been posted in teams. The latex typed solutions must be submitted on or before 4th October, 11:59 pm.
Assignment 2 has been posted in teams. The latex typed solutions must be submitted on or before 25th September, 11:59 pm.
The second quiz will be held on Friday, 8th September 2023, 11:40 am - 12:10 pm in CSA 252.
Assignment 1 has been posted in teams. The latex typed solutions must be submitted on or before 10th September, 11:59 pm.
The first quiz will be held on Wednesday, 23rd August 2023, 5:10 pm - 5:40 pm in CSA 252.
Tutorial sessions will be held on every Friday, 11:30 am - 12:30 pm in CSA 252.
The Microsoft teams code for this class is: qbcz9ph

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 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], Chapter 1 of KL and BS
Date : 03-08-2023

Lecture 2 : Perfect Security: Definition, Construction (Vernam Cipher), Proof; Drawbacks of OTP.
References : [Slides], Chapter 2 of KL and BS
Date : 08-08-2023

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], Chapter 2 of KL and BS
Date : 10-08-2023

Lecture 4 : Secret Sharing: Definition. Threshold Secret Sharing: Constructions (Additive Secret Sharing, Ito-Saito-Nishizeki Secret Sharing), Analysis. Basics concept of Abstract Algebra. Polynomials over Field. Lagrange Interpolation.
References : [Slides], Chapter 13 of KL and Chapter 11 of BS
Date : 17-08-2023

Lecture 5 : Shamir Secret Sharing. Perfectly-Secure Message Transmission (PSMT). BGW MPC Protocol for Linear Functions.
References : [Slides], Chapter 13 of KL and Chapter 11 of BS
Date : 22-08-2023

Lecture 6 : 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], Chapter 3 of KL and Chapter 2 of BS
Date : 24-08-2023

Lecture 7 : Pseudorandomness and Pseudo-random Generators (PRG), Indistinguishability Security, Statistical Tests, Next-bit Prediction Security, Impossibility of PRG against unbounded adversary, ind-secure SKE from PRG, Proof of security
References : Chapter 3 of KL and BS
Date : 28-08-2023

Lecture 8 : Multiple Message Security vs. Single Message Security, Applications of ind-secure SKE -- Anonymous Message Transfer/Onion Routing, PRG with one-bit expansion implies PRG with many-bit expansion, Hybrid Arguments
References : Chapter 3 of KL and BS
Date : 29-08-2023

Supplementary Lecture 1 : Stream ciphers. Linear feedback shift registers (LFSR), Reconstruction attack, Non-linear FSR, Trivium
References : [Slides], [Video], Chapter 6 of KL
Date : 01-09-2023

Lecture 9 : Applications of PRG -- Coin-tossing and Commitment Schemes, Chosen Plaintext Attack (CPA), CPA-security, Pseudo-random Functions (PRF)
References : Chapter 3 of KL and Chapter 4 of BS
Date : 05-09-2023

Lecture 10 : SKE based on PRF, Proof for CPA-security, PRG implies PRF -- GGM/tree construction
References : Chapter 3 of KL and Chapter 4, 5 of BS
Date : 07-09-2023

Lecture 11 : Yao's 2PC, Circuit Garbling as an application of CPA-secure SKE
References : 'A Proof of Yao's Protocol for Secure Two-Party Computation' by Yehuda Lindell and Benny Pinkas (available online)
Date : 12-09-2023

Lecture 12 : Yao's 2PC, Oblivious Transfer (OT), GMW Protocol
References : 'A Proof of Yao's Protocol for Secure Two-Party Computation' by Yehuda Lindell and Benny Pinkas; 'How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority' by Oded Goldreich, Silvio Micali, Avi Wigderson
Date : 14-09-2023

Lecture 13 : One-way Functions (OWF), One-way Permutations (OWP), Hard-core Predicates, Partial proof of Goldreich-Levin, OWP + Hardcore predicates imply PRG with one bit expansion.
References : Chapter 7 of KL
Date : 21-09-2023

Lecture 14 : (Partial) proof of Goldreich-Levin, Hash Functions, Collision Resistance, Applications, Merkle Tree.
References : Chapter 5, 7 of KL
Date : 26-09-2023

Lecture 15 : One-way Trapdoor Permutation (OWTP), OT instantiation from OWTP
Date : 28-09-2023