PGV-Style Block-Cipher-Based Hash Families and Black-Box Analysis

Wonil LEE  Mridul NANDI  Palash SARKAR  Donghoon CHANG  Sangjin LEE  Kouichi SAKURAI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E88-A  No.1  pp.39-48
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: 
hash function,  block cipher,  black-box model,  provable security, 

Full Text: PDF(265.6KB)

Summary: 
In [1] it was proved that 20 of 64 PGV hash functions based on block cipher are collision-resistant and one-way in the black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that, aside from the previously reported 20 hash functions, we have 22 more collision-resistant and one-way hash families. As all these 42 families are keyed hash family, these are also target-collision-resistant. All these 42 hash families have tight upper and lower bounds on (target) collision-resistant and one-way-ness.