Indifferentiability characterization of hash functions and optimal bounds of popular domain extensions

Rishiraj Bhattacharyya*, Avradip Mandal, Mridul Nandi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)


Understanding the principle behind designing a good hash function is important. Nowadays it is getting more importance due to the current SHA3 competition which intends to make a new standard for cryptogrpahic hash functions. Indifferentiability, introduced by Maurer et al in TCC'04, is an appropriate notion for modeling (pseudo)random oracles based on ideal primitives. It also gives a strong security notion for hash-designs. Since then, we know several results providing indifferentiability upper bounds for many hash-designs. Here, we introduce a unified framework for indifferentiability security analysis by providing an indifferentiability upper bound for a wide class of hash designs GDE or generalized domain extension. In our framework, we present an unified simulator and avoid the problem of defining different simulators for different constructions. We show, the probability of some bad event (based on interaction of the attacker with the GDE and the underlying ideal primitve) is actually an upper bound for indifferentiable security. As immediate applications of our result, we provide simple and improved (in fact optimal) indifferentiability upper bounds for HAIFA and tree (with counter) mode of operations. In particular, we show that n-bit HAIFA and tree-hashing with counter have optimal indifferentiability bounds and Θ(qσ/2 n) and Θ(q2 log ℓ/22) respectively, where ℓ is the maximum number of blocks in a single query and σ is the total number of blocks in all q queries made by the distinguisher.

Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2009 - 10th International Conference on Cryptology in India, Proceedings
Number of pages20
Publication statusPublished - 2009
Event10th International Conference on Cryptology in India, INDOCRYPT 2009 - New Delhi, India
Duration: 13 Dec 200916 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5922 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Conference on Cryptology in India, INDOCRYPT 2009
CityNew Delhi


  • Indifferentiability
  • Merkle-Damgård
  • Tree mode of operations with counter

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Indifferentiability characterization of hash functions and optimal bounds of popular domain extensions'. Together they form a unique fingerprint.

Cite this