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

From: Johannes Merkle <[email-masked]>
Date: Mon, 7 Jul 2014 16:53:16 +0200

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

---

From: Watson Ladd <[email-masked]>
Date: Mon, 7 Jul 2014 08:01:03 -0700

On Jul 7, 2014 7:53 AM, "Johannes Merkle" <[email-masked]>
wrote:
> Actually, the Schnorr signature is defined as using the full hash value,
but it has been repeatedly proposed (originally
> 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.

While the Pointcheval and Stern result is not tight, no one has made
attacks that do better.

The most compact and performant variant sends R and S. R is the size of a
group element, S the size of order of the group. This way the length of
what is to be transmitted does not depend on the hash used.
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 7 Jul 2014 18:10:11 +0200

Watson Ladd wrote on 07.07.2014 17:01:
> 
> On Jul 7, 2014 7:53 AM, "Johannes Merkle" <[email-masked] <mailto:[email-masked]>> wrote:
>>
> While the Pointcheval and Stern result is not tight, no one has made attacks that do better.

I didn't mean to imply that loosing the security proof makes the scheme insecure. But we have the choice (for 128 bit
security level):
1. Use the provably secure version with signature length of 64 byte
2. Use an optimized version without security proof giving signature length of 48 byte.

> 
> The most compact and performant variant sends R and S. R is the size of a group element, S the size of order of the
> group. This way the length of what is to be transmitted does not depend on the hash used.

Hmmm, by Hasse's theorem and for moderate co-factors, the size of the group roughly equals the size of the group
elements. Thus, this variant has about the same signature length as the original version (64 byte for 128 bit security).
Or do I miss something?

-- 
Johannes