---
_id: '3226'
abstract:
- lang: eng
text: 'A family of functions is weakly pseudorandom if a random member of the family
is indistinguishable from a uniform random function when queried on random inputs.
We point out a subtle ambiguity in the definition of weak PRFs: there are natural
weak PRFs whose security breaks down if the randomness used to sample the inputs
is revealed. To capture this ambiguity we distinguish between public-coin and
secret-coin weak PRFs. We show that the existence of a secret-coin weak PRF which
is not also a public-coin weak PRF implies the existence of two pass key-agreement
(i.e. public-key encryption). So in Minicrypt, i.e. under the assumption that
one-way functions exist but public-key cryptography does not, the notion of public-
and secret-coin weak PRFs coincide. Previous to this paper all positive cryptographic
statements known to hold exclusively in Minicrypt concerned the adaptive security
of constructions using non-adaptively secure components. Weak PRFs give rise to
a new set of statements having this property. As another example we consider the
problem of range extension for weak PRFs. We show that in Minicrypt one can beat
the best possible range expansion factor (using a fixed number of distinct keys)
for a very general class of constructions (in particular, this class contains
all constructions that are known today). '
acknowledgement: This work was partially supported by the Zurich Information Security
Center.
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Johan
full_name: Sjödin, Johan
last_name: Sjödin
citation:
ama: 'Pietrzak KZ, Sjödin J. Weak pseudorandom functions in minicrypt. In: Vol 5126.
Springer; 2008:423-436. doi:10.1007/978-3-540-70583-3_35'
apa: 'Pietrzak, K. Z., & Sjödin, J. (2008). Weak pseudorandom functions in minicrypt
(Vol. 5126, pp. 423–436). Presented at the ICALP: Automata, Languages and Programming,
Springer. https://doi.org/10.1007/978-3-540-70583-3_35'
chicago: Pietrzak, Krzysztof Z, and Johan Sjödin. “Weak Pseudorandom Functions in
Minicrypt,” 5126:423–36. Springer, 2008. https://doi.org/10.1007/978-3-540-70583-3_35.
ieee: 'K. Z. Pietrzak and J. Sjödin, “Weak pseudorandom functions in minicrypt,”
presented at the ICALP: Automata, Languages and Programming, 2008, vol. 5126,
no. PART 2, pp. 423–436.'
ista: 'Pietrzak KZ, Sjödin J. 2008. Weak pseudorandom functions in minicrypt. ICALP:
Automata, Languages and Programming, LNCS, vol. 5126, 423–436.'
mla: Pietrzak, Krzysztof Z., and Johan Sjödin. Weak Pseudorandom Functions in
Minicrypt. Vol. 5126, no. PART 2, Springer, 2008, pp. 423–36, doi:10.1007/978-3-540-70583-3_35.
short: K.Z. Pietrzak, J. Sjödin, in:, Springer, 2008, pp. 423–436.
conference:
name: 'ICALP: Automata, Languages and Programming'
date_created: 2018-12-11T12:02:07Z
date_published: 2008-08-06T00:00:00Z
date_updated: 2021-01-12T07:41:56Z
day: '06'
doi: 10.1007/978-3-540-70583-3_35
extern: 1
intvolume: ' 5126'
issue: PART 2
month: '08'
page: 423 - 436
publication_status: published
publisher: Springer
publist_id: '3455'
quality_controlled: 0
status: public
title: Weak pseudorandom functions in minicrypt
type: conference
volume: 5126
year: '2008'
...