CS 744: Pseudo-Random Generators

Departments to which the proposed course will be of interest:

CSE, Maths

 

Course Contents:

Pseudo-random generators are efficiently computable functions that stretch an input random string to a much bigger sized string such that the output string appears random to resource-bounded computations. These functions have become one of the fundamental objects to study in complexity theory because of their utility. They are used to derandomize randomized algorithms, formalize notions of cryptographic security, obtain lower bounds on the complexity of problems etc. (unfortunately, as of now very few constructions of pseudo- random generators are provably known although many are conjectured). In this course, we study pseudo-random generators and their connections in depth.

 

The topics covered in the course are as follows:

• Pseudo-random generators: definitions and Existence.
• Pseudo-random generators of small stretch: Definitions of cryptographic security, Equivalence of one-way functions and pseudo-random generators, Some functions conjectured to be one-way functions, Pseudo-random function generators.
• Pseudo-random generators of large stretch: Equivalence of lower bounds and pseudo-random generators, Known pseudo-random generators against small depth circuits and small space classes, Extractors and pseudo-random generators.
• Pseudo-random generators against arithmetic circuits: Equivalence of lower bounds and pseudo-random generators, A function conjectured to be pseudo- random.
• Other applications.

 

Reference:

• Foundations of Cryptography, Vol I and II.
• Author: Oded Goldreich.
• Research papers.