Abstract
In this paper, we revisit security notions for dedicated-key hash functions, considering two essential theoretical aspects; namely, formal definitions for security notions, and the relationships among them. Our contribution is twofold. First, we provide a new set of enhanced security notions for dedicated-key hash functions. The provision of this set of enhanced properties has been motivated by the introduction of the enhanced target collision resistance (eTCR) property by Halevi and Krawczyk at Crypto 2006. We notice that the eTCR property does not belong to the set of the seven security notions previously investigated by Rogaway and Shrimpton at FSE 2004; namely: Coll, Sec, aSec, eSec, Pre, aPre and ePre. The fact that eTCR, as a new useful property, is the enhanced variant of the well-known TCR (a.k.a. eSec or UOWHF) property motivates one to investigate the possibility of providing enhanced variants for the other properties. We provide such an enhanced set of properties. Interestingly, there are six enhanced variants of security notions available, excluding “ePre” which can be demonstrated to be non-enhanceable. As the second and main part of our contribution, we provide a full picture of the relationships (i.e. implications and separations) among the (thirteen) security properties including the (six) enhanced properties and the previously considered seven properties. The implications and separations are supported by formal proofs (reductions) and/or counterexamples in the concrete-security framework.
Chapter PDF
Similar content being viewed by others
References
Bellare, M., Rogaway, P.: Collision-Resistant Hashing: Towards Making UOWHFs Practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 470–484. Springer, Heidelberg (1997)
Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002)
Contini, S., Steinfeld, R., Pieprzyk, J., Matusiewicz, K.: A Critical Look at Cryptographic Hash Function Literature. In: ECRYPT Hash Workshop (2007)
Damgård, I.: Collision Free Hash Functions and Public Key Signature Schemes. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203–216. Springer, Heidelberg (1988)
Damgård, I.B.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. on Information Theory IT-22(6), 644–654 (1976)
Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Halevi, S., Krawczyk, H.: Strengthening Digital Signatures Via Randomized Hashing. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 41–59. Springer, Heidelberg (2006)
Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2n Work. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.C.: Secrecy, Authentication, and Public Key Systems. UMI Research Press (1979)
Merkle, R.C.: One Way Hash Functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
Naor, M., Yung, M.: Universal One-Way Hash Functions and Their Cryptographic Applications. In: Proceedings of the 21st ACM Symposium on the Theory of Computing–STOC 1989, pp. 33–43. ACM, New York (1989)
National Institute of Standards and Technology. FIPS PUB 180-2: Secure Hash Standard (August 2002)
National Institute of Standards and Technology. FIPS PUB 180-3: Secure Hash Standard (June 2007)
National Institute of Standards and Technology. NIST SP 800-106: Randomized Hashing for Digital Signatures (February 2009), http://www.csrc.nist.gov/publications/PubsSPs.html#800-106 (September 20, 2009)
National Institute of Standards and Technology. Cryptographic Hash Algorithm Competition, http://csrc.nist.gov/groups/ST/hash/sha-3/index.html (September 20, 2009)
Preneel, B.: Analysis and Design of Cryptographic Hash Functions. Doctoral dissertation, K. U. Leuven (1993)
Rabin, M.O.: Digitalized Signatures. In: Lipton, R., DeMillo, R. (eds.) Foundations of Secure Computation, pp. 155–166. Academic Press, New York (1978)
Reyhanitabar, M.R., Susilo, W., Mu, Y.: Enhanced Target Collision Resistant Hash Functions Revisited. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 327–344. Springer, Heidelberg (2009)
Reyhanitabar, M.R., Susilo, W., Mu, Y.: An Investigation of the Enhanced Target Collision Resistance Property for Hash Functions. Cryptology ePrint Archive, Report 2009/506 (2009)
Reyhanitabar, M.R., Susilo, W., Mu, Y.: Enhanced Security Notions for Dedicated-Key Hash Functions: Definitions and Relationships. Cryptology ePrint Archive, Report 2010/022 (2010)
Rivest, R.: The MD5 Message-Digest Algorithm. RFC 1321 (April 1992), http://www.ietf.org/rfc/rfc1321.txt (September 19, 2009)
Rogaway, P., Shrimpton, T.: Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 371–388. Springer, Heidelberg (2004)
Rogaway, P., Shrimpton, T.: Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. Cryptology ePrint Archive: Report 2004/035 (Revised version of [24]: August 9, 2009)
Rogaway, P.: Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 211–228. Springer, Heidelberg (2006)
Yasuda, K.: How to Fill Up Merkle-Damgård Hash Functions. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 272–289. Springer, Heidelberg (2008)
Zheng, Y., Matsumoto, T., Imai, H.: Connections among several versions of one-way hash functions. In: Proceedings of IEICE, Special Issue on Cryptography and Information Security, Japan (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reyhanitabar, M.R., Susilo, W., Mu, Y. (2010). Enhanced Security Notions for Dedicated-Key Hash Functions: Definitions and Relationships. In: Hong, S., Iwata, T. (eds) Fast Software Encryption. FSE 2010. Lecture Notes in Computer Science, vol 6147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13858-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-13858-4_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13857-7
Online ISBN: 978-3-642-13858-4
eBook Packages: Computer ScienceComputer Science (R0)