**The Iterated Random Function Problem**

*Ritam Bhaumik and Nilanjan Datta and Avijit Dutta and Nicky Mouha and Mridul Nandi*

**Abstract: **At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by $O(q^2r(\log r)^3/N)$, where $N$ is the size of the domain. In previous work, the best known bound was $O(q^2r^2/N)$, obtained as a direct result of interpreting the iterated random function problem as a special case of CBC-MAC based on a random function. For the iterated random function problem, the best known attack has an advantage of $\Omega(q^2r/N)$, showing that our security bound is tight up to a factor of $(\log r)^3$.

**Category / Keywords: **secret-key cryptography / Iterated random function, random function, pseudorandom function, password hashing, Patarin, H-coefficient technique, provable security

**Original Publication**** (with minor differences): **IACR-ASIACRYPT-2017

**Date: **received 7 Sep 2017, last revised 17 Sep 2017

**Contact author: **nicky at mouha be

**Available format(s): **PDF | BibTeX Citation

**Version: **20170917:192500 (All versions of this report)

**Short URL: **ia.cr/2017/892

[ Cryptology ePrint archive ]