### The Iterated Random Function Problem

Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, 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$.

Available format(s)
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
Iterated random functionrandom functionpseudorandom functionpassword hashingPatarinH-coefficient techniqueprovable security
Contact author(s)
nicky @ mouha be
History
Short URL
https://ia.cr/2017/892

CC BY

BibTeX

@misc{cryptoeprint:2017/892,
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{https://eprint.iacr.org/2017/892}},
url = {https://eprint.iacr.org/2017/892}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.