期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only k(n) oracle queries,
for any k(n)=(1) (e.g.\ k(n)=logn).
This result shows a limitation of a certain class of
techniques for proving efficiency lower bounds on the
construction of PRF from OWF. Our result builds on the
work of Reingold, Trevisan, and Vadhan (TCC '04), who
show that when OWF do not exist there is a pseudorandom
{\em generator} (PRG) construction that makes only one
oracle query to the hard-to-invert function. Our proof
combines theirs with the Nisan-Wigderson generator (JCSS '94),
and with a recent technique by Berman and Haitner (TCC '12).
