• Calendar

June 26, Tuesday
12:00 – 14:00

This talk addresses one of the most the most fundamental tasks in Cryptography, that of constructing pseudorandom generators from one-way functions. The seminal paper of Hastad et al. (known as HILL), proved that these notions are equivalent. However, the reduction is not nearly as security preserving as one may desire. In this context, we revisit a technique that we call the Randomized Iterate, introduced by Goldreich et al. In the talk I will introduce the randomized iterate and survey its recent applications. Our results simplify and strengthen the basic technique and achieve constructions with improved security of pseudorandom generators from regular one-way functions as well as general one-way functions. I will focus on another result: a new construction of a pseudorandom generator from any exponentially hard one-way function that gains substantial improvement in both security and efficiency.

Joint work with Iftach Haitner and Omer Reingold.