TY - GEN
T1 - Indifferentiability characterization of hash functions and optimal bounds of popular domain extensions
AU - Bhattacharyya, Rishiraj
AU - Mandal, Avradip
AU - Nandi, Mridul
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - HAIFA
KW - Indifferentiability
KW - Merkle-Damgård
KW - Tree mode of operations with counter
UR - http://www.scopus.com/inward/record.url?scp=77649262764&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10628-6_14
DO - 10.1007/978-3-642-10628-6_14
M3 - Conference contribution
AN - SCOPUS:77649262764
SN - 3642106277
SN - 9783642106279
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 199
EP - 218
BT - Progress in Cryptology - INDOCRYPT 2009 - 10th International Conference on Cryptology in India, Proceedings
T2 - 10th International Conference on Cryptology in India, INDOCRYPT 2009
Y2 - 13 December 2009 through 16 December 2009
ER -