Re: [TLS] [Cfrg] FW: Schnorr Signatures

[Johannes Merkle <[e-mail]>]

Nigel Smart wrote on 26.06.2014 22:56:
> With Schnorr you dont send the x-coord of R. What you send is
> half the hash value e
>     e=Hash(R||Message)
> So if using SHA-256 you send 128 bits of e over.

Actually, the Schnorr signature is defined as using the full hash value, but it has been repeatedly proposed (originally
by Schnorr himself) to use a half-length hash function (and that could be truncated SHA-256).

However, as you pointed out in [1], the security proofs you mentioned do not work with reduced hash length h=b AND
standard group order g = 2^(2b) for security level b. Your proof in the generic model [1] requires h=2*b and the proof
of Pointcheval and Stern in the Random oracle model [2] needs g=2^(3b). Thus, when using half-length hash values you
sacrifice provable security.


[1] Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Hash function requirements for schnorr
signatures. J. Mathematical Cryptology, 3(1):69–87, 2009

[2] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures.
Journal of Cryptology, 13(3):361–396, March 2000.


-- 
Johannes