The Iterated Random Function Problem

Published: November 02, 2017


Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, Nicky W. Mouha, Mrudil 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 O(q^2r/N), showing that our security bound is tight up to a factor of (log r)^3.
Proceedings Title: LNCS: Advances in Cryptology – ASIACRYPT 2017
Volume: 10625
Conference Dates: December 3-7, 2017
Conference Location: Hong Kong, -1
Conference Title: The 23rd Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
Pub Type: Conferences


Iterated random function, random function, pseudorandom function, bitcoin, password hashing, Patarin, H-coefficient technique, provable security
Created November 02, 2017, Updated November 10, 2018