Understanding and manipulating the hardness of one-way functions via computational analogues of entropiesSpeaker: Thibaut
Title: Understanding and manipulating the hardness of one-way functions via computational analogues of entropies
Date: 08 Apr 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Audience background: General TCS background, familiarity with pseudorandomness and cryptography helps but important definitions will be reminded as seen fit
Talk style: Casual and interactive whiteboard presentation
Abstract: We will discuss a line of work spread over the last decade simplifying and making more efficient constructions of cryptographic primitives from one-way functions. These improvements have been made possible by the introduction of computational analogues of entropy and understanding the constructions as manipulating these form of “computational entropies”. Specifically, we will focus on the constructions of pseudorandom generators and statistically hiding commitments from one-way functions which rely on the notions of next-bit pseudoentropy and next-bit accessible entropy respectively. We will first show how both notions of computational entropies can be seen as dual from each other and deriving from a single notion of hardness “KL-hardness” which one-way functions are easily shown to possess. If time permits, we will then discuss how similar sequences of transformations (entropy equalization, flattening and hashing) can be used to “amplify” these entropies (or more accurately, a small initial gap between real and computational entropies) to obtain the desired primitives.