Connections among Several Versions of One-Way Hash Functions

Yuliang ZHENG  Tsutomu MATSUMOTO  Hideki IMAI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.7   pp.1092-1099
Publication Date: 1990/07/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security)
Category: Authentication Techniques
Keyword: 


Full Text: PDF(772.7KB)>>
Buy this Article




Summary: 
We study the following two kinds of one-way hash functions: universal one-way hash functions (UOHs) and collision intractable hash functions (CIHs). The main property of the former is that given an initial-string x, it is computationally difficult to find a different string y that collides with x. And the main property of the latter is that it is computationally difficult to find a pair xy of strings such that x collides with y. Our main results are as follows. First we prove that UOHs with respect to initial-strings chosen arbitrarily exist if and only if UOHs with respect to initial-strings chosen uniformly at random exist. Then, as an application of the result, we show that UOHs with respect to initial-strings chosen arbitrarily can be constructed under a weaker assumption, the existence of one-way quasi-injections. Finally, we investigate relationships among different versions of one-way hash functions. We prove that some versions of one-way hash functions are strictly included in others by explicitly constructing hash functions that are one-way in the sense of the former but not in the sense of the latter.