Salil Vadhan, Harvard University

Abstract

This will be a tutorial on how various notions of computational entropy can be useful in understanding, simplifying, and improving constructions of cryptographic primitives. We will focus on the case of constructing pseudorandom generators from one-way functions. We will begin with revisiting the classic construction of pseudorandom generators from one-way permutations using this modern perspective, relating one-wayness to "guessing pseudoentropy", which in turn can be turned into pseudorandomness via "reconstructive extractors". Then we will turn to constructions of pseudorandom generators from general one-way functions. Here we will relate one-wayness to "sampling relative entropy," which in turn can be related to "(HILL) pseudoentropy," which can also be converted to pseudorandomness via randomness extractors. Time permitting, we will sketch how this approach yields a construction of pseudorandom generators with a seed length of O~(n^3) from a one-way function with input length n [Haitner-Reingold-Vadhan `10, Vadhan-Zheng `11], and discuss potential approaches for improved positive or negative results.

Slides    Video