Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The Iterated Random Function Problem

Published

Author(s)

Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, Nicky Mouha, Mrudil 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 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, CN
Conference Title
The 23rd Annual International Conference on the Theory and Application of Cryptology and Information
Security, ASIACRYPT 2017

Keywords

Iterated random function, random function, pseudorandom function, bitcoin, password hashing, Patarin, H-coefficient technique, provable security

Citation

Bhaumik, R. , Datta, N. , Dutta, A. , Mouha, N. and Nandi, M. (2017), 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 March 29, 2024)
Created November 1, 2017, Updated April 8, 2022