Collision-Resistant No More: Hash-and-Sign Paradigm Revisited

A signature scheme constructed according to the hash-and-sign paradigm—hash the message and then sign the hash, symbolically

σ

(

H

(

M

))—is no more secure than the hash function

H

against a collision-finding attack. Recent attacks on standard hash functions call the paradigm into question. It is well known that a simple modification of the hash-and-sign paradigm may replace the collision-resistant hash with a weaker primitive—a target-collision resistant hash function (also known as a universal one-way hash, UOWHF). The signer generates a random key

k

and outputs the pair (

k

,

σ

(

k

||

H

k

(

M

))) as a signature on

M

. The apparent problem with this approach is the increase in the signature size. In this paper we demonstrate that for three concrete signature schemes, DSA, PSS-RSA, and Cramer-Shoup, the message can be hashed simultaneously with computing the signature, using one of the signature’s components as the key for the hash function. We prove that our constructions are as secure as the originals for DSA and PSS-RSA in the random oracle model and for the Cramer-Shoup signature scheme in the standard model.