---
_id: '3221'
abstract:
- lang: eng
  text: |-
    We investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on m independent functions F 1,...,F m is given by a set of strings over {1,...,m}*, where for example {〈2〉, 〈1,2〉} corresponds to the function X ↦[F 2(X),F 2(F 1(X))]. All efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form.
    We completely classify such constructions as good, bad or ugly, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose insecurity can be proven via a black-box reduction, and the ugly constructions are those which are neither good nor bad.
    Our classification shows that the range expansion from [10] is optimal, in the sense that it achieves the best possible expansion (2 m  − 1 when using m keys).
    Along the way we show that for weak quasirandom functions (i.e. in the information theoretic setting), all constructions which are not bad – in particular all the ugly ones – are secure.
acknowledgement: This work was partially supported by the Zurich Information Security
  Center. It represents the views of the authors.
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. Range extension for weak PRFs the good the bad and
    the ugly. In: Vol 4515. Springer; 2007:517-533. doi:<a href="https://doi.org/10.1007/978-3-540-72540-4_30">10.1007/978-3-540-72540-4_30</a>'
  apa: 'Pietrzak, K. Z., &#38; Sjödin, J. (2007). Range extension for weak PRFs the
    good the bad and the ugly (Vol. 4515, pp. 517–533). Presented at the EUROCRYPT:
    Theory and Applications of Cryptographic Techniques, Springer. <a href="https://doi.org/10.1007/978-3-540-72540-4_30">https://doi.org/10.1007/978-3-540-72540-4_30</a>'
  chicago: Pietrzak, Krzysztof Z, and Johan Sjödin. “Range Extension for Weak PRFs
    the Good the Bad and the Ugly,” 4515:517–33. Springer, 2007. <a href="https://doi.org/10.1007/978-3-540-72540-4_30">https://doi.org/10.1007/978-3-540-72540-4_30</a>.
  ieee: 'K. Z. Pietrzak and J. Sjödin, “Range extension for weak PRFs the good the
    bad and the ugly,” presented at the EUROCRYPT: Theory and Applications of Cryptographic
    Techniques, 2007, vol. 4515, pp. 517–533.'
  ista: 'Pietrzak KZ, Sjödin J. 2007. Range extension for weak PRFs the good the bad
    and the ugly. EUROCRYPT: Theory and Applications of Cryptographic Techniques,
    LNCS, vol. 4515, 517–533.'
  mla: Pietrzak, Krzysztof Z., and Johan Sjödin. <i>Range Extension for Weak PRFs
    the Good the Bad and the Ugly</i>. Vol. 4515, Springer, 2007, pp. 517–33, doi:<a
    href="https://doi.org/10.1007/978-3-540-72540-4_30">10.1007/978-3-540-72540-4_30</a>.
  short: K.Z. Pietrzak, J. Sjödin, in:, Springer, 2007, pp. 517–533.
conference:
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
date_created: 2018-12-11T12:02:06Z
date_published: 2007-06-12T00:00:00Z
date_updated: 2021-01-12T07:41:54Z
day: '12'
doi: 10.1007/978-3-540-72540-4_30
extern: 1
fulldoi: https://doi.org/10.1007/978-3-540-72540-4_30
intvolume: '      4515'
month: '06'
page: 517 - 533
publication_status: published
publisher: Springer
publist_id: '3460'
quality_controlled: 0
status: public
title: Range extension for weak PRFs the good the bad and the ugly
type: conference
volume: 4515
year: '2007'
...