Digital Signatures Out of SecondPreimage Resistant Hash Functions

Abstract. We propose a new construction for Merkle authentication trees which does not require collision resistant hash functions; in con-trast with previous constructions that attempted to avoid the depen-dency on collision resistance, our technique enjoys provable security as-suming the well-understood notion of second-preimage resistance. The resulting signature scheme is existentially unforgeable when the underly-ing hash function is second-preimage resistant, yields shorter signatures, and is affected neither by birthday attacks nor by the recent progresses in collision-finding algorithms