Welcome to the resource topic for 2016/813
Title:
Fast Pseudorandom Functions Based on Expander Graphs
Authors: Benny Applebaum, Pavel Raykov
Abstract:We present direct constructions of pseudorandom function (PRF) families based on Goldreich’s one-way function. Roughly speaking, we assume that non-trivial local mappings f:\{0,1\}^n\rightarrow \{0,1\}^m whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak PRFs which can be computed in linear time of O(n) on a RAM machine with O(\log n) word size, or by a depth-3 circuit with unbounded fan-in AND and OR gates (AC0 circuit), and standard PRFs that can be computed by a quasilinear size circuit or by a constant-depth circuit with unbounded fan-in AND, OR and Majority gates (TC0). 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.
ePrint: https://eprint.iacr.org/2016/813
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .