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: Definition of PRF, GGM Construction of PRF, Proof of GGM Algorithm.

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

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]

A running lecture scribe of the course can be found here.