Cryptology ePrint Archive: Report 2016/813

Fast Pseudorandom Functions Based on Expander Graphs

Benny Applebaum and 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.

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