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.

Available format(s)
Publication info
Keywords
foundationspseudo-random functionsGoldreich's OWF
Contact author(s)
raykov pavel @ gmail com
benny applebaum @ gmail com
History
2016-08-25: revised
See all versions
Short URL
https://ia.cr/2016/813

CC BY

BibTeX

@misc{cryptoeprint:2016/813,
author = {Benny Applebaum and Pavel Raykov},
title = {Fast Pseudorandom Functions Based on Expander Graphs},
howpublished = {Cryptology ePrint Archive, Paper 2016/813},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/813}},
url = {https://eprint.iacr.org/2016/813}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.