## Range Extension for Weak PRFs; 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 $\{\langle 2\rangle,\langle 1,2\rangle\}$ 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.

## BibTeX Citation

@inproceedings{PieSjo07, author = {Krzysztof Pietrzak and Johan Sjödin}, title = {Range Extension for Weak {PRF}s; The Good, the Bad, and the Ugly}, editor = {Moni Naor}, booktitle = {Advances in Cryptology --- EUROCRYPT 2007}, pages = 517--533, series = {Lecture Notes in Computer Science}, volume = 4515, year = 2007, month = 5, publisher = {Springer-Verlag}, }