---
OA_place: repository
OA_type: green
_id: '1927'
abstract:
- lang: eng
text: 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.
acknowledgement: "We are grateful to Mihir Bellare for his feedback on earlier versions
of this paper. We are indebted to Vanishree Rao for her generous assistance in preparing
this proceedings version.\r\nResearch supported by ERC starting grant (259668-PSPC)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Momchil
full_name: Konstantinov, Momchil
last_name: Konstantinov
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Vanishree
full_name: Rao, Vanishree
last_name: Rao
citation:
ama: 'Fuchsbauer G, Konstantinov M, Pietrzak KZ, Rao V. Adaptive security of constrained
PRFs. In: 20th International Conference on the Theory and Application of Cryptology
and Information Security. Vol 8874. Springer Nature; 2014:82-101. doi:10.1007/978-3-662-45608-8_5'
apa: 'Fuchsbauer, G., Konstantinov, M., Pietrzak, K. Z., & Rao, V. (2014). Adaptive
security of constrained PRFs. In 20th International Conference on the Theory
and Application of Cryptology and Information Security (Vol. 8874, pp. 82–101).
Kaoshiung, Taiwan, China: Springer Nature. https://doi.org/10.1007/978-3-662-45608-8_5'
chicago: Fuchsbauer, Georg, Momchil Konstantinov, Krzysztof Z Pietrzak, and Vanishree
Rao. “Adaptive Security of Constrained PRFs.” In 20th International Conference
on the Theory and Application of Cryptology and Information Security, 8874:82–101.
Springer Nature, 2014. https://doi.org/10.1007/978-3-662-45608-8_5.
ieee: G. Fuchsbauer, M. Konstantinov, K. Z. Pietrzak, and V. Rao, “Adaptive security
of constrained PRFs,” in 20th International Conference on the Theory and Application
of Cryptology and Information Security, Kaoshiung, Taiwan, China, 2014, vol.
8874, pp. 82–101.
ista: 'Fuchsbauer G, Konstantinov M, Pietrzak KZ, Rao V. 2014. Adaptive security
of constrained PRFs. 20th International Conference on the Theory and Application
of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and
Application of Cryptology and Information Security, LNCS, vol. 8874, 82–101.'
mla: Fuchsbauer, Georg, et al. “Adaptive Security of Constrained PRFs.” 20th
International Conference on the Theory and Application of Cryptology and Information
Security, vol. 8874, Springer Nature, 2014, pp. 82–101, doi:10.1007/978-3-662-45608-8_5.
short: G. Fuchsbauer, M. Konstantinov, K.Z. Pietrzak, V. Rao, in:, 20th International
Conference on the Theory and Application of Cryptology and Information Security,
Springer Nature, 2014, pp. 82–101.
conference:
end_date: 2014-12-11
location: Kaoshiung, Taiwan, China
name: 'ASIACRYPT: Conference on the Theory and Application of Cryptology and Information
Security'
start_date: 2014-12-07
date_created: 2018-12-11T11:54:45Z
date_published: 2014-12-15T00:00:00Z
date_updated: 2025-09-23T09:47:44Z
day: '15'
department:
- _id: KrPi
doi: 10.1007/978-3-662-45608-8_5
ec_funded: 1
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-662-45608-8_5
intvolume: ' 8874'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2014/416
month: '12'
oa: 1
oa_version: Submitted Version
page: 82-101
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: 20th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eisbn:
- '9783662456088'
eissn:
- 1611-3349
isbn:
- '9783662456071'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '5167'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Adaptive security of constrained PRFs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8874
year: '2014'
...