---
res:
bibo_abstract:
- "We show a hardness-preserving construction of a PRF from any length doubling
PRG which improves upon known constructions whenever we can put a non-trivial
upper bound q on the number of queries to the PRF. Our construction requires only
O(logq) invocations to the underlying PRG with each query. In comparison, the
number of invocations by the best previous hardness-preserving construction (GGM
using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting
from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially
secure if queried at most q = exp(√n)times and where each invocation of the PRF
requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n)
required by known constructions. \r\n@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Abhishek
foaf_name: Jain, Abhishek
foaf_surname: Jain
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Aris
foaf_name: Tentes, Aris
foaf_surname: Tentes
bibo_doi: 10.1007/978-3-642-28914-9_21
bibo_volume: 7194
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Hardness preserving constructions of pseudorandom functions@
...