You are looking at a specific version 20130614:095735 of this paper. See the latest version.

Paper 2013/350

Ideal-Cipher (Ir)reducibility for Blockcipher-Based Hash Functions

Paul Baecher and Pooya Farshim and Marc Fischlin and Martijn Stam

Abstract

Preneel et al.~(Crypto 1993) assessed 64 possible ways to construct a compression function out of a blockcipher. They conjectured that 12 out of these 64 so-called PGV constructions achieve optimal security bounds for collision resistance and preimage resistance. This was proven by Black et al.~(Journal of Cryptology, 2010), if one assumes that the blockcipher is ideal. This result, however, does not apply to ``non-ideal'' blockciphers such as AES. To alleviate this problem, we revisit the PGV constructions in light of the recently proposed idea of random-oracle reducibility (Baecher and Fischlin, Crypto 2011). We say that the blockcipher in one of the 12 secure PGV constructions reduces to the one in another construction, if \emph{any} secure instantiation of the cipher, ideal or not, for one construction also makes the other secure. This notion allows us to relate the underlying assumptions on blockciphers in different constructions, and show that the requirements on the blockcipher for one case are not more demanding than those for the other. It turns out that this approach divides the 12 secure constructions into two groups of equal size, where within each group a blockcipher making one construction secure also makes all others secure. Across the groups this is provably not the case, showing that the sets of ``good'' blockciphers for each group are qualitatively distinct. We also relate the ideal ciphers in the PGV constructions with those in double-block-length hash functions such as Tandem-DM, Abreast-DM, and Hirose-DM. Here, our results show that, besides achieving better bounds, the double-block-length hash functions rely on weaker assumptions on the blockciphers to achieve collision and everywhere preimage resistance.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. EUROCRYPT 2013
Keywords
Ideal-cipher modelHash functionBlockcipherReducibility.
Contact author(s)
pbaecher @ gmail com
History
2013-06-14: revised
2013-06-10: received
See all versions
Short URL
https://ia.cr/2013/350
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.