Instructors: Dr. Avijit Dutta and Dr. Bimal Mandal
Course Objective:
Cryptology is concerned with the conceptualization, definition, and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. This course presents a rigorous and systematic treatment of the foundation issues: defining cryptographic tasks and solving new cryptographic problems using existing and new tools. The focus is given on the basic mathematical tools as well as some new advanced cryptographic tools and the advances of research using those tools.
Syllabus:
1. Introduction: Computation Model, P-Class, NP-Class, NP-Complete Class, Probabilisitic Turing Machine, BPP Class, P=NP implies no one-way function exists, Amplification Lemma, Non-Uniform Polynomial Machines, P/Poly-Class, P is a subset of P/Poly.
2. One-way Function: One-way Functions, Strong and Weak One way Function, One-way Function exists implies Weak One way Function exists, Weak One-way Function exists implies Strong One-way Function exists, Hardness Amplification Lemma, One-way Function defined only for some lengths, Length Regular and Length Preserving One-way Function, Non-Uniform One-way Function, Collections of One-way Function, Candidates of Collection of One-way Functions, Collections of Trapdoor Permutations, RSA Trapdoor Permutations.
3. Hard-Core Predicate: Motivation of Hard-Core Predicate, Definition of Hard-Core Predicate, Proof of Goldreich-Levin Theorem, Hard-Core Functions, Candidates of Hard-Core Predicates and Functions.
4. Pseudorandom Generators: Definition of PRG, Construction of PRG from Hard-Core Predicate, Computational XOR Lemma, Computational Indistinguishablity, Statistical Distance, Ensemble, Hybrid Random Variables, Proof using Hybrid Game, Unpredictability vs Indistinguishability, PRG Implies Strong One way function
5. Pseudorandom Functions and Permutations: Definition of PRF, Security notion of PRF, GGM Construction of PRF, Proof of GGM Algorithm, Definition of PRP, SPRP, Security notion of PRP, Luby-Rackoff Design, SPRP attack on 3-round Luby-Rackoff Design.
6. Zero Knowledge Proofs: Interactive Turing Machines, Definition of Interactive Proof System, Interactive Proof Class, Interactive Proof of Graph-Non-Isomorphism, Relation between NP, Co-NP, PSPACE and IP, Definition of Zero Knowledge Proofs, Perfect Zero Knowledge Proof, Statistical Zero Knowledge Proof, Computational Zero Knowledge Proof and their relation, Notion of Simulation, Zero Knowledge Proof of Graph-Isomorphism, Zero Knowledge Proof with Auxiliary Input, Sequential Composition of Zero Knowledge Proof, Bit Commitment Scheme, Construction of Bit Commitment from One way function, Zero Knowledge Proof for 3-Coloring, Zero Knowledge Proof for any NP language.
7. Secret Sharing Scheme: Definition of Secret Sharing Scheme, Access Structure, Threshold Secret Sharing Scheme, Benaloh-Leichter Scheme, Ito-Saito-Nishizeki Scheme, Lagranage Interpolation, Shamir Secret Sharing Scheme, Linear Secret Sharing Scheme and Its Properties, General (non-threshold) Secret Sharing Scheme.
8. Elliptic Curve Cryptogrphy: Group law, Point at Infinity, j-invariant, Elliptic curve over a finite field, Endomorphism, The Frobenius endomorphism, Torsion points, The Weil pairing, The Tate-Lichtenbaum pairing, Discrete logarithm problem, Diffie-Hellman key exchange, ElGamal public key encryption, ElGamal digital signatures, Digital signature algorithm, A public key scheme based on factoring, A cryptosystem based on Weil pairing
References:
- Foundations of Cryptography Vol-I Basic Tools by Oded Goldreich, ISBN 0-521-79172-3. Published in US in June 2001. Publisher: Cambridge University Press.
- Introduction to Modern Cryptography, 3rd Edition By Jonathan Katz and Yehuda Lindell, CRC Press
- A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup.
- Elliptic Curves Number Theory and Cryptography by Lawrence C Washington (2nd Edition)
- Online Lecture on Secure Multiparty Computation by Dr. Ashish Choudhury of IIIT Bangalore.
Classes:
[1] Introductory Materials: [Notes] [Videos]
[2] One-way Function: [Notes] [Videos]
[3] Hard-Core Predicates and Functions: [Notes] [Videos]
[4] Computational Indistinguishablity, Ensemble, Pseudorandom Genrators: [Notes] [Videos]
[5] Pseudorandom Functions and Pseudorandom Permutations: [Notes]
[6] Interactive Turing Machine, Interactive Proof System: [Notes]
[7] Zero Knowledge Proofs: [Notes]
[8] Secret Sharing Schemes: [Notes]
[9] Elliptic Curve Cryptography: [Notes]
A running lecture scribe of the course can be found here.