# Range Extension for Weak {PRF}s; The Good, the Bad, and the Ugly

## Krzysztof Pietrzak and Johan Sjödin

```
```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,\ldots,F_m$ is given by a set of strings over
$\{1,\ldots,m\}^*$, where for example $\{\str{2},\str{1,2}\}$ corresponds
to the function $X \mapsto [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
*in*security can be proven via a black-box reduction. The ugly
constructions are those which are neither good nor bad.

Our classification shows that the range expansion from \cite{MaSj06} 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.