Security considerations for incremental hash functions based on pair block chaining

Incremental hash functions have gained much attention due to their incremental property, i.e. hashes of updated messages can be speedily computed from previous hashes without having to re-hash the message as was the case in conventional hash functions. In this paper, we first show how collisions can be obtained in such incremental hash functions that are based on pair block chaining, highlighting that more caution should be taken into its design process. We then identify some design and implementation criteria for such incremental hash functions.