An Investigation of the Enhanced Target Collision Resistance Property for Hash Functions

Mohammad Reza Reyhanitabar; Willy Susilo; Yi Mu

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2009/506

An Investigation of the Enhanced Target Collision Resistance Property for Hash Functions

Mohammad Reza Reyhanitabar, Willy Susilo, and Yi Mu

Abstract

We revisit the enhanced target collision resistance (eTCR) property as a newly emerged notion of security for dedicated-key hash functions, which has been put forth by Halevi and Krawczyk at CRYPTO'06, in conjunction with the Randomized Hashing mode to archive this property. Our contribution is twofold. Firstly, we provide a full picture of the relationships between eTCR and each of the seven security properties for a dedicated-key hash function, considered by Rogaway and Shrimpton at FSE'04; namely, collision resistance (CR), the three variants of second-preimage resistance (Sec, aSec, eSec) and the three variants of preimage resistance (Pre, aPre, ePre). The results show that, for an arbitrary dedicated-key hash function, eTCR is not implied by any of these seven properties, and it can only imply three of the properties; namely, eSec (TCR), Sec, Pre. In the second part of the paper, we analyze eTCR preservation capabilities of several domain extension transforms (a.k.a. modes of operation) for hash functions, including (Plain, Strengthened, and Prefix-free) Merkle-Damgård, Randomized Hashing (variant in the dedicated-key hash function setting), Shoup, Enveloped Shoup, XOR Linear Hash (XLH), and Linear Hash (LH) methods. From this analysis it turns out that, with the exception of a nested variant of LH construction, none of the investigated transforms can preserve eTCR property.

Note: Revised to correct some typos and minor technical errors in the previous version.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Hash Functions Security Notions eTCR Relationships Domain Extension
Contact author(s): mrr790 @ uow edu au
History: 2010-01-12: last of 4 revisions; 2009-10-20: received; See all versions
Short URL: https://ia.cr/2009/506
License: CC BY

BibTeX

@misc{cryptoeprint:2009/506,
      author = {Mohammad Reza Reyhanitabar and Willy Susilo and Yi Mu},
      title = {An Investigation of the Enhanced Target Collision Resistance Property for Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/506},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/506}},
      url = {https://eprint.iacr.org/2009/506}
}