" Cryptography from Information Loss "
Prashant Vasudevan (UC Berkeley)
Abstract: Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to
an instance of another in such a way that solving the latter allows solving the former. The subject of this work is “lossy”
reductions, where the reduction loses some information about the input instance. Such reductions are closely related to prevalent
concepts in various areas of computer science, such as parametrized complexity and cryptography. We show that such reductions, when
they exist, have interesting and powerful consequences for lifting hardness into “useful” hardness, namely cryptography. We show
various sufficient conditions in terms of such reductions that, together with worst-case or average-case hardness of the underlying
language, imply one-way functions and collision-resistant hash functions.
Joint work with Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, and Vinod Vaikuntanathan.