You are looking at a specific version 20140605:203716 of this paper. See the latest version.

Paper 2014/416

Adaptive Security of Constrained PRFs

Georg Fuchsbauer and Momchil Konstantinov and Krzysztof Pietrzak and Vanishree Rao

Abstract

Constrained pseudorandom functions have recently been introduced independently by Boneh and Waters [Asiacrypt'13], Kiayias et al.\ [CCS'13], and Boyle et al.\ [PKC'14]. In a standard pseudorandom function (PRF) a key $k$ is used to evaluate the PRF on all inputs in the domain. Constrained PRFs additionally offer the functionality to delegate ``constrained'' keys $k_S$ which allow to evaluate the PRF only on a subset $S$ of the domain. The three above-mentioned papers all show that the classical GGM construction [J.ACM'86] of a PRF from a pseudorandom generator (PRG) directly gives 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 get 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 novel 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. We construct a meta-reduction which shows that any ``simple'' reduction that proves full security of this construction from a non-interactive hardness assumption must incur an exponential security loss.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Constrained PRFComplexity LeveragingFull SecurityMeta-Reduction
Contact author(s)
krzpie @ gmail com
History
2015-01-28: revised
2014-06-05: received
See all versions
Short URL
https://ia.cr/2014/416
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.