Subject: Re: [Cfrg] FW: Schnorr Signatures

From: Dan Brown <[email-masked]>
Date: Mon, 7 Jul 2014 17:00:15 +0000

For half-length hashes, and thus 3b-bit Schnorr signatures (that consist of hash plus a group element), I’ve devised a hash that seems to show that the loose bound implicit in the Neven--Smart—Warinschi Theorem 2 cannot be improved without new hash assumptions.  In other words, the looseness of the results is not merely an artefact of the proof.

So, for b=128, the 128-bit hash seems to be 128-bit RPP-secure (and speculatively RPSP secure), yet when use with 192-bit Schnorr signature gives only 64-bit security.  

I’m drafting a report about this … but have confirmed it with authors.

Just to be clear, it is a contrived hash.  It does not rule out new provable security results with a tighter bound, but does prove that such a new result would require further assumptions about the hash function, not just RPP and RPSP security.

Here’s the contrived hash function: H(R||m) = H1(R) + H2(m) where H1 and H2 are secure 128-bit hashes.  Specifically, H1 needs a smoothness property (thanks to Neven for this property, I had used random oracle), and H2 needs a pre-image resistance property, to achieve the RPP property in the NSW paper.  

Note that this contrived H is not OW (it only has 64-bit security), so perhaps a new provable security result for short Schnorr adding the condition of the short hash being one-way, in addition to RPP and RPSP secure might still be possible.

From: TLS [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Monday, July 07, 2014 11:01 AM
To: [email-masked]
Subject: Re: [TLS] [Cfrg] FW: Schnorr Signatures

On Jul 7, 2014 7:53 AM, "Johannes Merkle" <[email-masked]> wrote:
>
> 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.

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.
>
>
> [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
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls