Subject: Re: [Cfrg] Signature question ... [RE: Actual security levels for IETF crypto]

From: Paulo Sergio Licciardi Messeder Barreto <[email-masked]>
Date: Thu, 30 Oct 2014 18:17:10 -0200 (BRST)

> Date: Thu, 30 Oct 2014 13:55:12 -0400
> From: David Leon Gil <[email-masked]>
> To: Watson Ladd <[email-masked]>
> Cc: Dan Brown <[email-masked]>, "[email-masked]" <[email-masked]>
> Subject: Re: [Cfrg] Signature question ... [RE: Actual security
> levels
> for IETF crypto]
> Message-ID:
> <[email-masked]>
> Content-Type: text/plain; charset=UTF-8

> On Thu, Oct 30, 2014 at 10:54 AM, Watson Ladd <[email-masked]>
> wrote:
> > While the above is certainly interesting theoretically, I doubt it
> > matters practically. Schnorr signatures have been intensively
> > studied
> > for many years, with no attacks, as have ECDSA.

> Agreed: But I prefer security reductions to the absence of attacks,
> where at all possible. The former proves security; the latter only
> proves a lack of cleverness.

> > The question is one over how annoyed you want the implementor to
> > be,
> > when they have to try to make a constant time inversion modulo an
> > ugly
> > prime.

> Well, doing arithmetic modulo an ugly prime is already necessary for
> Schnorr.

> And if you read the Katz et al. paper, you will see that signing does
> not require performing an inversion mod #K.

The Katz et al. scheme is a direct variant of Schnorr, *not* of ECDSA. It also requires *two* exponentiations for signing, which is worse than doing an inversion. It is also inferior on all accounts to Shao's variant of Schnorr [Shao], whose security reduction is as tight as it can be (and it requires a single exponentiation and no modular inversion, just an extra hash, with negligible computational overhead). 

P. 

-- 

[Shao] Z. Shao, A provably secure short signature scheme based on discrete logarithms, Information Sciences 177(23), 2007, pp. 5432--5440, Elsevier. <http://www.sciencedirect.com/science/article/pii/S0020025507002757>

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 30 Oct 2014 17:16:35 -0700

> On Oct 30, 2014, at 1:17 PM, Paulo Sergio Licciardi Messeder Barreto <[email-masked]> wrote:
> 
> 
> From: David Leon Gil <[email-masked] <mailto:[email-masked]>>
> To: Watson Ladd <[email-masked] <mailto:[email-masked]>>
> Cc: Dan Brown <[email-masked] <mailto:[email-masked]>>, "[email-masked] <mailto:[email-masked]>" <[email-masked] <mailto:[email-masked]>>
> Subject: Re: [Cfrg] Signature question ... [RE: Actual security levels
>         for IETF crypto]
> Message-ID:
>         <[email-masked] <mailto:[email-masked]>>
> On Thu, Oct 30, 2014 at 10:54 AM, Watson Ladd <[email-masked] <mailto:[email-masked]>> wrote:
> > matters practically. Schnorr signatures have been intensively studied
> > The question is one over how annoyed you want the implementor to be,
> > when they have to try to make a constant time inversion modulo an ugly
> > prime.
> 
> Well, doing arithmetic modulo an ugly prime is already necessary for Schnorr.
> 
> [Shao] Z. Shao, A provably secure short signature scheme based on discrete logarithms, Information Sciences 177(23), 2007, pp. 5432--5440, Elsevier. <http://www.sciencedirect.com/science/article/pii/S0020025507002757 <http://www.sciencedirect.com/science/article/pii/S0020025507002757>>

That sounds really useful.  Do you have a quick description for those of us who aren’t at a university?

Thanks,
— Mike