Collision-Resistant and Pseudorandom Hashing Modes of Compression Functions

This paper presents two novel keyed hashing modes, KHC1 and KHC2, designed to construct hash functions that guarantee both collision resistance and pseudorandomness. These modes employ compression functions alongside unique encoding schemes, enabling efficient handling of variable-length inputs. The proposed constructions achieve collision resistance, provided that the underlying compression function satisfies the extended notion of collision resistance, which ensures that it is intractable to find distinct input pairs whose output difference falls within a small set. They are also proven to be secure pseudorandom functions (PRFs) under the assumption that the underlying compression function is a secure PRF under related-key attacks. They accept a 256-bit key as input and guarantee 128-bit security against quantum key recovery when instantiated with the SHA-256 compression function. Furthermore, we implemented KHC1 and KHC2 instantiated with the SHA-256 compression function and evaluated their performance. The results confirm that both constructions achieve the efficiency expected by the theoretical evaluation and outperform HMAC-SHA-256 for short messages.