For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Connections among Several Versions of One-Way Hash Functions
Yuliang ZHENG Tsutomu MATSUMOTO Hideki IMAI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/07/25
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security)
Category: Authentication Techniques
Full Text: PDF(772.7KB)>>
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.