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.
LNCS: Advances in Cryptology – ASIACRYPT 2017
December 3-7, 2017
Hong Kong, CN
The 23rd Annual International Conference on the Theory and Application of Cryptology and Information
Security, ASIACRYPT 2017
, Datta, N.
, Dutta, A.
, Mouha, N.
and Nandi, M.
The Iterated Random Function Problem, LNCS: Advances in Cryptology – ASIACRYPT 2017, Hong Kong, CN, [online], https://doi.org/10.1007/978-3-319-70697-9_23, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=922854
(Accessed October 4, 2023)