---
res:
bibo_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 kS 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
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 2N in security, where N is the input length. The first contribution
of this paper is a new reduction that only loses a quasipolynomial factor qlog
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 2N loss,
which we show is inherent. We construct a meta-reduction which shows that any
“simple” reduction of full security from a noninteractive hardness assumption
must incur an exponential security loss.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Georg
foaf_name: Georg Fuchsbauer
foaf_surname: Fuchsbauer
foaf_workInfoHomepage: http://www.librecat.org/personId=46B4C3EE-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Momchil
foaf_name: Konstantinov, Momchil
foaf_surname: Konstantinov
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Krzysztof Pietrzak
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Vanishree
foaf_name: Rao, Vanishree
foaf_surname: Rao
bibo_doi: 10.1145/2591796.2591825
bibo_volume: 8874
dct_date: 2014^xs_gYear
dct_publisher: Springer@
dct_title: Adaptive security of constrained PRFs@
...