Weak Security Notions of Cryptographic Unkeyed Hash Functions and Their Amplifiability

Shoichi HIROSE 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E88-A  No.1  pp.33-38
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Cryptography
Keyword: 
cryptographic hash function,  collision resistance,  weak collision resistance,  second-preimage resistance,  weak second-preimage resistance, 

Full Text: PDF(150.7KB)

Summary: 
Cryptographic unkeyed hash functions should satisfy preimage resistance, second-preimage resistance and collision resistance. In this article, weak second-preimage resistance and weak collision resistance are defined following the definition of weak one-wayness. Preimage resistance is one-wayness of cryptographic hash functions. The properties of weak collision resistance is discussed in this article. The same kind of results can be obtained for weak second-preimage resistance. Weak collision resistance means that the probability of failing to find a collision is not negligible, while collision resistance means that the success probability is negligible. It is shown that there really exist weakly collision resistant hash functions if collision resistant ones exist. Then, it is shown that weak collision resistance is amplifiable, that is, collision resistant hash functions can be constructed from weakly collision resistant ones. Unfortunately, the method of amplification presented in this article is applicable only to a certain kind of hash functions. However, the method is applicable to hash functions based on discrete logarithms. This implies that collision resistant hash functions can be obtained even if the discrete logarithm problem is much easier than is believed and only weakly intractable, that is, exponentiation modulo a prime is weakly one-way.