Our proofs are based on a new search-to-decision reduction for expander-based functions. This extends a previous reduction of the first author (STOC 2012) which was applicable for the special case of \emph{random} local functions. Additionally, we present a new family of highly efficient hash functions whose output on exponentially many inputs jointly forms (with high probability) a good expander graph. These hash functions are based on the techniques of Miles and Viola (Crypto 2012). Although some of our reductions provide only relatively weak security guarantees, we believe that they yield novel approach for constructing PRFs, and therefore enrich the study of pseudorandomness.
Category / Keywords: foundations, pseudo-random functions, Goldreich's OWF Original Publication (in the same form): IACR-TCC B--2016 Date: received 23 Aug 2016, last revised 25 Aug 2016 Contact author: raykov pavel at gmail com,benny applebaum@gmail com Available format(s): PDF | BibTeX Citation Version: 20160825:185933 (All versions of this report) Short URL: ia.cr/2016/813 Discussion forum: Show discussion | Start new discussion