Course Outline
The course deals with the revolutionary developments which took place in the last decade to transform cryptography from a semi-scientific discipline to a field in Theoretical Computer Science. In particular, the course deals with concepts such as computational indistinguishability, pseudo-randomness, Random-Oracles, zero-knowledge interactive proofs (see detailed syllabus). The emphasis shall be on presenting the basic concepts, definitions, goals, assumptions and results in cryptography formally. The contents of the course shall have significance to students of computer science at all levels, including researchers. The proper understanding of the fundamentals behind the much important topic of cryptography shall have various applications in designing and analyzing cryptographic primitives and security protocols. Please note that this is NOT AN INTRODUCTORY COURSE TO CRYPTOGRAPHY, and we shall not spend much time on basic definitions. The students are assumed to read them up on their own.

Detailed Syllabus:

Introduction to Cryptography: Basics of Symmetric Key Cryptography, Basics of Assymetric Key Cryptography, Hardness of Functions

Notions of Semantic Security (SS) and Message Indistinguishability (MI): Proof of Equivalence of SS and MI, Hard Core Predicate, Trap-door permutation, Goldwasser-Micali Encryption

Goldreich-Levin Theorem: Relation between Hardcore Predicates and Trap-door permutations

Formal Notions of Attacks: Attacks under Message Indistinguishability: Chosen Plaintext Attack(IND-CPA), Chosen Ciphertext Attacks (IND-CCA1 and IND-CCA2), Attacks under Message Non-malleability: NM-CPA and NM-CCA2, Inter-relations among the attack model

Random Oracles: Provable Security and asymmetric cryptography, hash functions

One-way functions: Weak and Strong one way functions

Pseudo-random Generators (PRG): Blum-Micali-Yao Construction, Construction of more powerful PRG, Relation between One-way functions and PRG, Pseudo-random Functions (PRF)

Building a Pseudorandom Permutation: The Luby Rackoff Construction: Formal Definition, Application of the Luby Rackoff Construction to the construction of Block Ciphers, The DES in the light of Luby Rackoff Construction

Left or Right Security (LOR)

Message Authentication Codes (MACs): Formal Definition of Weak and Strong MACs, Using a PRF as a MAC, Variable length MAC

Public Key Signature Schemes: Formal Definitions, Signing and Verification, Formal Proofs of Security of Full Domain Hashing

Assumptions for Public Key Signature Schemes: One way functions Imply Secure One-time Signatures

Shamir's Secret Sharing Scheme

Formally Analyzing Cryptographic Protocols

Zero Knowledge Proofs and Protocols

Text Books:

Hans Delfs, Helmut Knebl, "Introduction to Cryptography, Principles and Applications", Springer Verlag.

Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography", Chapman \& Hall/CRC.

Wenbo Mao, "Modern Cryptography, Theory and Practice", Pearson Education (Low Priced Edition)

Shaffi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography, Available in http://citeseerx.ist.psu.edu

Reference Books:

O. Goldreich, Foundations of Cryptography, CRC Press (Low Priced Edition Available), Part 1 and Part 2

(For the confusion with the title of the course, blame Him, the author of this classic text and not a lesser mortal like me.)

Tentative Evaluation Procedure

Scribing is essential for the course. The students are supposed to write scribes for each class and submit them on a weekly basis mentioning the name of the author, and also the date of the class. Please treat this as serious, as I will be meticulous while correcting and there will be significant marks for the scribes. Also the best scribe will be put up on the web-page along with your name for future batches and for people outside the institute.

There will be marks for term paper writing, when the students will be asked to present a write up on a related topic (to be fixed by me or chosen by the students with my consent). We shall have a discussion on the topic during the class sessions or during a mutually decided time. The submissions will be in individuals or in groups depending on the class strength. All documents are to be prepared in latex.

Two Tests during the Mid-sem and End-Sem. Please note that the final evaluation methodology and the marks distribution shall depend on the progress of the class.

Presentations for the class:



Formal Notions of Encryption

Hard Core Predicates

Pseudo Random Generators

Pseudo Random Functions - I

Pseudo Random Functions - II

Luby Rackoff's Construction

Authentication and Encryption: How to order them?

Relations among Notions of Security for Public Key Schemes

Message Authentication Codes

Digital Signatures

Random Oracles

Practice Problems



Class Test-I

Important Papers

How to construct pseudorandom functions, Oded Goldreich, Shafi Goldwasser and Silvio Micali, JACM, 1986