Paper 2017/892

The Iterated Random Function Problem

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


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$.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Iterated random functionrandom functionpseudorandom functionpassword hashingPatarinH-coefficient techniqueprovable security
Contact author(s)
nicky @ mouha be
2017-09-17: received
Short URL
Creative Commons Attribution


      author = {Ritam Bhaumik and Nilanjan Datta and Avijit Dutta and Nicky Mouha and Mridul Nandi},
      title = {The Iterated Random Function Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2017/892},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.