International Association
for Cryptologic Research

Neven, Smart and Warinschi (NSW) proved, in the generic group model, that full-length Schnorr signatures require only random-prefix resistant hash functions to resist passive existential forgery.

Short Schnorr signatures halve the length of the hash function, and

have been conjectured to provide a similar level of security. The

NSW result is too loose to provide a meaningful security for short

Schnorr signatures, but Neven, Smart and Warinschi conjecture that

this is mere artefact of the proof technique, and not an essential

deficiency of the short Schnorr signatures. In particular, this

amounts to a conjecture that short Schnorr signature are secure

under the same set of assumptions, namely random-prefix resistance

of the hash function.

This report provides a counterexample to the latter conjecture, in

other words, a separation result. It finds a hash function that

seems to suggest random-prefix resistance does not suffice for short

Schnorr signatures. In other words, the loose reduction implicit

in the NSW theorem is as tight as possible.

Obviously, this result does not preclude the possibility of another

proof for short Schnorr signatures, based on different hash function

security properties such as preimage resistance.