[Resource Topic] 2017/892: The Iterated Random Function Problem

Welcome to the resource topic for 2017/892

The Iterated Random Function Problem

Authors: Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, Nicky Mouha, 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.

ePrint: https://eprint.iacr.org/2017/892

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .