# E0 235: Cryptography (Fall 2020)

• Instructors: Chaya Ganesh and Arpita Patra   Course credits: 3:1   Lecture time: T,Th 3:30-5 pm   Venue: Microsoft Teams.

• TAs: Prajval Koul (prajvalkoul AT iisc DOT ac DOT in)

• Office Hours: By appointment. Contact Prajval to make an appointment with the instructor.

• Objective:
This course offers a graduate introduction to cryptography, the science of securing data and computation against various adversarial behaviors. At the end of the course, you should be able to:
1. Formally define security properties and reason about them mathematically.
2. Understand cryptographic constructions at work: what makes them secure.

• Intended Audience: All students with curiosity about cryptography are welcome. Mathematical maturity is expected.

• Syllabus:
• For first half of the syllabus, refer to this link.
• 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.

• References:
• Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell. [Link]
• A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup. [Link]
• Foundations of Cryptography, Oded Goldreich. [Link]

• Prerequisites: Mathematical maturity, Familiarity/ ease with reading and writing proofs, Algorithmic concepts, Elementary number theory, Elementary discrete probability.

• Course Policy:

• Assignments - 40%
• In-class Quizzes - 24%
• Final exam - 36%

• Collaboration:
You are encouraged to discuss homework problems with your peers. However, you must write up your own solutions, and list the names of students you collaborated with in each homework you turn in.

• Announcements:
• Homework 3 has been posted.
• Quiz 3 will be held on Jan 12.
• Homework 2 has been posted.
• Quiz 2 will be held on Dec 22.
• Homework 1 has been posted.
• Quiz 1 will be held on Dec 8.
• First class on Dec 1.

• Assignments:

• Lectures:
This is a list of lectures delivered in the course (for reference purposes). Actual lectures and notes are available on Teams to the course attendees.
• Lecture 0 (Dec 1): Introduction and motivation.
• Lecture 1 (Dec 3): Algebra and Number theory refresher.
• Lecture 2 (Dec 8): Diffie Hellman key exchange.
• Lecture 3 (Dec 10): Basic hardness assumptions and the Diffie Hellman problem, RSA and Rabin function.
• Lecture 4 (Dec 15): Public Key Cryptosystems, Hybrid Encryption, Random Oracle Model.
• Lecture 5 (Dec 17): Random Oracle Model: Proofs, Programmability, and Public Key Encryption; Elgamal Encryption Scheme.
• Lecture 6 (Dec 22): CPA Security of Elgamal Encryption, CCA Security in Public Key setting: Preliminaries, Definition, and Constructions.
• Lecture 7 (Dec 24): Digital Signatures: Motivation, Definition, (CMA) Security; Signatures from Trapdoor One-way Permutations.
• Lecture 8 (Dec 29): Hash and Sign Paradigm, Fast Hash based Signatures, Lamport's One-time Signature Scheme.
• Lecture 9 (Dec 31): Stateful Signature Schemes, Merkle Signatures, Certificates.
• Lecture 10 (Jan 5): Proofs and Proof Systems: Soundness, Completeness, Efficiency; Notion of Interactive Proof Systems, Complexity Class IP, Zero Knowledge Proofs.
• Lecture 11 (Jan 7): Zero Knowledge Proof System, Quadratic Residuosity Problem, Zero Knowledge for NP (HAM and SAT), Paradigms of Zero Knowledge, Soundness Amplification.
• Lecture 12 (Jan 12): Proof of Knowledge, Zero Knowledge Proofs of Knowledge, Knowledge Soundness, Knowledge Extraction, Schnorr's Protocol.
• Lecture 13 (Jan 14): Sigma Protocols, Non-interactivity and the Fiat-Shamir Heuristic, Zero Knowledge from Sigma Protocols, Proof of Knowledge from Sigma Protocols.

• Tutorials:
(Will be announced).