The three above-mentioned papers all show that the classical GGM construction (J.ACM'86) of a PRF from a pseudorandom generator (PRG) directly yields a constrained PRF where one can compute constrained keys to evaluate the PRF on all inputs with a given prefix. This constrained PRF has already found many interesting applications. Unfortunately, the existing security proofs only show selective security (by a reduction to the security of the underlying PRG). To achieve full security, one has to use complexity leveraging, which loses an exponential factor $2^N$ in security, where $N$ is the input length.
The first contribution of this paper is a new reduction that only loses a quasipolynomial factor $q^{\log N}$, where $q$ is the number of adversarial queries. For this we develop a new proof technique which constructs a distinguisher by interleaving simple guessing steps and hybrid arguments a small number of times. This approach might be of interest also in other contexts where currently the only technique to achieve full security is complexity leveraging.
Our second contribution is concerned with another constrained PRF, due to Boneh and Waters, which allows for constrained keys for the more general class of bit-fixing functions. Their security proof also suffers from a $2^N$ loss, which we show is inherent. We construct a meta-reduction which shows that any ``simple'' reduction of full security from a non-interactive hardness assumption must incur an exponential security loss.
Category / Keywords: secret-key cryptography / Constrained PRF, Complexity Leveraging, Full Security, Meta-Reduction Original Publication (with major differences): IACR-ASIACRYPT-2014 Date: received 2 Jun 2014, last revised 28 Jan 2015 Contact author: gfuchsbauer at ist ac at Available format(s): PDF | BibTeX Citation Note: Major revision improving presentation of the results. Version: 20150128:165810 (All versions of this report) Short URL: ia.cr/2014/416 Discussion forum: Show discussion | Start new discussion