Published: December 7, 2017
Author(s)
Ritam Bhaumik (ISI), Nilanjan Datta (Indian Institute of Technology), Avijit Dutta (ISI), Nicky Mouha (NIST), Mridul Nandi (ISI)
Conference
Name: 23rd Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
Dates: 12/03/2017 - 12/07/2017
Location: Hong Kong, China
Citation: Advances in Cryptology – ASIACRYPT 2017, vol. 10625, pp. 667-697
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 functionproblem, 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(q2r(logr)3/N), where N is the size of the domain. In previous work, the best known bound was O(q2r2/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 Ω(q2r/N), showing that our security bound is tight up to a factor of (logr)3.
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 functionproblem, and prove the first almost-tight...
See full 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 functionproblem, 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(q2r(logr)3/N), where N is the size of the domain. In previous work, the best known bound was O(q2r2/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 Ω(q2r/N), showing that our security bound is tight up to a factor of (logr)3.
Hide full abstract
Keywords
iterated random function; random function; pseudorandom function; password hashing; Patarin; H-coefficient technique; provable security
Control Families
None selected
) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)
